[Numpy-discussion] Double-ended queues

[Nathaniel Smith]

On Tue, Sep 25, 2012 at 12:31 PM, Sturla Molden <sturla at molden.no> wrote:
> On 25.09.2012 11:38, Nathaniel Smith wrote:
>
>> Implementing a ring buffer on top of ndarray would be pretty
>> straightforward and probably work better than a linked-list
>> implementation.
>
> Amazingly, many do not know that a ringbuffer is simply an array indexed
> modulus its length:
>
> foo = np.zeros(n)
> i = 0
> while 1:
>    foo[i % n]  # access ringbuffer
>    i += 1

Good trick, but to be reliable I think you need to either be willing
for i to overflow into a long (arbitrary width) integer, or else make
sure that i is an unsigned integer and that n is 2**k where k <=
sizeof(i)? Just doing i %= n on each pass through the loop might be
less error-prone.

> Also, instead of writing a linked list, consider collections.deque.
> A deque is by definition a double-ended queue. It is just waste of time
> to implement a deque (double-ended queue) and hope it will perform
> better than Python's standard lib collections.deque object.

The original poster is using collections.deque now, but wants a
version that supports efficient vectorized operations.

-n