On Sun, 09 Jan 2005 22:51:47 GMT, Andrea Griffini <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
