list.pop(0) vs. collections.dequeue

Steve Howell showell30 at
Sun Jan 24 11:33:36 CET 2010

On Jan 23, 8:00 pm, Raymond Hettinger <pyt... at> wrote:
> [Steve Howell]
> > Why wouldn't you get a competent C programmer simply make
> > list_ass_slice smart enough to make list.pop(0) O(1)?
> When this suggestion was discussed on python-dev years ago,
> it was rejected.  One reason is that it was somewhat
> common for C code to access the list data structure directly
> (bypassing API accessor functions).  Changing the list to have
> a starting offset would break existing C extensions.
> Another reason is that Guido is non-tolerant of space or time
> trade-offs for lists and tuples because they pervade the language
> and are heavily used internally.  Any additional space or time
> requirement however small would impact the language performance
> as a whole.  FWIW, that is also the reason that lists are not
> weak-referenceable (it would cost one extra pointer field per
> instance and that wasn't deemed to be worth it).
> > The brilliant computer scientist, Christian Heimes, provides the
> > answers, and I am paraphrasing here, of course:
> IMHO, Christian IS a brilliant computer scientist, so I'll ignore
> the rude intention and take the sentence literally.

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.

More information about the Python-list mailing list