On Jul 11, 8:01 am, [EMAIL PROTECTED] wrote: > Following links from this > thread:http://groups.google.com/group/comp.lang.python/browse_thread/thread/... > > I have found this perfect hash (minimal too) > implementation:http://burtleburtle.net/bob/hash/perfect.html > > I have already translated part of it to D, and it seems to work well > enough. As discussed in the PyConDue, I think this may be used in > frozenset (and frozendict) to build a (minimal too?) perfect hash on > the fly, to allow (hopefully) faster retrieval of items that don't > change. > That code is C and I think it's public domain, so if experiments show > it gives enough speed up, it may be added to CPython 2.6/3. > > Bye, > bearophile
It would be interesting to see if such an algorithm could actually provide any significant performance improvements for the size of sets that I suspect are most often used in practice. The chance of a hash collision for a good 32-bit general is fairly low even for a set of 1,000,000 unique elements, which seems to me to be a pretty large memory-based set. Compare that with the cost of determining a perfect hash (O(n**2)?). >From my perspective, a perfect hash would certainly be a welcome addition to the Python library or even as an optional algorithm supporting hash-based collections. -- http://mail.python.org/mailman/listinfo/python-list
