Home Original page

how to delete multiple elements from a list

Alex Martelli aleaxit at yahoo.com
Thu Nov 16 06:00:09 EST 2000 
"Rainer Deyke" <root at rainerdeyke.com> wrote in message
news:PQFQ5.200688$g6.91773599 at news2.rdc2.tx.home.com...
> "Alex Martelli" <aleaxit at yahoo.com> wrote in message
> news:8uuunt015s3 at news1.newsguy.com...
> > The reallocation costs are amortized by rounding up the
> > size (number of items) to a multiple of 10 (of 100, for
> > large lists), but that doesn't change the O(N) cost of
> > element insertions and deletions (it does change the
> > amortized costs by a constant factor of 10, or 100).
>
> I'm curious.  Why multiples of 10 (or 100), and not powers of 2 (or
> similar)?  The latter has much better amortized performance for huge
lists,
> and never wastes more than half of its space.

Exponential growth (by any exponent > 1) has O(1) amortized
time for append (and will not waste more than a specified
fraction of space); a C++ std::vector, for example, must in
practice use exponential growth since the standard specifies
such a performance constraint.

I don't know why Python doesn't choose to use such a scheme
for its lists.  I guess it's felt that potentially wasting
megabytes for a million-elements list is unacceptable, and
the actual performance gain from moving to amortized O(1)
not that big a deal (but, I *am* just-guessing here; I am
not privy to the motivations of GvR and friends!).

It's easy to play with this setting if you want to locally
rebuild Python from sources -- see static function
roundupsize (and macro ROUNDUP) at the very start of source
file Objects/listobject.c.  You can thus easily see if
it makes any difference to your programs, and in what
direction...


Alex
More information about the Python-list mailing list