Good read: cPython's dictionary implementation(svn.python.org)
svn.python.org
Good read: cPython's dictionary implementation
http://svn.python.org/view/python/trunk/Objects/dictobject.c?view=markup
8 comments
Tim Peters is very good at practical algorithm design. He one of the primary designers of the Python dictionary algorithms. His sort algorithm (timsort) is also pretty cool. Also check out the Knights Tour and N-Queens algorithms in the unit tests: <http://svn.python.org/view/python/trunk/Lib/test/test_genera... .
Also worth noting that timsort is used for array sorting in Java 7.
http://bugs.sun.com/bugdatabase/view%5Fbug.do?bug%5Fid=68041...
http://bugs.sun.com/bugdatabase/view%5Fbug.do?bug%5Fid=68041...
The introductory comments are an excellent read about the pragmatics of good hash table design. It would have been really helpful a couple of decades back when I was routinely implementing custom hash tables. OTOH tuning the probe parameters for a table was always an entertaining way to spend an afternoon. Generating a perfect hash for an evolving keyword table was too cumbersome, but trying to reach nearly every symbol in a dense table with a single probe was good sport.
http://svn.python.org/view/python/trunk/Objects/dictnotes.tx... is a great summary of the issues.
iirc isn't there a chapter in Beautiful Code about this? http://oreilly.com/catalog/9780596510046
Looks like a good book, would you recommend it?
(Also, looks like this is a chapter: Chapter 18 Python's Dictionary Implementation: Being All Things to All People)
(Also, looks like this is a chapter: Chapter 18 Python's Dictionary Implementation: Being All Things to All People)
Yeah, I thought it was worth reading. I liked Bentley's Programming Pearls more though, as a book in a similar vein.