True lists in python?

Discussion in 'Python' started by Dmitry Groshev, Dec 19, 2010.

  1. Is there any way to use a true lists (with O(c) insertion/deletion and
    O(n) search) in python? For example, to make things like reversing
    part of the list with a constant time.
    Dmitry Groshev, Dec 19, 2010
    #1
    1. Advertising

  2. On Dec 19, 9:18 am, Dmitry Groshev <> wrote:
    > Is there any way to use a true lists (with O(c) insertion/deletion and
    > O(n) search) in python? For example, to make things like reversing
    > part of the list with a constant time.


    I forgot to mention that I mean *fast* lists. It's trivial to do
    things like this with objects, but it will be sloooow.
    Dmitry Groshev, Dec 19, 2010
    #2
    1. Advertising

  3. Dmitry Groshev wrote:

    > Is there any way to use a true lists (with O(c) insertion/deletion and
    > O(n) search) in python? For example, to make things like reversing
    > part of the list with a constant time.


    if you're interested just in "reverse" a collection maybe you can take a
    look at the deque[0] module.

    If you want "true lists" (um... "linked list"?) there are is this recipe[1]
    you might look.

    [0] http://docs.python.org/library/collections.html#collections.deque
    [1] http://code.activestate.com/recipes/577355-python-27-linked-list-vs-
    list/

    --
    By ZeD
    Vito 'ZeD' De Tullio, Dec 19, 2010
    #3
  4. On Dec 19, 9:48 am, Vito 'ZeD' De Tullio <>
    wrote:
    > Dmitry Groshev wrote:
    > > Is there any way to use a true lists (with O(c) insertion/deletion and
    > > O(n) search) in python? For example, to make things like reversing
    > > part of the list with a constant time.

    >
    > if you're interested just in "reverse" a collection maybe you can take a
    > look at the deque[0] module.
    >
    > If you want "true lists" (um... "linked list"?) there are is this recipe[1]
    > you might look.
    >
    > [0]http://docs.python.org/library/collections.html#collections.deque
    > [1]http://code.activestate.com/recipes/577355-python-27-linked-list-vs-
    > list/
    >
    > --
    > By ZeD


    -I can't find any information about reverse's complexity in python
    docs, but it seems that deque is a linked list. Maybe this is the one
    I need.
    -Yes, I meant linked list - sorry for misunderstanding.
    -Linked list on objects is too slow. It must be a C-extension for a
    proper speed.
    Dmitry Groshev, Dec 19, 2010
    #4
  5. Dmitry Groshev

    Paul Rubin Guest

    Dmitry Groshev <> writes:
    > -I can't find any information about reverse's complexity in python
    > docs, but it seems that deque is a linked list. Maybe this is the one
    > I need.


    Deques are not linked lists. They're just like regular Python lists
    (i.e. resizeable arrays) except they can grow and shrink at both ends
    rather than just one. The amortized complexity of an append or pop
    operation (at either end) is O(1) but occasionally the list has to
    be reallocated, which is O(N).
    Paul Rubin, Dec 19, 2010
    #5
  6. On Sat, 18 Dec 2010 22:18:07 -0800, Dmitry Groshev wrote:

    > Is there any way to use a true lists (with O(c) insertion/deletion and
    > O(n) search) in python?


    Python lists have amortized constant time insertion and deletion at the
    end of the list, O(N) insertion and deletion at the beginning of the
    list, and O(N) search.


    > For example, to make things like reversing part
    > of the list with a constant time.


    It's been many years since I've had to worry about rolling my own low-
    level linked lists, but I don't think that reversing a list can be done
    in constant time.

    I can't see any way to go from this linked list:

    node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> node7

    to this:

    node1 -> node6 -> node5 -> node4 -> node3 -> node2 -> node7

    in constant time. You have to touch each of the nodes being reversed.

    Others have already suggested you look at deques, but I'm curious as to
    what application you have where regular lists are too slow. (I assume you
    have actually profiled your application, and are trying to solve an
    actual speed issue, not just assuming it is slow.) I would normally
    reverse a portion of a list like this:

    mylist[23:42] = mylist[23:42][::-1]

    So long as the section you are reversing is small enough to fit in memory
    without paging, this should be quite quick.



    --
    Steven
    Steven D'Aprano, Dec 19, 2010
    #6
  7. Steven D'Aprano wrote:

    > I can't see any way to go from this linked list:
    >
    > node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> node7
    >
    > to this:
    >
    > node1 -> node6 -> node5 -> node4 -> node3 -> node2 -> node7
    >
    > in constant time. You have to touch each of the nodes being reversed.


    very crude example:


    class Node(object):
    def __init__(self, value, list):
    self.value = value
    self.next = self.previous = None
    self.list = list

    def nextNode(self):
    if not self.list.reversed:
    return self.next
    else:
    return self.previous

    class LinkedList(object):
    def __init__(self):
    self.head = None
    self.reversed = False
    def insertAsHead(self, value):
    n = Node(value, self)
    n.next = self.head
    if self.head is not None:
    self.head.previous = n
    self.head = n

    def main():
    ll = LinkedList()
    ll.insertAsHead(4)
    ll.insertAsHead(3)
    ll.insertAsHead(2)

    n = ll.head
    while n is not None:
    n_previous = n
    print n.value
    n = n.nextNode()

    print 'reversed'

    ll.reversed = True

    n = n_previous
    while n is not None:
    print n.value
    n = n.nextNode()

    if __name__ == '__main__':
    main()


    --
    By ZeD
    Vito 'ZeD' De Tullio, Dec 19, 2010
    #7
  8. Dmitry Groshev wrote:
    > Is there any way to use a true lists (with O(c) insertion/deletion
    > and O(n) search) in python?


    Inserting/deleting in the middle requires shuffling elements around, since
    Python's list is an array/vector. If you don't rely on the ordering, insert
    or delete at the end instead, possibly swapping the last element with the
    one you want to delete first:

    class x(list):
    def pop(self, index=None):
    if index is None:
    return list.pop(self)
    res = self[index]
    self[index] = self[-1]
    self.pop()
    return res


    > For example, to make things like reversing
    > part of the list with a constant time.


    a) This doesn't work in constant time but O(n) time.
    b) You can have the same complexity with a Python list, too.

    Cheers!

    Uli
    Ulrich Eckhardt, Dec 19, 2010
    #8
  9. Am 19.12.2010 07:18, schrieb Dmitry Groshev:
    > Is there any way to use a true lists (with O(c) insertion/deletion and
    > O(n) search) in python? For example, to make things like reversing
    > part of the list with a constant time.

    reversing part of the list could also be interpreted as reading it
    in the opposite direction from a given starting point to a known end.

    Perhaps you want to look into the array module, but you
    have to sacrifice the typelessness of a true python list:
    it can only contain numerical data (also char, byte).

    But don't know the timing pattern of array objects, only that they are *way*
    faster then lists.
    Stefan Sonnenberg-Carstens, Dec 19, 2010
    #9
  10. Dmitry Groshev

    John Nagle Guest

    On 12/18/2010 10:41 PM, Dmitry Groshev wrote:
    > On Dec 19, 9:18 am, Dmitry Groshev<> wrote:
    >> Is there any way to use a true lists (with O(c) insertion/deletion and
    >> O(n) search) in python? For example, to make things like reversing
    >> part of the list with a constant time.

    >
    > I forgot to mention that I mean *fast* lists. It's trivial to do
    > things like this with objects, but it will be sloooow.


    Try using objects with "slots". If you have a large number
    of small objects, and are doing many very simple operations on
    them, the attribute lookup time will dominate.

    A nice example of when you might need real lists is for the
    Traveling Salesman Problem. The usual way to solve that is:

    1. Link up all the nodes in a random order.
    2. Pick two links at random, and cut the list into three lists.
    3. Try all possible ways to arrange the three lists
    (there are 6*4*2/2 = 24 ways) and compute the
    path length for each.
    4. Pick the shortest path.
    5. Repeat steps 2-5 until no improvement is observed for
    a while.

    The cut-and-reassemble steps are constant time for real lists, but
    require expensive copying with arrays.

    If you're really worried about low-level performance issues,
    CPython is probably the wrong tool for the job.

    John Nagle
    John Nagle, Dec 19, 2010
    #10
  11. Dmitry Groshev

    TomF Guest

    On 2010-12-18 22:18:07 -0800, Dmitry Groshev said:

    > Is there any way to use a true lists (with O(c) insertion/deletion and
    > O(n) search) in python? For example, to make things like reversing
    > part of the list with a constant time.


    I assume you mean a C extension that implements doubly linked lists
    (reversing part of a list is only constant time if the list is
    doubly-linked). I'm not aware of one.

    A longer answer is that many high level languages (Python, Perl, Ruby)
    don't bother implementing simple linked lists because they're not very
    useful. Instead they use hybrid data structures that can operate as
    lists and arrays with flexibility and acceptable costs. And if you
    need greater speed you usually go to special purpose arrays (for
    constant time access) rather than lists.

    -Tom
    TomF, Dec 19, 2010
    #11
  12. Dmitry Groshev

    Ian Kelly Guest

    On Sun, Dec 19, 2010 at 5:59 AM, Vito 'ZeD' De Tullio
    <> wrote:
    > Steven D'Aprano wrote:
    >
    >> I can't see any way to go from this linked list:
    >>
    >> node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> node7
    >>
    >> to this:
    >>
    >> node1 -> node6 -> node5 -> node4 -> node3 -> node2 -> node7
    >>
    >> in constant time. You have to touch each of the nodes being reversed.

    >
    > very crude example: [SNIPPED]



    That reverses the whole list. How does it help with reversing only
    part of the list, as in Steven's example?
    Ian Kelly, Dec 19, 2010
    #12
  13. On Sun, 19 Dec 2010 20:45:55 +0100
    Stefan Sonnenberg-Carstens <> wrote:
    > Am 19.12.2010 07:18, schrieb Dmitry Groshev:
    > > Is there any way to use a true lists (with O(c) insertion/deletion and
    > > O(n) search) in python? For example, to make things like reversing
    > > part of the list with a constant time.

    > reversing part of the list could also be interpreted as reading it
    > in the opposite direction from a given starting point to a known end.
    >
    > Perhaps you want to look into the array module, but you
    > have to sacrifice the typelessness of a true python list:
    > it can only contain numerical data (also char, byte).
    >
    > But don't know the timing pattern of array objects, only that they are *way*
    > faster then lists.


    Why do you say there're much faster?

    Regards

    Antoine.
    Antoine Pitrou, Dec 19, 2010
    #13
  14. Duncan Booth <> writes:

    > I guess you might be able to do it with a double-linked list provided
    > that when traversing the list you always keep two nodes around to
    > determine the direction. e.g. instead of asking for node6.nextNode() you
    > ask for node6.nextNode(previous=node1) and then the code can return
    > whichever sibling wasn't given. That would make reversal (assuming you
    > have both nodes) O(1), but would make traversing the list slower.


    There used to be a trick to implement doubly linked lists with the same
    memory footprint as singly linked ones: instead of each node storing two
    pointers (one to the next node, one to the previous one), you just store
    one value:

    (previous node) xor (next node)

    This means that when traversing the list, you need to always remember
    which node you are coming from. But it also makes these lists
    kind of symmetrical.

    --
    Arnaud
    Arnaud Delobelle, Dec 21, 2010
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Siemel Naran

    Does true ^ true return false?

    Siemel Naran, Jun 17, 2004, in forum: C++
    Replies:
    19
    Views:
    650
    Chris Theis
    Jun 18, 2004
  2. Chip
    Replies:
    6
    Views:
    2,616
    E. Robert Tisdale
    Jan 8, 2005
  3. Andy Leszczynski
    Replies:
    4
    Views:
    314
    Erik Max Francis
    Oct 13, 2005
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. bdb112
    Replies:
    45
    Views:
    1,316
    jazbees
    Apr 29, 2009
Loading...

Share This Page