Speed revisited

[Bulba!]

On Sun, 09 Jan 2005 22:51:47 GMT, Andrea Griffini <agriff at tin.it>
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).

Smth similar happened here - I _assumed_ that since lists in 
Python can hold arbitrary objects, the low level C implementation 
was smth like "array" of pointers to those objects (or offsets of
those objects stored elsewhere). 

If so, deleting an element from a list would merely be deleting a
pointer (or zeroing particular offset to get this object "released"),
which would have negligible cost. 

I've read that Python's memory management technique
is 'reference counting' - it would seem only logical that 
the list is an array (or linked list or linked list of arrays
maybe, as it can grow in size arbitrarily) of such 
references.

>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).

But either the book-keeping of offsets or pointers or references 
to list elements has to be done by Python interpreter, oops,
VIRTUAL MACHINE, somehow anyway. 

I don't see why should deleting element from a list be O(n), while
saying L[0]='spam' when L[0] previously were, say, 's', not have the
O(n) cost, if a list in Python is just an array containing the 
objects itself?

Why should JUST deletion have an O(n) cost?



--
I have come to kick ass, chew bubble gum and do the following:

from __future__ import py3k

And it doesn't work.