Surprising (for me) benchmark results...

[Alex Martelli]

"Courageous" <jkraska1 at san.rr.com> wrote in message
news:jr9vet8v8i1qinl1tkhjitkppksoeuqo7h at 4ax.com...
>
>
> >> list.append() appends items to a dynamic array in O(1)+k
> >> constant amortized time. It does this by using a liberal preallocation
> >> strategy, and leaving empty slots into which new elements can
> >> be placed. The occasional realloc() amortizes away quite readily.
>
> >Are you sure?
>
> Yes.

I don't understand where this certainty comes from.  Constant
amortized time for append-at-end requires geometrical growth
in the capacity successively preallocated, doesn't it?  And
Python doesn't do that -- it resizes linearly instead, by 10
items per resize at first (when the list is still small), then
by 100 per resize.  So, amortization can't happen for unbounded
numbers of append-at-end -- the O() behavior of each such append
sure looks O(N) to me, with one reallocation [O(N)] every 100
appends [and constants don't matter in O() notation].

So, what _am_ I missing...?  I'm using listobject.c as my
reference, by the way.


> If we weren't supposed to be talking about list.append(),
> sorry. :-)

I _am_ taking about .append().  From past experiments, I have
noticed that using a guaranteed-amortized-O(1) container does
not shew _practical_ advantages [C++'s std::vector<> _does_
have such an O()-guarantee, so it's easy to test -- or else,
tweaking the roundupsize function and/or macros ROUNDUP and
NRESIZE, all in listobject.c, makes it easy to play with
this].  But big-O-notation is about performance behavior
limits for N growing without bounds, isn't it...?

I _do_ know that "pre-allocating" shows measurable performance
gains in many practical cases, just like .reserve() does with
a C++'s std::vector (no matter that Python's lists and C++'s
vectors have different big-O performance guarantees, each
reallocation still costs:-) -- but that, of course, is not
a very relevant point regarding big-O issues.


Alex