The REALLY bad thing about Python lists ..

[rturpin at my-deja.com]

I wrote:
>> Creating an array by appending at the end is
>> linear in the length of the array.

In article <m3zoptnday.fsf at atrus.jesus.cam.ac.uk>,
  Michael Hudson <mwh21 at cam.ac.uk> wrote:
> Only if you know the length of the array in advance,
> surely?  I know why this doesn't really apply to Python,
> but I was being theoretical.

I'm guessing you're worried about memory management. The
cost of that is highly dependent on both (a) the language
processor, and (b) the state of the program when the
algorithm is run. Starting with the first, I don't know
how much memory Python requests for an array when it gets
longer. If it requests some constant amount, then indeed,
the array will be copied a number of times proportional
to its length, and each copy is O(n), so the whole thing
becomes O(n^2). I suspect, though, that Python is smart,
and doubles the length of the array each time it exceeds
its current allocation. In this case, the cost of copies
is O(n). Since my empirical runs show O(n) behavior, I
would bet money that Python is smart about this.

But what about the allocation algorithm itself? For many,
it is O(1) if the program does no deallocations. In general,
it can get worse, though usually no worse than logarithmic,
or less, over a long series allocates and frees. Generally,
you don't credit to an algorithm the costs associated with
fragmented memory from previous work.

Of course, memory allocation eventually fails, so in real
life, creating an array of length n requires O(1) time and
fails in almost all (theoretical) cases, though almost no
real-life cases.

Dead-horse-beating'ly yrs,
Russell


Sent via Deja.com http://www.deja.com/
Before you buy.