3 ms·
Good read: cPython's dictionary implementation
- russell 17y agoThe 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.
- kingkilr 17y agohttp://svn.python.org/view/python/trunk/Objects/dictnotes.txt?view=markup http://svn.python.org/view/python/trunk/Objects/dictnotes.tx... is a great summary of the issues.
- nas 17y agoTim 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_generators.py?revision=73489&view=markup http://svn.python.org/view/python/trunk/Lib/test/test_genera... .
- mrduncan 17y agoAlso worth noting that timsort is used for array sorting in Java 7. http://bugs.sun.com/bugdatabase/view%5Fbug.do?bug%5Fid=6804124 http://bugs.sun.com/bugdatabase/view%5Fbug.do?bug%5Fid=68041...
- mgrouchy 17y agoiirc isn't there a chapter in Beautiful Code about this? http://oreilly.com/catalog/9780596510046 http://oreilly.com/catalog/9780596510046
- paulgb 17y agoLooks 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)
- neilc 17y agoYeah, I thought it was worth reading. I liked Bentley's Programming Pearls more though, as a book in a similar vein.
- g__ 17y agoI have mixed feelings. http://stackoverflow.com/questions/184118/what-programming-book-would-you-not-recommend-to-developers http://stackoverflow.com/questions/184118/what-programming-b... http://www.amazon.com/review/R1W0YZZWT53Y9M/ref=cm_cr_rdp_perm http://www.amazon.com/review/R1W0YZZWT53Y9M/ref=cm_cr_rdp_pe...