Time-based sliding window and measuring (change of) data arrival rate
<p>I'm trying to implement a time-based sliding window (in Python), i.e., a data sources inserts new data items, and items older than, say, 1h are automatically removed. On top of that, I need to measures the rate, or rather the change of rate the data sources inserts items.</p>

<p>My question is kind of two-fold. First, how is the best way to implement a time-based window. In my currently, probably naive solution, I simply use a Python list <code>window = []</code>. In case of a new data <code>item</code>, I append the item with the current timestamp: <code>window.append((current_time, item))</code>. Then, using a timer, every 1sec I <code>pop</code> all first elements with a timestamp older than the current (timestamp-1h):</p>

<pre><code>threshold = int(time.time()*1000) - self.WINDOW_SIZE_IN_MS
while True:
    try:
        if window[0][0] &lt; threshold:
            del self.word_lists[0]
        else:
            break            
    except:
        break
</code></pre>

<p>While this works, I wonder if there are more clever solutions to this. </p>

<p>More importantly, what would be a good way to measure the change of rate data items enter the window. Here, I have no good idea how to approach this, at least none that sounds also efficient. Something very naive I had in mind: I split the 1h-window in 20 intervals each 5min and count the number of items. If the most recent 5min-interval conains significantly more items than the average of the 20 intervals, I say there is a burst. But I would have to do this every, say, 1min. This sounds not efficient and there are a lot of parameters. </p>

<p>In short, I need to measure the acceleration in which new items enter my window. Are there best-practices approaches for this?</p>

<p>For the first part, it is more efficient to check for expired items and remove them when you receive a new item to add.  That is, don't bother with a timer which wakes up the process for no reason once a second--just piggyback the maintenance work when real work is happening.</p>

<p>For the second part, the entire 1 hour has a known length.  Store an integer which is the index in the list of five minutes ago.  You can maintain this when doing an insert, and you know you only have to move it forward.</p>

<p>Putting it all together, pseudo-code:</p>

<pre><code>window = []
recent_index = 0
def insert(time, item):
    while window and window[0][0] &lt; time - timedelta(hours=1):
        window.pop()
        recent_index -= 1

    while window[recent_index][0] &lt; time - timedelta(minutes=5):
        recent_index += 1

    window.append((time, item))

    return float(len(window) - recent_index) / len(window)
</code></pre>

<p>The above function returns what fraction of items from the past hour arrived in the past five minutes.  Over 20 or 50%, say, and you have a burst.</p>

python list queue sliding-window