bulba at bulba.com
Mon Jan 10 17:52:42 CET 2005
On Sun, 09 Jan 2005 22:51:47 GMT, Andrea Griffini <agriff at tin.it>
>>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
>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='spam' when L previously were, say, 's', not have the
O(n) cost, if a list in Python is just an array containing the
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.
More information about the Python-list