18

ミリ秒単位の解像度でプログラムにメッセージが入ってきます (ミリ秒あたりゼロから数百メッセージまで)。

分析をしてみたいと思います。具体的には、メッセージが着信するたびに更新される、メッセージ数の複数のローリング ウィンドウを維持したいと考えています。たとえば、

  • 最後の 1 秒間のメッセージ数
  • 過去 1 分間のメッセージ数
  • 過去30 分間のメッセージ数を過去 1 時間のメッセージ数で割った値

「最後の 1 秒間に 1,017 件のメッセージ」のような単純なカウントを維持することはできません。メッセージが 1 秒よりも古い時期がわからないため、カウントに含めるべきではないためです...

私は、すべてのメッセージのキューを維持し、1 秒より古い最も新しいメッセージを検索し、インデックスからカウントを推測することを考えました。ただし、これは遅すぎるようで、多くのメモリを消費します。

これらの値をリアルタイムで効率的に取得できるように、プログラムでこれらのカウントを追跡するにはどうすればよいですか?

4

5 に答える 5

17

これは、循環バッファで処理するのが最も簡単です。

循環バッファには、固定数の要素とそれへのポインタがあります。バッファに要素を追加できます。追加すると、次の要素へのポインタがインクリメントされます。固定長のバッファを通過した場合は、最初から開始します。これは、「最後のN」個のアイテムを保管するためのスペースと時間の効率的な方法です。

これで、あなたの場合、1,000個のカウンターからなる1つの循環バッファーを作成できます。各カウンターは1ミリ秒の間にメッセージの数をカウントします。1,000個のカウンターをすべて追加すると、最後の1秒間の合計数がわかります。もちろん、カウントを段階的に更新することでレポート部分を最適化できます。つまり、挿入時に上書きした数値をカウントから差し引いてから、新しい数値を追加します。

次に、60スロットを持ち、1秒あたりのメッセージの総数をカウントする別の循環バッファを作成できます。1秒に1回、ミリ秒バッファーの合計カウントを取得し、秒などの解像度を持つバッファーにカウントを書き込みます。

ここでCのような擬似コード：

int msecbuf[1000]; // initialized with zeroes
int secbuf[60]; // ditto
int msecptr = 0, secptr = 0;
int count = 0;
int msec_total_ctr = 0;
void msg_received() { count++; }
void every_msec() {
  msec_total_ctr -= msecbuf[msecptr];
  msecbuf[msecptr] = count;
  msec_total_ctr += msecbuf[msecptr];
  count = 0;
  msecptr = (msecptr + 1) % 1000;
}
void every_sec() {
  secbuf[secptr] = msec_total_ctr;
  secptr = (secptr + 1) % 60;
}
于 2010-02-16T01:00:32.330 に答える
9

指数平滑法、別名指数加重移動平均が必要です。最後のメッセージが到着してからの時間のEWMAを取得し、その時間を1秒に分割します。これらのいくつかを異なる重みで実行して、より長い時間間隔を効果的にカバーできます。事実上、そのときは無限に長いウィンドウを使用しているので、データの期限切れについて心配する必要はありません。ウェイトを減らすことはあなたのためにそれをします。

于 2010-02-16T00:47:48.667 に答える
3

最後のミリ秒の間、カウントを保持します。ミリ秒スライスが次のスライスに移動したら、count をリセットし、count をミリ秒ローリング バッファー配列に追加します。この累積を維持すると、一定量のメモリで 1 秒あたりのメッセージ数を抽出できます。

0.1 秒のスライス (または 1 分に近い他の小さな値) が完了したら、ローリング バッファー配列から最後の 0.1*1000 項目を合計し、それを次のローリング バッファーに配置します。このようにして、ミリ秒単位のローリング バッファーを小さく (1 秒の最大ルックアップで 1000 アイテム)、1 分間のルックアップのバッファー (600 アイテム) に保つことができます。

次のトリックは、0.1 分間隔の分単位で実行できます。尋ねられたすべての質問は、いくつかの整数を合計する (または cummulative を使用している場合は 2 つの値を減算する) ことによって照会できます。

唯一の欠点は、最後の秒の値がミリ秒ごとに変更され、分の値が 0.1 秒ごとにのみ変更され、時間の値 (および最後の 1/2 時間の % を含む導関数) が 0.1 分ごとに変更されることです。しかし、少なくともメモリ使用量を抑えることができます。

于 2010-02-16T10:24:18.740 に答える
2

ローリング表示ウィンドウは非常に高速にしか更新できません。たとえば、1秒間に10回更新したい場合、1秒に相当するデータの場合、10個の値が必要になります。各値には、その1/10秒に表示されたメッセージの数が含まれます。これらの値をビンと呼びましょう。各ビンは1/10秒に相当するデータを保持します。100ミリ秒ごとに、ビンの1つが破棄され、新しいビンがその100ミリ秒に表示されたメッセージの数に設定されます。

1時間全体で1/10秒の精度を維持したい場合は、メッセージレートに関する1時間分の情報を保持するために36Kビンの配列が必要になります。しかし、それはやり過ぎのようです。

しかし、時間間隔が大きくなるにつれて精度を落とす方が合理的だと思います。

たぶん、1秒に相当するデータを100ミリ秒に正確に、1分に相当するデータを秒に正確に、1時間に相当するデータを1分に正確に保つというようになります。

于 2010-02-16T01:04:40.707 に答える
0

私は、すべてのメッセージのキューを維持し、1 秒より古い最も新しいメッセージを検索し、インデックスからカウントを推測することを考えました。ただし、これは遅すぎるようで、多くのメモリを消費します。

より良いアイデアは、メッセージのリンクされたリストを維持し、新しいメッセージを (タイムスタンプ付きで) 先頭に追加し、有効期限が切れたときに末尾からポップすることです。または、それらをポップしなくても、目的の時間枠で受信した最も古いメッセージへのポインターを保持し、そのメッセージの有効期限が切れたときに先頭に向かって進めます (これにより、複数の時間枠を 1 つのリストで追跡できます)。

必要に応じて末尾から先頭に移動してカウントを計算するか、カウントを個別に保存して、先頭に値を追加するたびに増分し、末尾を進めるたびに減分することができます。

于 2010-02-16T00:45:11.950 に答える