PEP 372 -- Adding an ordered directory to collections

[Lucio Santi]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110807/bac97dd8/attachment.html>