<br><br><div class="gmail_quote">On Tue, Sep 25, 2012 at 6:50 AM, Nathaniel Smith <span dir="ltr"><<a href="mailto:njs@pobox.com" target="_blank">njs@pobox.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Tue, Sep 25, 2012 at 12:31 PM, Sturla Molden <<a href="mailto:sturla@molden.no">sturla@molden.no</a>> wrote:<br>
> On <a href="tel:25.09.2012%2011" value="+12509201211">25.09.2012 11</a>:38, Nathaniel Smith wrote:<br>
><br>
>> Implementing a ring buffer on top of ndarray would be pretty<br>
>> straightforward and probably work better than a linked-list<br>
>> implementation.<br>
><br>
> Amazingly, many do not know that a ringbuffer is simply an array indexed<br>
> modulus its length:<br>
><br>
> foo = np.zeros(n)<br>
> i = 0<br>
> while 1:<br>
>    foo[i % n]  # access ringbuffer<br>
>    i += 1<br>
<br>
</div>Good trick, but to be reliable I think you need to either be willing<br>
for i to overflow into a long (arbitrary width) integer, or else make<br>
sure that i is an unsigned integer and that n is 2**k where k <=<br>
sizeof(i)? Just doing i %= n on each pass through the loop might be<br>
less error-prone.<br>
<div class="im"><br>
> Also, instead of writing a linked list, consider collections.deque.<br>
> A deque is by definition a double-ended queue. It is just waste of time<br>
> to implement a deque (double-ended queue) and hope it will perform<br>
> better than Python's standard lib collections.deque object.<br>
<br>
</div>The original poster is using collections.deque now, but wants a<br>
version that supports efficient vectorized operations.<br>
<span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><div><br>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.<br>
<br>Efficient circular lists are often implemented using powers of two so that modulo indexing can be done using a mask.<br><br>Chuck<br></div><br></div>