Speed revisited

[John Machin]

Andrea Griffini wrote:
> On 9 Jan 2005 12:39:32 -0800, "John Machin" <sjmachin at lexicon.net>
> wrote:
>
> >Tip 1: Once you have data in memory, don't move it, move a pointer
or
> >index over the parts you are inspecting.
> >
> >Tip 2: Develop an abhorrence of deleting data.
>
> I've to admit that I also found strange that deleting the
> first element from a list is not O(1) in python. My wild
> guess was that the extra addition and normalization required
> to have insertion in amortized O(1) and deletion in O(1) at
> both ends of a random access sequence was going to have
> basically a negligible cost for normal access (given the
> overhead that is already present in python).
>
> But I'm sure this idea is too obvious for not having been
> proposed, and so there must reasons for refusing it
> (may be the cost to pay for random access once measured was
> found being far from negligible, or that the extra memory
> overhead per list - one int for remembering where the live
> data starts - was also going to be a problem).
>

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]

<humour>
Suggested projects for you, in increasing order of difficulty:

1. Grab the source code (listobject.c) and report back on how you would
implement your proposal.
2. Convince folk that your implementation is faster and more robust and
has beter internal documentation than anything the timbot could ever
write.
3. Write a PEP that didn't cause a flamewar.
</humour>