On 27Jan2010 23:08, Nick Coghlan <ncogh...@gmail.com> wrote: | Cameron Simpson wrote: | > The proposed change to make pop(0) O(1) involves adding a base offset | > to the internal list implementation. Doesn't that incur a (small) | > overhead to _every_ list operation? Doesn't that weaken "list" as the | > "as efficient as possible" implementation of choice for "array"-like | > things? | | No, the implementation is smarter than that. The existing pointer in the | PyList_* structure will continue to point to the first element of the | list while an extra pointer is added that points to the beginning of the | allocated memory. The difference between the two memory addresses will | determine the number of "orphan" pointer slots that exist at the | beginning of the list.
Mmmm, that is smarter. Nice. | Only operations that change the length of the list will be slowed down | at all, since they will need to take the orphans into account when | deciding whether or not to resize the allocated memory. Nice again. | The big practical concern is actually the memory cost of adding yet | another pointer (potentially 8 bytes of data) to every list object, even | empty ones. Um, yes. How big is a an empty list already? -- Cameron Simpson <c...@zip.com.au> DoD#743 http://www.cskk.ezoshosting.com/cs/ Who is the happier man, he who has braved the storm of life and lived, or he who has stayed securely on shore and merely existed? - Hunter S. Thompson, age seventeen _______________________________________________ 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
