最後の1時間のキー値ペアのストリームのトップ10

Question

タイムスタンプを持つキー値のペアのストリームがあり、最後の1時間に最大値のトップ10キーを検索したいとします。 （最後の1時間のキーの値は、その特定のキーのストリーミングされたすべての値の合計です）。

私はこのようなソリューションを考え出しました：http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/。しかし、私は時間の複雑さに重い費用をかけることなく、時間を絵にもたらすことができません。任意のアイデアが評価されます。

Answer 1

正確なオンラインアルゴリズムを得るには、すべてのものを複数コピーする必要があります。赤黒の木のようなソートされたデータ構造のキーを値で追跡する必要があります。あなたはキーで追跡する必要があります。クイックキールックアップの値 - ハッシュが機能します。 1時間以上経過したものを取り除くことができるように、何らかのイベントループ/観測待ち行列が必要です。それと

、観察を追加するためのあなたのプロセスは、次のようになります。削除するには、現在あるすべての観測値を削除し

1. 。 （1分でそれを行う方法の詳細はこちらをご覧ください）
2. 削除するタイムスタンプとともに、to-deleteのキューに観測を追加します。
3. キーで、キーによる値のハッシュの現在の合計値を見つけます。
4. 値+ keyによって、平衡バイナリツリーのエントリを見つけて削除します。
5. keyのvalueハッシュの現在の合計値を更新します。
6. キーの値のハッシュに新しい値を挿入します。

トップ10を見つけるには、同様のパスを実行する必要があります。

1. 現在削除しているすべての観測を削除します。 （1分でそれを行う方法の詳細はこちらをご覧ください）
2. トップ10の観測については、平衡二分木を見てください。

とキューを削除するには、トップの要素が一時間以上古いですが、削除するために現在の観測値を削除するには：

1. をキューを削除するからキー/値のペアをポップ。
2. 合計値のハッシュ値をキーで検索します。
3. 平衡バイナリツリーから値を削除します。
4. 合計値のハッシュの合計値をキーで更新します。
5. バランスのとれたバイナリキーに新しい値/キーを挿入します。

OK、費用と時間はどうですか？

私たちはすべての観察の3つのコピーを保持します。オーバーヘッドを伴う複雑なデータ構造のものつまり、過去1時間のイベントのためにおそらく5倍のスペースを使用しています。観測ごとに多くの操作がありますが、すべて対数です。実際、データ構造を最新に保ち、トップ10を返すために、観測ごとの合計労力はO(log(n))のようになります。

オーバーヘッドが大きくなりすぎると、単純な解決策は近似することです。大量の近似アルゴリズムがありますが、最も簡単なことはデータ構造にランダムに含めることです。たとえば、100を超える値を持つものはその値の1％に含まれ、以下の値を持つものは含まれる可能性があります。次に、最終的な答えに100を掛けます。平均値が1〜10の範囲にある場合、O(1)フィルタは、必要なデータストレージと作業の90-99%を削除しました。しかし、おおよその答えが表示されます。