algorithm - 限制每个时间段的事件数

Question

我需要限制在 deltaT 时间段内允许的事件数 n。我能想到的任何方法，空间都是 O(m)，其中 m 是每个 deltaT 发送的事件请求的最大数量，或者 O(deltaT/r)，其中 r 是可接受的分辨率。

编辑:deltaT 是一个相对于时间戳的滑动时间窗口。

例如:保留事件时间戳的循环缓冲区。在事件中裁剪所有早于 t-deltaT 的时间戳。如果时间戳的数量超过 n，则拒绝事件。将时间戳添加到缓冲区。

或者，初始化一个大小为 deltaT/r 的整数循环桶缓冲区，该缓冲区按相对于当前分辨率 r 的时间进行索引。维护指针i。在事件中，自上次事件以来的时间除以 r 后递增 i。将原始 i 和新缓冲区之间的缓冲区清零。在 i 处递增。如果 bugger 的总和超过 n，则拒绝。

什么是更好的方法？

---

我刚刚在 c# 中实现了我上面的第二个建议，固定 deltaT 为 1 秒，固定分辨率为 10 毫秒。

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;
    }
}

Answer 1

如果有这些变量呢:num_events_allowed、time_before、time_now、time_passed

在初始时间你会做:time_before = system.timer(), num_events_allowed = n

收到事件后，您执行以下操作:

  time_now = system.timer()
  time_passed = time_now - time_before
  time_before = time_now

  num_events_allowed += time_passed * (n / deltaT);

  if num_events_allowed > n 
      num_events_allowed = n

  if num_events_allowed >= 1
      let event through, num_events_allowed -= 1
  else
      ignore event

这个算法的好处是 num_events_allowed 实际上是根据自上次事件以来耗时和可以接收的事件的速率递增的，这样你就可以增加每个事件可以发送的事件数time_passed 以保持在 n 的限制内。因此，如果您过早收到一个事件，您会将其递增小于 1，如果它在太长时间后递增，您将递增超过 1。当然，如果事件通过，你就会将津贴减 1，因为你刚刚得到一个事件。如果津贴超过了最大事件 n ，则将其返回到 n ，因为在任何时间阶段都不能允许超过 n 。如果允许量小于 1，则不能发送整个事件，不要让它通过!

这是漏桶算法:https://en.wikipedia.org/wiki/Leaky_bucket