Aahz <a...@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 <n...@craig-wood.com> -- http://www.craig-wood.com/nick -- http://mail.python.org/mailman/listinfo/python-list