On Jan 22, 12:40 pm, Christian Heimes <li...@cheimes.de> wrote: > Steve Howell wrote: > > Is that really true in CPython? It seems like you could advance the > > pointer instead of shifting all the elements. It would create some > > nuances with respect to reclaiming the memory, but it seems like an > > easy way to make lists perform better under a pretty reasonable use > > case. > > > Does anybody know off the top of their head if the "have-to-be-shifted- > > by-one" warning is actually valid? > > Why do you think the documentation has such obvious errors?
I wasn't making any assumptions, hence the question mark. The Python docs are very good, but even the best of projects make advances that aren't reflected in the docs. > CPython's list type uses an array of pointers to store its members. The > type is optimized for the most common list operations in Python: > iteration and appending. Python code rarely changes the head or middle > of a list. The dequeue type is an optimized data structure for popping > and inserting data at both ends. > I disagree that Python code rarely pops elements off the top of a list. There are perfectly valid use cases for wanting a list over a dequeue without having to pay O(N) for pop(0). Maybe we are just quibbling over the meaning of "rarely." > When you list.pop() or list.insert() the pointers in the internal array > must be shifted. appending is much faster because the internal array is > overallocated meaning it contains free slots at the tail of the data > structure. A linked list of pointers requires more memory and iteration > is slower since since it can't utilize the CPU's cache as good as an array. > I am not proposing a linked list of pointers. I am wondering about something like this: p = &p[1]; (and then reclaim p[0] as free memory, I already said I understood that was the tricky bit) The pointer arithmetic for accessing each element would still work in O (1), right? -- http://mail.python.org/mailman/listinfo/python-list
