On Jan 24, 3:20 am, Steven D'Aprano <st...@remove-this- cybersource.com.au> wrote: > On Sun, 24 Jan 2010 02:33:36 -0800, Steve Howell wrote: > > You are also a brilliant computer scientist, despite the fact that you > > are defending a list implemenation that can't pop the first element off > > the list in O(1) time. > > You say that like it's a bad thing.
It is. > It's very simple: the trade-offs that the Python development team have > deliberately chosen aren't the same trade-offs that you prefer. That > doesn't make your trade-offs right and Python's wrong. They're just > different, and if Python lists had your preferred implementation, I > guarantee that somebody would be complaining about it right now. > > If you're serious about wanting O(1) pops from the start of the list, > write your own list implementation and use it. You might even like to > make it public, so others can use it as well. But please stop with the > snide remarks and poorly disguised insults and back-handed compliments, > it's getting tedious. I will stop being snide, but I will be blunt, and if anybody interprets my criticism as an insult, so be it. The current algorithm is broken. It's a 20th century implementation of lists built on top of a 20th century memory manager. It's at least ten years behind the times. > Or just change your algorithm slightly -- it's not hard to turn an > algorithm that pops from the start of a list to one that pops from the > end of the list. > The fact that you are proposing to reverse a list to work around its performance deficiencies just confirms to me that the algorithm is broken. I will concede the fact that most of CPython's tradeoffs are driven by the limitations of the underlying memory manager. If realloc () allowed you to easily release memory from the front of a previously allocated block, we'd be talking about maybe a 10-line patch here, and it wouldn't impact even list_resize() in a meaningful way. Even with realloc()'s brokenness, you could improve pop(0) in a way that does not impact list access at all, and the patch would not change the time complexity of any operation; it would just add negligible extract bookkeeping within list_resize() and a few other places. The objection that the extra pointer would increase the size of list objects is totally 20th century thinking. It would be totally negligible for any real world program. -- http://mail.python.org/mailman/listinfo/python-list
