On Thursday 08 November 2007 02:43, Martin Albrecht wrote: > > Hashing string is definitely one of the easiest ways to get a lot of > > semantics that we want ... i.e. agreement with '=='. In all other > > respects, it seems like one of the most awful hash algorithms one could > > imagine. However, I'm not saying it's a bad design decision since > > agreement with '==' is pretty much the central requirement. > > Is it? Is this written down somewhere? It is just that I hear the first > time about this requirement in this thread. I usually aimed for speed and > small chance of clashes first.
Well, I have an example somewhere up this thread of a substitution that "fails" due to the fact that the generators of a fraction field of a poly ring do not hash the same as the generators of the poly ring. This seems a great shame because to any mathematician these are utterly synonymous. The other thread I linked http://groups.google.com/group/sage-devel/msg/b3812493e9d2d2c8 references python documentation which demands this. The point is that if the hash doesn't get you into the right bucket in the dictionary, then you are doomed for extracting the item corresponding to the key you want. I was thinking more about this and I conclude that all sage polynomials hash entirely incorrectly (in regards to this '==' desire). For one thing the constant polynomial 1 should hash to 1 just like the integer 1. Then, if there are non-constant monomials, we should be hashing in the variable names of the variables with non-zero powers. I believe that one could work out a scheme whereby multi-variable and univariable polys over ZZ (and also QQ) would all hash compatibly. Whether or not this could be fast (enough), I don't know. I would certainly think that it could be faster than converting to a string! I am beginning to wonder if the use of dictionaries in sage is simply a broken concept. As was discussed at great length in the other thread, you simply can't support the '==' requirement in all cases (with-out hashing everything to 0). And further, I'm investigating some uses of dictionaries to examine whether the dictionary lookup is even a good algorithm because of the "slow" hash times. I was assuming that using a dictionary is much faster than keyword arguments for substitution, but I have my doubts now. -- Joel --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
