[Numpy-discussion] Double-ended queues

[Charles R Harris]

On Tue, Sep 25, 2012 at 6:50 AM, Nathaniel Smith <njs at pobox.com> wrote:

> 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.
>
>
The C++ stdlib has an efficient deque object, but it moves through memory.
Hmm, it wouldn't be easy to make that work with numpy arrays what with
views and all.

Efficient circular lists are often implemented using powers of two so that
modulo indexing can be done using a mask.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20120925/413f25c6/attachment.html>