Ordered Sets

[Aahz]

In article <01d457aa$0$17208$c3e8da3 at news.astraweb.com>,
Steven D'Aprano  <steve at REMOVE-THIS-cybersource.com.au> wrote:
>On Fri, 20 Mar 2009 11:50:28 -0700, Scott David Daniels wrote:
>> Raymond Hettinger wrote:
>>> [Aahz]
>>>>
>>>> The doubly-linked list part is what's sick and perverted.
>>> 
>>> The doubly-linked list part is what gives it big-oh running times the
>>> same as regular sets.  If the underlying sequence is stored as a list,
>>> then deletion goes from O(1) to O(n). If the insertion times are
>>> recorded in a dictionary, then the insertion order has to be sorted
>>> prior to iteration which makes iteration go from O(n) to O(n log n).
>> 
>> The double-linked list part could be done with weakrefs and perhaps Aahz
>> would relax a bit.
>
>I'm not sure whether Aahz's description is meant to be taken seriously, 
>or if there is a smiley hidden in his post. After all, doubly-linked 
>lists are a standard building block in data structure design.

It's a half-smiley.  I find the trick of using a Python list to store the
doubly-linked list difficult to understand (as opposed to the usual
mechanism of a node class).  I understand why it was done (time and space
efficiency), but I also still feel emotionally that it's somewhat sick
and perverted.  I probably would feel more comfortable if the
doubly-linked list were abstracted out and commented.  Heck, the whole
thing needs unit tests.

I needed to look up the code again, so I might as well repeat the URL to
make it handy for everyone else:

http://code.activestate.com/recipes/576694/
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by
definition, not smart enough to debug it."  --Brian W. Kernighan