[SciPy-user] How to start with SciPy and NumPy
David Cournapeau
cournape at gmail.com
Mon Jan 26 11:34:21 EST 2009
On Tue, Jan 27, 2009 at 1:16 AM, Sturla Molden <sturla at molden.no> wrote:
>> On Tue, Jan 27, 2009 at 12:32 AM, alex <argriffi at 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