Ordered Sets

[Nick Craig-Wood]

Aahz <aahz at pythoncraft.com> wrote:
> 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.

Hmmm... Lets compare the two.

Here is the length three list

$ python
Python 2.5.2 (r252:60911, Jan  4 2009, 17:40:26)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> L = []
>>> for i in xrange(1000000):
...     L.append([1,2,3])
...
>>> import os
>>> os.getpid()
28134
>>>

(from top)
28134 ncw       20   0 58860  53m 1900 S    0  2.6   0:02.62 python

vs a Node class with __slots__ (for efficiency)

$ python
Python 2.5.2 (r252:60911, Jan  4 2009, 17:40:26)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> class Node(object):
...     __slots__ = ["prev", "next", "this"]
...     def __init__(self, prev, next, this):
...         self.prev = prev
...         self.next = next
...         self.this = this
...
>>> Node(1,2,3)
<__main__.Node object at 0xb7e897cc>
>>> Node(1,2,3).prev
1
>>> L = []
>>> for i in xrange(1000000):
...     L.append(Node(1,2,3))
...
>>> import os
>>> os.getpid()
28203
>>>

(from top)
28203 ncw       20   0 43364  38m 1900 S    0  1.9   0:04.41 python

So the Node class actually takes less memory 38 Mbytes vs 53 Mbytes for
the list.

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick