addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscrossdots-three-verticaleditemptyheartexporteye-with-lineeyefacebookfolderfullheartglobegmailgooglegroupshelp-with-circleimageimagesinstagramFill 1linklocation-pinm-swarmSearchmailmessagesminusmoremuplabelShape 3 + Rectangle 1ShapeoutlookpersonJoin Group on CardStartprice-ribbonShapeShapeShapeShapeImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruserwarningyahoo

Re: [nycpython] question about list.insert()

From: Aaron W.
Sent on: Monday, August 16, 2010 4:05 PM
I'm pretty sure list.insert is not linear if you insert near the end of the list. 
I think lists overallocate a percentage
of space to allow n inserts near the end to have n log n
asymptotic performance.  In fact
looking at the top of listobject.c in Python 2.7 I see:

        /* This over-allocates proportional to the list size, making room                                                                                  
         * for additional growth.  The over-allocation is mild, but is                                                                                     
         * enough to give linear-time amortized behavior over a long                                                                                       
         * sequence of appends() in the presence of a poorly-performing                                                                                    
         * system realloc().                                                                                                                               
         * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...                                                                                

On the other hand n calls to list.insert(0,x) has n**2 performance for n inserts because
all the elements in the internal array all have to be shifted for each insert.

So the moral is: If you need to add stuff to the front then build the list backwards
and reverse it.  If you need to add stuff randomly, then you probably want to think
about using a dictionary somehow and then linearize it into a list later.

In theory Lisp cons cells are better for this kind of thing: in practice the
memory fragmentation kills you and python-style list/arrays are better
for what you usually need to do.

Sorry, couldn't keep my mouth shut.  -- Aaron Watters


--- On Sat, 8/14/10, Jordan P <[address removed]> wrote:

From: Jordan P <[address removed]>
Subject: Re: [nycpython] question about list.insert()
To: [address removed]
Date: Saturday, August 14, 2010, 1:22 PM

Holy inefficiency, Batman! I had no idea that list.insert was linear!

Sign up

Meetup members, Log in