To add additional verification by testing in Ami Answer, I made a simple ring buffer from a numpy array that uses only direct indexing to create inserts. Basically, each insertion simply changes the values of the oldest element in the queue.
The code is not completely trouble-free, but it can serve as the basis for simple performance testing.
import math import numpy as np class CircFifo(): """ helper class, uses a numpy array to provide a circular fixed size fifo interface. put(element): removes the oldest element and places a new one get(): returns the oldest entry empty(): returns true if fifo is empty full(): returns true if fifo is full """ def __init__(self, size): self.array = np.empty(shape=(size, 2)) self.size = size self.array[:] = np.NAN self.top = 0 self.bottom = 0 def put(self, row): self.array[self.top, :] = row self.top += 1 if self.top == self.size: self.top = 0 def get(self): if not math.isnan(self.array[self.bottom, 0]): row = copy.deepcopy(self.array[self.bottom, :]) self.array[self.bottom, :] = float('NaN') self.bottom += 1 if self.bottom == self.size: self.bottom = 0 if math.isnan(self.array[self.bottom, 0]): self.bottom = 0 self.top = 0 return row def empty(self): if math.isnan(self.array[self.bottom, 0]): return True else: return False def full(self): if self.size - np.count_nonzero( np.isnan(self.array[:, 0])) == self.size: return True else: return False
The correctness of the responses in the message seems to be confirmed by a simple test that I run. I checked the performance of the insert against the deque object. Even for 1000 attachments, deque, which is also a server as a dynamic rather than a static data structure (unlike my static circular spot), clearly outperforms the circular fifo.
Here is a simple test that I run
In [5]: import time In [6]: circFifo = CircFifo(300) In [7]: elapsedTime = 0 In [8]: for i in range(1, 1000): ...: start = time.time() ...: circFifo.put(np.array([[52, 12]])) ...: elapsedTime += time.time() - start ...: In [9]: elapsedTime Out[9]: 0.010616540908813477 In [21]: queue = deque() In [22]: elapsedTime = 0 In [23]: for i in range(1, 1000): ....: start = time.time() ....: queue.append(np.array([[52, 12]])) ....: elapsedTime += time.time() - start ....: In [24]: elapsedTime Out[24]: 0.00482630729675293
I know that this test is not informative, but it becomes quite obvious that deque is much faster. At least this is the number of inserts.
I would expect that if this circular fifo were implemented in C with a static array, it could not be easily beaten. Since basically a static array of C is the simplest and has a smaller data structure available.