Speed revisited

[Andrea Griffini]

On 9 Jan 2005 16:03:34 -0800, "John Machin" <sjmachin at lexicon.net>
wrote:

>My wild guess: Not a common use case. Double-ended queue is a special
>purpose structure.
>
>Note that the OP could have implemented the 3-tape update simulation
>efficiently by reading backwards i.e. del alist[-1]

Note that I was just trying to say that it's not obvious
that list insertion at the first element is O(n); because
there are "less naive" implementation that can do better.
For a lower level language O(n) is probably what 99% of
programmers indeed would expect, but for a VHLL like
python this is IMO not the case.

I remember when a few years ago working with PowerBuilder
(a RAD environment for client-server applications) to my
great surprise I found that even adding at the end of a
list was O(n) in that language... where is the line ?
After all "smart" reallocation is still a tradeoff (extra
"wasted" space traded for diminshed copying) ...

Andrea