[Python-Dev] collections module
tim.one at comcast.net
Fri Jan 9 17:03:24 EST 2004
>> My own ideal solution would be a subtle hack to the list
>> implementation to make pop(0) and insert(0, x) go a lot faster --
>> this can be done by adding one or two extra fields to the list head
>> and allowing empty space at the front of the list as well as at the
> I'm sure you know this, but just for sake of argument, how many extra
> fields? A couple? A few? 20? 30?
As Guido said, "one or two" would be enough. I think you're talking about
different things, though: Guido is talking about the number of new named
struct members that would have to be added to Python's list object header.
I think you're talking about how many array slots to leave unused on both
ends. Just as now, on a reallocation the number of free slots asked for has
to be proportional to the total number of slots, so that growth via a huge
number of one-at-a-time appends takes (amortized) constant-time per append.
Picking any fixed number of free slots leads to overall quadratic-time (in
the number of appends) behavior.
More information about the Python-Dev