On Tue, Sep 25, 2012 at 6:50 AM, Nathaniel Smith <njs@pobox.com> wrote:
On Tue, Sep 25, 2012 at 12:31 PM, Sturla Molden <sturla@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