[SciPy-user] How to start with SciPy and NumPy
Mon Jan 26 09:32:48 CST 2009
David Cournapeau wrote:
> On Mon, Jan 26, 2009 at 11:52 PM, Sturla Molden <firstname.lastname@example.org> wrote:
>>> Sturla Molden wrote:
>>> This is independent of the list implementation, isn't it ? I am quite
>>> curious to understand how you could get O(1) complexity for a "growable"
>>> container: if you don't know in advance the number of items, and you add
>>> O(N) items, how come you can get O(1) complexity ?
>> Each time the array is re-sized, you add in some extra empty slots. Make
>> sure the number of extra slots is proportional to the size of the array.
> So this is the well known method of over allocating when you need to
> grow, right ? This is not constant time, and depends on the number of
> items you are adding I think (sublinearly, but still)
I think you guys are talking about different N. If N is the number of
items already in the list, then adding a single item to the list could
be O(N) if you use arrays to represent lists and you do not
over-allocate when you need to grow. By over-allocating when you need
to grow, you can get amortized O(1) for the operation of adding a single
element (not N elements) to the list. Python apparently uses this
latter method. I guess the discussion started on the topic of the
difference between arrays and lists, and that Python's 'list' has some
properties of a classical 'array' (fast random access) and some of a
classical 'list' (fast amortized append).
More information about the SciPy-user