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.