java - 無限のストリームに n 個の最大頻度の数値を保持する

Question

数値の無限のストリーム (BigInteger) が与えられた場合、上位 N 個の出現(頻度)を持つ数値をどのように検出して保存できますか?

メモリには制限があります (数値ごとにカウンターを格納できません)。

編集：

頻度の値は次のサイズを超えることはできませんlong

score 4 · Accepted Answer

上位 N 件の外観は、すべてのデータ (またはほとんどのデータ) が揃うまで決定できません。

これまでの N の出現回数は、出現回数をカウントし、カウント順に並べ替えることで判断できます。これは、多くを保存できない場合に問題になる可能性があります。この場合、スペースを節約するためにどのような妥協をするかを決定する必要があります。

long十分な大きさではないと思います。どのようなデータをカウントしていますか?

あなたが直面している問題を示す簡単な例。

アカウント ID の無限のストリームがすべて異なるとします。これは、トップ N を記録する唯一の方法は、それらすべてを記録することであることを意味します。いくつかの近道がなければ、他に考えられる解決策はありません。

注: ユーザーがしばらくの間見られている場合は、体重を減らしたいと思うように、減衰平均が本当に必要な場合があります。トップユーザーをアクティブでなくなったユーザーにしたくありません。

score 1 · Accepted Answer

ストリームが無限である場合、いくつかの低い頻度の数がより頻繁になる可能性があります。つまり、すべての数値の頻度を更新する必要があります。

一方、には境界がないためBigIntegers、無限のストレージ要件があります。すべての数値nについて、少なくともいくつかの情報を保存する必要があります (少し言ってみましょう)。メモリが有限である場合、のようなf別の整数があります。mm * n > f

この問題は、いくつかの追加の制約なしでは解決できません。

編集

あなたが示したように、訪問者数を追跡したいと思います。過去 1 年または 1 か月だけ数えた方が簡単ではないでしょうか。辞書 (訪問者、訪問) のペアがあるだけです。BigIntegers については、2^63-1 を超えるユーザーを計画していますか?

score 0 · Accepted Answer

分布が定常的であると仮定でき、おおよその結果を受け入れる場合は、ストリームからの数の有限サンプルに基づいて結果を推定できます。