c - Checking real-time for N events within T time in memory-constrained environment - Stack Overflow

admin管理员组

文章数量:1188234

I am working on some firmware, and I have to implement some logic that takes an immediate action if N number of events have occurred in the previous T milliseconds. However, N and T are user-configurable settings. N will need to be in the hundreds.

The challenge is that memory is extremely limited (I only have a few KB left to use) but the only way I know how to implement this algorithm is something like the following (Python for brevity and illustrative purposes, but I'm actually working in C):

import time
from collections import deque 

history = deque(maxlen=N)   # N is user-configurable

def on_event (): 
    """Called on an event, takes an action if N events occur within T time."""
    
    history.append(time.monotonic()) # removes oldest if len > maxlen (N)

    if len(history) >= N and history[-1] - history[0] <= T:  # T is user-configurable
        history.clear()
        take_an_action()

In C I'd use a ring buffer for the history to keep the algorithm performant. That's the easy part.

The hard part is this algorithm requires storage of N timestamps. In the firmware each timestamp is a 32-bit integer so if N is configured to be, say, 500, this will require 500*4 = 2000 bytes of memory, which I can't afford to use for this.

My question is: I'd like to allow for values of N that aren't constrained by memory. Is there any way to implement this logic in a way that doesn't require storing N historical timestamps? For now I am not concerned about performance, only memory efficiency.

I am working on some firmware, and I have to implement some logic that takes an immediate action if N number of events have occurred in the previous T milliseconds. However, N and T are user-configurable settings. N will need to be in the hundreds.

The challenge is that memory is extremely limited (I only have a few KB left to use) but the only way I know how to implement this algorithm is something like the following (Python for brevity and illustrative purposes, but I'm actually working in C):

import time
from collections import deque 

history = deque(maxlen=N)   # N is user-configurable

def on_event (): 
    """Called on an event, takes an action if N events occur within T time."""
    
    history.append(time.monotonic()) # removes oldest if len > maxlen (N)

    if len(history) >= N and history[-1] - history[0] <= T:  # T is user-configurable
        history.clear()
        take_an_action()

In C I'd use a ring buffer for the history to keep the algorithm performant. That's the easy part.

The hard part is this algorithm requires storage of N timestamps. In the firmware each timestamp is a 32-bit integer so if N is configured to be, say, 500, this will require 500*4 = 2000 bytes of memory, which I can't afford to use for this.

My question is: I'd like to allow for values of N that aren't constrained by memory. Is there any way to implement this logic in a way that doesn't require storing N historical timestamps? For now I am not concerned about performance, only memory efficiency.

• c
• algorithm
• firmware

Share Improve this question Follow asked Jan 24 at 20:20 Jason CJason C 40.3k1515 gold badges133133 silver badges197197 bronze badges 7

• 2 Would an approximate result be acceptable? Say be subdividing the interval T into K histogram buckets of events, with the result accurate to the resolution of the subdivision. – doynax Commented Jan 24 at 20:45
• Are you sure this is the logic you want? Wouldn't you want to process the history after the time interval is up rather than wait for another event which might be a while? The history could end up waiting an indeterminate amount of time. – Simon Goater Commented Jan 24 at 21:01
• @doynax I think that would be OK that's not a bad idea. – Jason C Commented Jan 24 at 21:03
• 1 Re “Is there any way to implement this logic in a way that doesn't require storing N historical timestamps?”: The desired behavior you describe requires that, for any particular event, the device’s behavior change when an event becomes T old. In order for that to happen, the times of all events not yet T old must be part of the device’s state information. Therefore you must have memory for them… – Eric Postpischil Commented Jan 24 at 22:48
• 1 … Then your options are: (a) Figure out how much information is needed. It might not be 32 bits for each timestamp times N timestamps. You might need only log2(T/r) bits per timestamp, where r is the resolution needed (seconds, milliseconds, whatever); the timestamps could operate in a cyclic window of times (units of time since the last rollover). Or (b) Accept some alteration of the desired behavior. – Eric Postpischil Commented Jan 24 at 23:02

 |  Show 2 more comments

1 Answer 1

Sorted by: Reset to default 0

I can improve this slightly. The following will work if T is under 32 seconds.

As an example, let's do T is 5 seconds, and N is 500. We will keep:

• Lagging timestamp = 4 bytes.
• Circular buffer of just the last byte of each event's timestamp = 500 bytes.
• Both where you are reading from and writing to in that buffer. We only need 2 bytes each, for 4 more bytes.
• A list of where in the circular buffer we increment the second byte. That's 2 bytes per entry, for a buffer of 20 elements, is another 40 bytes.
• Both where you are reading from and writing to in that second buffer. That's 1 byte each for 2 more bytes.

Total, 550 bytes.

本文标签： cChecking realtime for N events within T time in memoryconstrained environmentStack Overflow