Steve Howell <showel...@yahoo.com> writes: > Proposal: Improve list's implementation so that deleting elements from > the front of the list does not require an O(N) memmove operation. ... > It is possible now, of course, to use a data structure in > Python that has O(1) for deleting off the top of the list, but none of > the alternatives fully replicate the benefits of list itself.
I think you are mostly referring to deque. Why don't you instead say what you think is wrong with using deque, and how deque can be improved? > See above. An implementation of this PEP would not change the > definition of the language in any way, but it would have to minimally > impact the performance of lists for the normal use cases. But you're talking about adding one or two words to EVERY list, and many normal use cases allocate a LOT of lists. Those use cases are likely more common than use cases that pop from the front of the list but for some reason can't use deque. > The most ambitious proposal is to fix the memory manager itself to > allow the release of memory from the start of the chunk. That's inappropriate given the memory fragmentation it would cause. Really, you're describing a problem that arises in a few programs but up til now, as far as I know, everyone has found deque to be an adequate solution. Your approach of snarling against list is not persuading anyone that list needs to be changed, because most everyone is satisfied with the existing solution. You might change approaches and discuss deque, what's wrong with it, and whether it can be fixed. Getting a change approved for deque is probably much easier than getting one approved for list, just because nowhere near as many things depend on deque's performance. And when discussing performance in this context, additive constants do matter. -- http://mail.python.org/mailman/listinfo/python-list
