[Python-Dev] Alternative C implementation idea for collections.deque

[Raymond Hettinger]

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