Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #65565 > unrolled thread

Question about `list.insert`

Back to article view | Back to comp.lang.python

Contents

  Question about `list.insert` cool-RR <ram.rachum@gmail.com> - 2014-02-06 15:59 -0800
    Re: Question about `list.insert` Terry Reedy <tjreedy@udel.edu> - 2014-02-06 19:40 -0500
    Re: Question about `list.insert` MRAB <python@mrabarnett.plus.com> - 2014-02-07 00:42 +0000
    Re: Question about `list.insert` Terry Reedy <tjreedy@udel.edu> - 2014-02-06 21:48 -0500
    Re:Question about `list.insert` Dave Angel <davea@davea.name> - 2014-02-06 21:54 -0500
      Re: Question about `list.insert` Roy Smith <roy@panix.com> - 2014-02-06 22:00 -0500
        Re: Question about `list.insert` Rustom Mody <rustompmody@gmail.com> - 2014-02-06 19:08 -0800
        Re: Question about `list.insert` Tim Chase <python.list@tim.thechases.com> - 2014-02-06 21:11 -0600
          Re: Question about `list.insert` Roy Smith <roy@panix.com> - 2014-02-06 22:12 -0500
            Re: Question about `list.insert` Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-07 17:18 +1300
        Re: Question about `list.insert` Chris Angelico <rosuav@gmail.com> - 2014-02-07 14:14 +1100
        Re: Question about `list.insert` Chris Angelico <rosuav@gmail.com> - 2014-02-07 14:20 +1100
          Re: Question about `list.insert` Rustom Mody <rustompmody@gmail.com> - 2014-02-06 19:29 -0800
            Re: Question about `list.insert` Chris Angelico <rosuav@gmail.com> - 2014-02-07 14:45 +1100
        Re: Question about `list.insert` Asaf Las <roegltd@gmail.com> - 2014-02-06 19:28 -0800
    Re: Question about `list.insert` Dan Stromberg <drsalists@gmail.com> - 2014-02-06 20:52 -0800
      Re: Question about `list.insert` Asaf Las <roegltd@gmail.com> - 2014-02-06 21:18 -0800
    Re: Question about `list.insert` Peter Otten <__peter__@web.de> - 2014-02-07 09:25 +0100

#65565 — Question about `list.insert`

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?


Thanks,
Ram.

[toc] | [next] | [standalone]

#65567

On 2/6/2014 6:59 PM, cool-RR wrote:
> 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.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#65568

On 2014-02-06 23:59, cool-RR wrote:
> 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.

[toc] | [prev] | [next] | [standalone]

#65574

On 2/6/2014 7:42 PM, MRAB wrote:
> On 2014-02-06 23:59, cool-RR wrote:
>> 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.

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

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#65575

 cool-RR <ram.rachum@gmail.com> Wrote in message:
> 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.

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#65576

In article <mailman.6471.1391741496.18130.python-list@python.org>,
 Dave Angel <davea@davea.name> wrote:

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

[toc] | [prev] | [next] | [standalone]

#65578

On Friday, February 7, 2014 8:30:56 AM UTC+5:30, Roy Smith wrote:
>  Dave Angel wrote:
> 
> > 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?

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

[toc] | [prev] | [next] | [standalone]

#65579

On 2014-02-06 22:00, Roy Smith wrote:
> > 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?

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

-tkc

[toc] | [prev] | [next] | [standalone]

#65580

In article <mailman.6472.1391742656.18130.python-list@python.org>,
 Tim Chase <python.list@tim.thechases.com> wrote:

> On 2014-02-06 22:00, Roy Smith wrote:
> > > 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?
> 
> Pish...there's always O(0) which is achieved by *not* performing some
> unneeded operation ;-)

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

[toc] | [prev] | [next] | [standalone]

#65589

Roy Smith wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#65581

On Fri, Feb 7, 2014 at 2:00 PM, Roy Smith <roy@panix.com> wrote:
> In article <mailman.6471.1391741496.18130.python-list@python.org>,
>  Dave Angel <davea@davea.name> wrote:
>
>> 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?

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

[toc] | [prev] | [next] | [standalone]

#65582

On Fri, Feb 7, 2014 at 2:11 PM, Tim Chase <python.list@tim.thechases.com> wrote:
> On 2014-02-06 22:00, Roy Smith wrote:
>> > 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?
>
> 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

[toc] | [prev] | [next] | [standalone]

#65585

On Friday, February 7, 2014 8:44:43 AM UTC+5:30, Chris Angelico wrote:
> On Fri, Feb 7, 2014 at 2:00 PM, Roy Smith  wrote:
> >  Dave Angel wrote:
> >> 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?

> 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

[toc] | [prev] | [next] | [standalone]

#65586

On Fri, Feb 7, 2014 at 2:29 PM, Rustom Mody <rustompmody@gmail.com> wrote:
> On Friday, February 7, 2014 8:44:43 AM UTC+5:30, Chris Angelico wrote:
>> On Fri, Feb 7, 2014 at 2:00 PM, Roy Smith  wrote:
>> >  Dave Angel wrote:
>> >> 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?
>
>> 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

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

[toc] | [prev] | [next] | [standalone]

#65584

On Friday, February 7, 2014 5:00:56 AM UTC+2, Roy Smith wrote:
> In article <mai...t@python.org>,
> 
>  Dave Angel wrote:
> > 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?

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)." 

[toc] | [prev] | [next] | [standalone]

#65592

On Thu, Feb 6, 2014 at 3:59 PM, cool-RR <ram.rachum@gmail.com> wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#65595

On Friday, February 7, 2014 6:52:24 AM UTC+2, Dan Stromberg wrote:
> On Thu, Feb 6, 2014 at 3:59 PM, cool-RR <ra...@gmail.com> wrote:
> 
> 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

[toc] | [prev] | [next] | [standalone]

#65601

cool-RR wrote:

> 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web