«

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.

On Dec 19, 9:18*am, Dmitry Groshev <lambdadmi...@gmail.com> 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 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/colle...lections.deque
[1] http://code.activestate.com/recipes/...inked-list-vs-
list/

--
By ZeD

On Dec 19, 9:48*am, Vito 'ZeD' De Tullio <zak.mc.kra...@libero.it>
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 <> 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).

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

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

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.

On 12/18/2010 10:41 PM, Dmitry Groshev wrote:
> On Dec 19, 9:18 am, Dmitry Groshev<lambdadmi...@gmail.com> 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