list.pop(0) vs. collections.dequeue

Steve Howell showell30 at yahoo.com
Sun Jan 24 13:59:32 EST 2010


On Jan 24, 3:20 am, Steven D'Aprano <st... at 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.







More information about the Python-list mailing list