algorithm - 引き違い窓セット

Question

特定のデータストリーム (〜 100k 値/秒) からの 1 分間のスライディング ウィンドウから一連の値を効率的に維持する方法を探しています。

最大で対数の挿入時間を持つソリューションを探しています (値の基本的な時系列ベクトルには o(n) があるため)

Answer 1

私があなたの質問を誤解していない限り、これは循環バッファを使用して一定時間（挿入ごとに一定）で実行できます。ウィンドウ内の要素の最大数よりも 2 のべき乗の長さのバッファーを割り当てます。たとえば、1 秒あたり最大 10 万の値、1 分あたり 600 万の値なので、8388608 バイトの長さのバッファを割り当てます。このバッファに絶対インデックスを保持しますが、そこに挿入し、インデックスを 0x7FFFFF でマスクして要素を削除します。