Hi all, I'm a first-time writer here, so excuse me if I say something inappropriate or such.
Last week, I was reviewing some Python 2.7 modules when I came across the OrderedDict data structure. After seeing its official implementation and also after reading through the corresponding PEP, I figured out another way of implementing it. As I recently saw here, the idea is similar to the one proposed by bearophile, but nevertheless I think it is more efficient since there is no need to perform lookups multiple times. The idea is to embed the doubly-linked list of items in the dictionary itself, and extend the values inserted by providing a node as a 4-tuple <key, value, previous node, next node>. Of course, references to the first and last nodes must be kept too, in addition to the dictionary. After implementing this approach, I experimented a little bit and compared both versions (i.e., the official one that uses an extra dictionary and mine) by measuring the running times of some basic operations. I verified that it indeed outperforms the existing implementation. I made up a recipe with the code and several comments, including more details about the experimentation mentioned above: http://code.activestate.com/recipes/577826-yet-another-ordered-dictionary/ Comments will be surely appreciated! Lucio
-- http://mail.python.org/mailman/listinfo/python-list