PEP 372 -- Adding an ordered directory to collections
lukius at gmail.com
Sun Aug 7 14:56:16 CEST 2011
I'm a first-time writer here, so excuse me if I say something inappropriate
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:
Comments will be surely appreciated!
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list