I need to cap the number of events n permitted during a time period deltaT. Any approach I can think of, space is O(m), where m is the maximum number of eventrequests sent per deltaT, or O(deltaT/r), where r is an acceptable resolution.
Edit: deltaT is a sliding time window relative to the timestamp.
For instance: Keep a circular buffer of event timestamps. On event crop all earlier timestamps than t-deltaT. Deny event if the number of timestamps exceeds n. Add timestamp to the buffer.
Or, init a circular bucket buffer of integers of size deltaT/r indexed by time relative to the current with resolution r. Maintain pointer i. On event, increment i by time since last event divided by r. Zero the buffer between the original i and the new one. Increment at i. Deny, if the sum of the bugger exceeds n.
What's a better way?
I just implemented my second suggestion above in c# with a fixed deltaT of 1 s and a fixed resolution of 10 ms.
public class EventCap
{
private const int RES = 10; //resolution in ms
private int _max;
private readonly int[] _tsBuffer;
private int p = 0;
private DateTime? _lastEventTime;
private int _length = 1000 / RES;
public EventCap(int max)
{
_max = max;
_tsBuffer = new int[_length];
}
public EventCap()
{
}
public bool Request(DateTime timeStamp)
{
if (_max <= 0)
return true;
if (!_lastEventTime.HasValue)
{
_lastEventTime = timeStamp;
_tsBuffer[0] = 1;
return true;
}
//A
//Mutually redundant with B
if (timeStamp - _lastEventTime >= TimeSpan.FromSeconds(1))
{
_lastEventTime = timeStamp;
Array.Clear(_tsBuffer, 0, _length);
_tsBuffer[0] = 1;
p = 0;
return true;
}
var newP = (timeStamp - _lastEventTime.Value).Milliseconds / RES + p;
if (newP < _length)
Array.Clear(_tsBuffer, p + 1, newP - p);
else if (newP > p + _length)
{
//B
//Mutually redundant with A
Array.Clear(_tsBuffer, 0, _length);
}
else
{
Array.Clear(_tsBuffer, p + 1, _length - p - 1);
Array.Clear(_tsBuffer, 0, newP % _length);
}
p = newP % _length;
_tsBuffer[p]++;
_lastEventTime = timeStamp;
var sum = _tsBuffer.Sum();
return sum <= 10;
}
}