[Python-Dev] Alternative C implementation idea for collections.deque (original) (raw)

Raymond Hettinger python at rcn.com
Thu Nov 15 07:57:14 CET 2007

From: "Daniel Stutzbach" <daniel at stutzbachenterprises.com>

Many years ago I implemented a deque type in C (for use in C programs) using a single dynamically sized array as the underling type,

The approach was not used so we could avoid data movement associated with re-sizing.

I see the advantages as follows:

- getitem would take O(1) time instead of O(n)

While nice, that is somewhat at odds with how deques are used. The current implementation has O(1) access time with a tiny constant for access near the end-points. The only reason that getitem was put in was to support fast access to the head and tail without actually popping the value. That it can access the middle was incidental and imho optimizing in the middle access would only encourage mis-use of the data structure.

Compared to the existing code, memory allocation/deallocation is less frequent but more expensive when necessary,

For most use cases, the current version rolls around with no memory allocations (reusable blocks are kept on a free list).

Comments? Thoughts? Would a patch be welcome?

Might as well put it in the tracker for history/research purposes, but I think you're barking up the wrong tree. Deques are not about accessing the nth item in the middle. For their purpose, the current design works really well (the blocks are sized to fit in cache lines and no mass movements are necessary when the size changes -- the data never moves).

If you're going to spend time, why not put it into developing a data structure we don't already have (red-black trees or some such).

FWIW, my development time is now somewhat limited and I prefer to spend it on a todo list that has been around for some time. I dread throwing that time away and spending it on reviewing your patch, timing tons of test cases, arguing the merits of alternate approaches, and ending-up with substantially the same functionality that we already have.

The big win for deques was getting the O(1) append/pop on each end. That gave a huge algorithmic speed boost to the Queue module and a number of other tools that were using lists for deque-style operations.

Raymond

More information about the Python-Dev mailing list