Surprising (for me) benchmark results...

[Courageous]

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

Well, yes, technically.

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

Nothing, really. I keep pretending Python doesn't do that
silly constant allocation thing. :-)

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

Does not show practical advantages with regards to what?

>reallocation still costs:-) -- but that, of course, is not
>a very relevant point regarding big-O issues.

I'm sure that one of the reasons that this hasn't been addressed
is that it does matter for routine values of n.

C//