Hi all,<div><br></div><div>I'm a first-time writer here, so excuse me if I say something inappropriate or such.</div><div><br></div><div>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 <span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">bearophile, but nevertheless I think it is more efficient since there is no need to perform lookups multiple times.</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></span></div><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">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.</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></span></div><div><font class="Apple-style-span" face="arial, sans-serif">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.  </font></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></span></div><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">I made up a recipe with the code and several comments, including more details about the experimentation mentioned above:</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><a href="http://code.activestate.com/recipes/577826-yet-another-ordered-dictionary/">http://code.activestate.com/recipes/577826-yet-another-ordered-dictionary/</a></span></div>
<div><br></div><div><br></div><div>Comments will be surely appreciated!</div><div><br></div><div><br></div><div>Lucio</div>