元の質問は、前日にアクセスされた 5 GB の URL を含むファイルが与えられ、上位 k の頻繁な URL を見つけます。この問題は、ハッシュ マップを使用して個別の URL の出現をカウントし、O(n log k) 時間かかる最小ヒープを使用して上位 k を見つけることで解決できます。
入力が (静的ファイルではなく) 無制限のオンライン データ ストリームである場合、どうすれば最終日の上位 k URL を知ることができるでしょうか?
または、最後の分、最後の日、および最後の時間の上位 k URL を動的に取得できるシステムに改善できる点はありますか?
ヒントをいただければ幸いです!!
いくつかの間違ったエントリを含む可能性のある確率的な回答で解決したい場合は、count-min スケッチデータ構造を確認する必要があります。可能な限り少ないメモリを使用してストリーム内の頻繁な要素を推定するように特別に設計されており、ほとんどの実装では、ストリームからの上位 k 要素の時間と空間効率の非常に高い近似値をサポートしています。また、スペースの使い方を自由に調整できる構造になっているので、このようなシチュエーションにも最適です。IIRC Google はこれを使用して、最も頻繁な検索クエリを決定します。
オンラインで入手できるこのデータ構造の実装がいくつかあります。
お役に立てれば！