On Jan 23, 4:12 am, Steven D'Aprano <st...@remove-this- cybersource.com.au> wrote: > On Fri, 22 Jan 2010 21:42:43 -0800, Steve Howell wrote: > > This innocent program here literally moves about a million bytes of > > memory around for no good reason: > > > lst = [] > > for i in range(2000): > > lst.append(i) > > while lst: > > print lst.pop(0) > > > Why? Because list.pop(0) is implemented in O(N) instead of O(1). > > > Why wouldn't you get a competent C programmer simply make list_ass_slice > > smart enough to make list.pop(0) O(1)? > > Because there are always trade-offs, and the competent C programmers who > coded the implementation for lists choose different tradeoffs to the ones > you would prefer. > > Seems to me that the simple solution to your problem is for you to > implement your own data structure that makes whatever trade-offs you > like. If it is good enough and popular enough, it might even replace the > existing list implementation. >
The data structure that would make the tradeoffs I want would be implemented within CPython itself. I give a sketch of the changes elsewhere in this thread. Terry Reedy said: ''' If you try writing a full patch, as I believe someone did, or at least a prototype thereof, when the idea was discussed, you might have a better idea of what the tradeoffs are and why it was rejected. ''' I have to run, but tomorrow I will try to dig through python-dev archives and find the patch. If anybody has hints on where to look for it (anybody remember the author, for example?), it would be much appreciated. If the patch looks simple, I will try to pitch the idea that its time has come. Now that the specification of the language itself is frozen, I think there might be more room for improving implementations. Also, I might be able to make the argument that tradeoffs of memory vs. CPU vs. code complexity have different forces in the 2010s. Thanks for your reply. -- http://mail.python.org/mailman/listinfo/python-list
