On Sun, Feb 27, 2011 at 07:00:22AM -0800, bump wrote:
> Something is wrong, however. Before the patches, the following takes
> about 32 seconds:
>
> A2=WeylCharacterRing("A2",style="coroots")
> A7=WeylCharacterRing("A7",style="coroots")
> s = A7.fundamental_weights()[1]
> ad=A2(1,1)
> time A7(5*s).branch(A2,rule=branching_rule_from_plethysm(ad,"A7"))
>
> After the patches (or just the hash patch) it takes about 350.
Ah ah, interesting! After analysis, it turns out that the hash
function I proposed induces a lot of collisions, which is *bad*. The
point is that the hash function on tuples is close to "additive":
sage: x = 4/3
sage: y = 13/8
sage: hash( (1,x) ) - hash( (1,y) )
-2165050
sage: hash( (2,x) ) - hash( (2,y) )
-2165050
sage: hash( (3,x) ) - hash( (3,y) )
2165050
sage: hash( (0,x) ) - hash( (0,y) )
2165050
sage: hash( (4,x) ) - hash( (4,y) )
2165050
Then, with my hash function, if one exchanges two coefficients in a
free module element, then one often gets a collision. E.g. on gets
the same hash value with the two vectors:
x * B(1) + y * B(2) + rest and y*B(1) + x*B(2) + rest
A bit of care will be needed for optimizing __hash__. I thus propose
to split the problem in two:
- For #7922: understanding why in your example the hash function gets
called sooo often. For this, we should look at a smallest possible
example where hash is obviously called too often.
- Independently on #7922: creating a new ticket for optimizing hash
and equality tests for free module elements. Both are currently
lousy. Both will require a bit of thought and we might use the
occasion to cython them.
I am going to guard out trac_7922-hash-nt.patch.
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
