On 26/01/2010 00:28, Christian Heimes wrote:
Michael Foord wrote:
How great is the complication? Making list.pop(0) efficient sounds like
a worthy goal, particularly given that the reason you don't use it is
because you *know* it is inefficient (so the fact that you don't use it
isn't evidence that it isn't wanted - merely evidence that you had to
work around the known inefficiency).
The implementation must be changed in at least four places:
* The PyListObject struct gets an additional pointer that stores a
reference to the head. I would keep the head (element 0) of the list in
**ob_item and the reference to the malloc()ed array in a new pointer
*ob_allocated.
* PyList_New() stores the pointer to the allocated memory in
op->ob_allocated and sets op->ob_item = op->ob_allocated
* listpop() moves the op->ob_item pointer by one for the special case
of pop(0)
* list_resize() should occasionally compact the free space before the
head with memcpy() if it gets too large.
listinsert() could be optimized for 0 if the list has some free space in
front of the header, too.
I favor this approach over an integer offset because doesn't change the
semantic of ob_item.
Christian
Well, on the face of it this doesn't sound like a huge increase in
complexity. Not that I'm qualified to judge.
Michael
--
http://www.ironpythoninaction.com/
http://www.voidspace.org.uk/blog
READ CAREFULLY. By accepting and reading this email you agree, on behalf of
your employer, to release me from all obligations and waivers arising from any
and all NON-NEGOTIATED agreements, licenses, terms-of-service, shrinkwrap,
clickwrap, browsewrap, confidentiality, non-disclosure, non-compete and
acceptable use policies (”BOGUS AGREEMENTS”) that I have entered into with your
employer, its partners, licensors, agents and assigns, in perpetuity, without
prejudice to my ongoing rights and privileges. You further represent that you
have the authority to release me from any BOGUS AGREEMENTS on behalf of your
employer.
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
