0

昨日面接をしました。プログラミングの問題の解決策がわからなかったので、ここでいくつかのアイデアを入手したいと思います。問題は：

JavaでTimeWindowBufferを実装する必要があります。これは、時間の経過とともにユーザーが継続的に受け取る番号を格納します。バッファにはmaxBufferSizeがあります。ユーザーは、過去数秒間の平均値、つまりユーザーから渡されたtimeWindowを知りたいと考えています（これはスライディングウィンドウです）。システムから現在の時刻を取得できます（System.currentTimeMills()Javaなど）。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
}

例：

たとえば、ユーザーは1秒ごとに数値を受信し（ユーザーは特定の速度で数値を受信しない場合があります）、過去5秒間の平均値を知りたいとします。
入力：
maxBufferSize = 5、timeWindow = 5（s）
numbers = {-5 4 -8 -8 -8 1 6 1 8 5} 出力
（説明のためにここに式をリストしますが、ユーザーは結果のみを必要とします）：- 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-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;
  ...
}

ペアは時間順に追加されるため、リストで2分探索を実行し、timeWindowに該当する数値の平均を計算できます。問題は、バッファにmaxBufferSizeがあり（ArrayListにはありませんが）、バッファがいっぱいになったときに最も古い値を削除する必要があることです。そして、その値はまだtimeWindowを満たすことができますが、今ではオフレコになり、いつ期限切れになるかはわかりません。

私は今のところここで立ち往生しています。

直接の答えは必要ありませんが、ここでいくつかの議論やアイデアがあります。問題と私の説明について混乱があれば、今すぐ教えてください。

4

2 に答える 2

1

I enjoy little puzzles like this. I did not compile this code, nor did I take into account all the things you would have to for production usage. Like I did not design a way to set a missed value to 0 - i.e. if a value does not come in at every tick.

But this will give you another way to think of it....

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;
  }
}
于 2013-01-12T03:46:32.760 に答える
0

あなたの質問は、一定のメモリを使用してストリームの統計を計算すると要約できます。

私にとって、それtimeはキーとvalue値としてのヒープ (プライオリティ キュー) でありtime、一番上にありません。

新しい を受け取ったら(time,value)、それをヒープに追加します。ヒープ サイズがバッファ サイズより大きい場合は、ヒープが十分に小さくなるまで、ヒープ内のルート ノードを削除します。

timeまた、ヒープを使用すると、O(1) 時間でバッファー (つまりヒープ)の最小値を取得できるため、time古いペアがすべてクリアされるまで、ルート (最小値を持つノード) を削除するだけです。

統計の場合、整数を保持しsumます。新しいペアをヒープに追加すると、sum = sum + value of pair. ヒープからルートを削除すると、sum = sum - value of root.

于 2013-01-14T05:15:38.433 に答える