True lists in python?

D

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.
 
D

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.

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

Vito 'ZeD' De Tullio

Dmitry 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.

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/
 
D

Dmitry Groshev

Dmitry 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.

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/

-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.
 
P

Paul Rubin

Dmitry Groshev said:
-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).
 
S

Steven D'Aprano

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.
 
V

Vito 'ZeD' De Tullio

Steven said:
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()
 
U

Ulrich Eckhardt

Dmitry said:
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
 
S

Stefan Sonnenberg-Carstens

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.
 
J

John Nagle

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
 
T

TomF

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
 
I

Ian Kelly

Steven said:
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?
 
A

Antoine Pitrou

Am 19.12.2010 07:18, schrieb Dmitry Groshev:
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.
 
A

Arnaud Delobelle

Duncan Booth said:
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top