Question about `list.insert`

[cool-RR]

Hi,

I'm curious. If I append an item to a list from the left using `list.insert`, will Python always move the entire list one item to the right (which canbe super-slow) or will it check first to see whether it can just allocate more memory to the left of the list and put the item there, saving a lot ofresources?


Thanks,
Ram.

 

[Terry Reedy]

Hi,

I'm curious. If I append an item to a list from the left using
`list.insert`, will Python always move the entire list one item to
the right (which can be super-slow) or will it check first to see
whether it can just allocate more memory to the left of the list and
put the item there, saving a lot of resources?

"It depends on the implementation"

Assume O(n), which I am sure it is for CPython, but easy enough to check.

 

[MRAB]

Hi,

I'm curious. If I append an item to a list from the left using
`list.insert`, will Python always move the entire list one item to
the right (which can be super-slow) or will it check first to see
whether it can just allocate more memory to the left of the list and
put the item there, saving a lot of resources?

If it needs more space it resizes. It then moves the items.

 

[Terry Reedy]

If it needs more space it resizes. It then moves the items.

The OP apparently knows that there is usually extra space at the right
(end), so that reallocation is usually not needed. He wanted to know
whether extra space is also kept at the left (beginning) to make left
appends as efficient as right appends. This has been proposed and the
answer was to use collections.deque if it really matters. CPython lists
are asymmetric re-sizable stacks

 

[Dave Angel]

Hi,

I'm curious. If I append an item to a list from the left using `list.insert`, will Python always move the entire list one item to the right (which can be super-slow) or will it check first to see whether it can just allocate more memory to the left of the list and put the item there, saving a lot of resources?

Excellent question. list does not promise better than O (1)
behavior, and CPython in particular will copy, I'm pretty
sure.

However that's exactly what collections.deque is for.

 

[Roy Smith]

list does not promise better than O(1) behavior

I'm not aware of any list implementations, in any language, that
promises better than O(1) behavior for any operations. Perhaps there is
O(j), where you just imagine the operation was performed?

 

[Rustom Mody]

I'm not aware of any list implementations, in any language, that
promises better than O(1) behavior for any operations. Perhaps there is
O(j), where you just imagine the operation was performed?

I believe Oracle has such a product on offer
The price too is by imagination

 

[Tim Chase]

I'm not aware of any list implementations, in any language, that
promises better than O(1) behavior for any operations. Perhaps
there is O(j), where you just imagine the operation was performed?

Pish...there's always O(0) which is achieved by *not* performing some
unneeded operation ;-)

-tkc

 

[Roy Smith]

Pish...there's always O(0) which is achieved by *not* performing some
unneeded operation ;-)

O(-1). In Soviet Russia, operation performs you!

 

[Chris Angelico]

I'm not aware of any list implementations, in any language, that
promises better than O(1) behavior for any operations. Perhaps there is
O(j), where you just imagine the operation was performed?

I have a printer that executes in O(1/N) time, where N is the number
of marbles the sysadmin (me!) has lost. The less sanity I have, the
more printouts it produces. And the less printouts it produces, the
more marbles I lose trying to figure out WHY? WHY? WHY?!?

Okay, I'm done ranting about Windows and 1990s accounting packages and
modern PostScript printers.

ChrisA

 

[Chris Angelico]

Pish...there's always O(0) which is achieved by *not* performing some
unneeded operation ;-)

-tkc

Ooh! Ooh! I got it!

class fast_list(list):
def append(self,obj,randrange=random.randrange):
if len(self) and randrange(len(self)): return
return super().append(obj)

Repeated appends to this list are amortized O(0)!

ChrisA

 

[Asaf Las]

I'm not aware of any list implementations, in any language, that
promises better than O(1) behavior for any operations. Perhaps there is
O(j), where you just imagine the operation was performed?

Archimedes once said "Give me whereon to stand and I will move the earth"
he said that for lists, specifically he meant "give me enough RAM and
list will perform O(1)."

 

[Rustom Mody]

I have a printer that executes in O(1/N) time, where N is the number
of marbles the sysadmin (me!) has lost. The less sanity I have, the
more printouts it produces. And the less printouts it produces, the
more marbles I lose trying to figure out WHY? WHY? WHY?!?

Heh! Nice to know I have company!

Thought I was the only one who lost hair at the printer's
free-paper-munificience

 

[Chris Angelico]

Heh! Nice to know I have company!

Thought I was the only one who lost hair at the printer's
free-paper-munificience

See, here's the deal. I have a nice, modern, CUPS-based printer. It
supports all the modern protocols (IPP, JetDirect, whatever), and when
I point one of my Linux boxes in its direction and say "Print", a
sheet of paper comes out in fairly short order. Nice, right? Okay, now
let's mix in the problem ingredients.

We have an ancient accounting package, supporting a rather old and
winding-down business. It's not worth upgrading to a newer version of
the program (that costs money), and certainly not worth migrating to a
completely different program (that takes time), because the business
just isn't operating at that level any more. It's a Windows 16-bit
application.

The physical hardware is decently modern, and is running Debian Jessie
(the latest, not even stable yet, because I wanted something else
relating to scanning - that's a separate point). Debian is running
VirtualBox, and inside the VM is running OS/2 (eComStation). OS/2 will
run the old accounting package in a Win-OS/2 session.

Now, OS/2 will talk to the printer. I can fire up DeScribe Word
Processor, type in some text, hit Print, and a sheet of paper comes
out with a representation of that text. The recent versions of OS/2
are quite good at that. But Windows? Windows? Oh no. It won't be that
courteous. No, it claims to have printed the document, and everything
I can see suggests that the data has passed through on its way to the
printer, but no paper comes out. My best guess is that there's some
flaw in the PostScript engine in Windows, because I can generate
output successfully by a complex dance involving freezing the
printer's output, printing from Windows, printing an unrelated
document (anything at all) from OS/2, and then releasing all the
printed data at once.

Current suggestions awaiting experimentation including slaughtering a
black goat at midnight, waving a rubber chicken, and throwing salt
over my shoulder in the direction of the full moon.

ChrisA

 

[Gregory Ewing]

O(-1). In Soviet Russia, operation performs you!

It's rumoured that the PSU is developing a time
machine module that can achieve O(-n), but

 

[Dan Stromberg]

Hi,

I'm curious. If I append an item to a list from the left using `list.insert`, will Python always move the entire list one item to the right (which can be super-slow) or will it check first to see whether it can just allocate more memory to the left of the list and put the item there, saving a lot of resources?

I'm pretty sure it'll slide all the existing elements right one
position, and add at the leftmost position just opened up - assuming
you're inserting at position 0.

As was already mentioned, collections.deque is good for this sort of
thing. It's implemented as a fancy doubly-linked list. Or rather, a
doubly-linked list of smallish arrays/lists.

For a singly-linked list:
http://stackoverflow.com/questions/280243/python-linked-list
http://stromberg.dnsalias.org/~strombrg/linked-list/

HTH

 

[Asaf Las]

I'm pretty sure it'll slide all the existing elements right one
position, and add at the leftmost position just opened up - assuming
you're inserting at position 0.

As was already mentioned, collections.deque is good for this sort of
thing. It's implemented as a fancy doubly-linked list. Or rather, a
doubly-linked list of smallish arrays/lists.
For a singly-linked list:
http://stackoverflow.com/questions/280243/python-linked-list
http://stromberg.dnsalias.org/~strombrg/linked-list/

HTH

the Py list is just 2 members (as declared in corresponding header)
structure where only one double pointer serves addressing towards most
probably dynamically allocated array of pointers towards python
objects. so adding could expensive as it should copy all pointers
in array into new bigger one during expanding as array needs to be
contiguous. so it looks more array than list. but i could be wrong in
my conclusion.

/Asaf

 

[Peter Otten]

I'm curious. If I append an item to a list from the left using
`list.insert`, will Python always move the entire list one item to the
right (which can be super-slow) or will it check first to see whether it
can just allocate more memory to the left of the list and put the item
there, saving a lot of resources?

Let's see:

$ python3.4 -m timeit -s 'a = [None]' 'a.insert(0, None); del a[0]'
1000000 loops, best of 3: 0.596 usec per loop
$ python3.4 -m timeit -s 'a = [None]*1000' 'a.insert(0, None); del a[0]'
100000 loops, best of 3: 2.59 usec per loop
$ python3.4 -m timeit -s 'a = [None]*10000' 'a.insert(0, None); del a[0]'
10000 loops, best of 3: 24.7 usec per loop
$ python3.4 -m timeit -s 'a = [None]*100000' 'a.insert(0, None); del a[0]'
1000 loops, best of 3: 508 usec per loop
$ python3.4 -m timeit -s 'a = [None]*1000000' 'a.insert(0, None); del a[0]'
100 loops, best of 3: 7.61 msec per loop

$ python3.4 -m timeit -s 'from collections import deque; a =
deque([None]*1000000)' 'a.appendleft(None); a.popleft()'
1000000 loops, best of 3: 0.263 usec per loop