The REALLY bad thing about Python lists ..

[rturpin at my-deja.com]

In article <391ED8C9.BC2BAE8D at san.rr.com>,
  Courageous <jkraska1 at san.rr.com> wrote:
> Are you talking about some kind of strategy where
> you allocate a maxsize and then put the used memory
> in the middle?

Yep. You wouldn't have to do this on first allocation,
but could do so only on first prepend that runs over
the start of the buffer, on the assumption if it
happens once, it might happen again. Then you get
efficiency in both directions. The object pointer
still points to the zero-th element, so indexing is
no different. Below the zero-th element, you have
pointers to both ends of the buffer. Prepending
would be a BIT more expensive than appending, since
you have to move these pointers. But you don't have
to move the entire vector each time you prepend,
which seems to be what is now done. Creating vectors
of length n by prepending elements one at a time is
now an n^2 operation!

Russell


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