Raymond Hettinger: >Paul Rubin: >>another (messy) approach would be to write a C >>extension that uses a doubly linked list some day. > > That seems like an ideal implementation to me.
This was my Python implementation, where the delete too is O(1), but it's slow: http://code.activestate.com/recipes/498195/ I think the C extension with the doubly linked list is the best approach. Note that in modern CPUs caches are able to change the performance a lot. So reducing the memory used is very important. So using the XOR (or subtraction) trick to use only 1 pointer for each key-value may be useful to keep performance not too much far from the normal python dicts: http://en.wikipedia.org/wiki/XOR_linked_list Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
