实现有限大小的TimeWindowBuffer

Question

我昨天去面试了。我无法找到一个编程问题的解决方案，我想在这里找到一些想法。问题是：

我需要在Java中实现一个TimeWindowBuffer，它存储用户随着时间的推移不断接收的数字。缓冲区有一个maxBufferSize。用户想知道过去几秒钟的平均值，用户传入的timeWindow (因此这是一个滑动窗口)。我们可以从系统获得当前时间(例如，Java中的System.currentTimeMills() )。TimeWindowBuffer类如下所示：

public class TimeWindowBuffer {
  private int maxBufferSize;
  private int timeWindow;

  public TimwWindowBuffer(int maxBufferSize, int timeWindow) {
     this.maxBufferSize = maxBufferSize;
     this.timeWindow = timeWindow;
  }

  public void addValue(long value) {
     ...
  }

  public double getAvg() {
     ...
     return average;
  }

  // other auxiliary methods
}

示例：

比方说，用户每秒钟接收一个数字(用户可能不会以一定的速率接收一个数字)，并且希望知道过去5秒的平均值。

输入

maxBufferSize = 5，timeWindow =5 (s)

numbers={-5 4 -8 -8 -8 6 1 8 5}

Output (我在这里列出了用于说明的公式，但用户只需要结果)：

-5 /1 (t=1)

(-5 + 4) /2 (t=2)

(-5 +4-8)/3 (t=3)

(-5 +4-8-8)/4 (t=4)

(-5 +4-8-8)/5 (t=5)

(4-8-8-8+ 1) /5 (t=6)

(-8-8-8+1+ 6) /5 (t=7)

(-8-8+1+6+ 1) /5 (t=8)

(-8 +1+6+1+ 8) /5 (t=9)

(1 +6+1+8+ 5) /5 (t=10)

由于没有指定TimeWindowBuffer的数据结构，所以我一直在考虑保留一对值及其增加的时间。因此，我对底层缓冲区的声明如下：

 private ArrayList<Pair> buffer = new ArrayList<Pair>(maxBufferSize);

哪里

class Pair {
  private long value;
  private long time;
  ...
}

由于这对是按时间顺序添加的，所以我可以在列表上进行二进制搜索，并计算属于timeWindow的数字的平均值。问题是缓冲区有一个maxBufferSize (尽管ArrayList没有)，当缓冲区已满时，我必须删除最旧的值。这个值仍然可以满足timeWindow的要求，但现在它已经不公开了，我永远也不会知道它何时到期。

我被困在这里是为了水流。

我不需要一个直接的答案，但在这里有一些讨论或想法。如果对这个问题和我的描述有任何疑问，请允许我现在就说。

Answer 1

我喜欢这样的小谜题。我没有编译这段代码，也没有考虑到生产使用中必须做的所有事情。就像我没有设计一种方法来将丢失的值设置为0，也就是说，如果一个值不是在每一个滴答处出现的话。

但这会给你另一种思考的方式.

public class TickTimer
{
  private int tick = 0;
  private java.util.Timer timer = new java.util.Timer();

  public TickTimer(double timeWindow)
  {
    timer.scheduleAtFixedRate(new TickerTask(),
          0, // initial delay
          Math.round(1000/timeWindow)); // interval
  }

  private class TickerTask extends TimerTask
  {
    public void run ()
    {
      tick++;
    }
  }

  public int getTicks()
  {
    return tick;
  }
}

public class TimeWindowBuffer
{
  int buffer[];
  TickTimer timer;

  final Object bufferSync = new Object();

  public TimeWindowBuffer(int maxBufferSize, double timeWindow)
  {
    buffer = new int[maxBufferSize]; 
    timer = TickTimer(timeWindow);
  }

  public boolean add(int value)
  {
    synchronize(bufferSync)
    {
      buffer[timer.getTicks() % maxBufferSize] = value;
    }
  }

  public int averageValue()
  {
    int average = 0;

    synchronize(bufferSync)
    {
      for (int i: buffer)
      {
        average += i;
      }
    }

    return average/maxBufferSize;
  }
}

Answer 2

您的问题可以概括为使用常量内存来计算流上的一些统计数据。

对我来说，这是一个堆(优先级队列)，其中键是time，值是value，顶部是最小的time。

当收到新的(time,value)时，将其添加到堆中。如果堆大小大于缓冲区大小，只需移除堆中的根节点，直到堆足够小。

此外，通过使用堆，您可以在O(1)时间内在缓冲区(即堆)中获得最小的time，所以只需删除根(具有最小time的节点)，直到清除所有过期的对。

对于统计数据，保留一个整数sum。当您向堆中添加新的对时，sum = sum + value of pair。当您从堆中删除根时，sum = sum - value of root。