[SciPy-user] How to start with SciPy and NumPy

David Cournapeau cournape@gmail....
Mon Jan 26 10:34:21 CST 2009


On Tue, Jan 27, 2009 at 1:16 AM, Sturla Molden <sturla@molden.no> wrote:
>> On Tue, Jan 27, 2009 at 12:32 AM, alex <argriffi@ncsu.edu> wrote:
>
>> I meant that adding N items to a list requires O(log(N)) malloc when
>> using over allocation (double the size at ever allocation). I am not
>> sure to understand how the number of items already in the list would
>> influence the complexity of growing, at least when complexity =
>> counting the number of malloc.
>
> Because the items already in the list has to be copied for every malloc.
> The O(log(N)) mallocs do not have O(1) complexity. The complexity is not
> counting the number of mallocs.

Ok - I did not understand what amortized cost meant.

>
> By the way, a Python list does not double in size on each allocation. It
> has a less greedy growth pattern.

Yes - but then python does not use malloc directly either anyway :)

David


More information about the SciPy-user mailing list