In article <01d457aa$0$17208$c3e8...@news.astraweb.com>, Steven D'Aprano <st...@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 (a...@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 -- http://mail.python.org/mailman/listinfo/python-list
