On Jan 24, 12:44 pm, Paul Rubin <no.em...@nospam.invalid> wrote: > 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? >
There is nothing wrong with deque, at least as far as I know, if the data strucure actually applies to your use case. It does not apply to my use case. > > 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. For EVERY list, you are not only allocating memory for the list itself, but you are also allocating memory for the objects within the list. So the extra one or two words are NEGLIGIBLE. > > 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. > Bullshit. Memory managers consolidate free memory chunks all the time. That's their job. > 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. Wrong. Many programs delete the first element of the list. > 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. Please provide evidence of that. I am pretty sure that everybody who chooses alternatives to Python would disagree. > 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. Again...I am not looking to improve deque, which is a perfectly valid data structure for a limited set of problems. > And when discussing performance in this contextc > additive constants do matter. Wrong again. Operations that mutate lists are already expensive, and a few checks to see if unreleased memory can be reclaimed are totally NEGLIGIBLE. -- http://mail.python.org/mailman/listinfo/python-list
