查找最後一天或最後一小時或最後一分鐘的前k個訪問網址？

最初的問題是給定的文件包含5GB的URL被訪問的最後一天，找到最常見的k頻繁的URL。這個問題可以通過使用哈希映射來計算不同URL的出現次數，並在最小堆的幫助下找到最高k，並取O（n log k）時間。查找最後一天或最後一小時或最後一分鐘的前k個訪問網址？

現在我想如果輸入是無限的在線數據流（而不是靜態文件），那麼我怎麼能知道最後一天的前k個URL？

或者是否有任何改進，我可以讓系統的最後一分鐘和最後一天以及最後幾小時動態獲取頂部k URL？

任何提示將不勝感激！

來源

2013-01-02 user1941469

結帳http://stackoverflow.com/a/10190836/404145 – DiveInto

如果你願意接受可能包含一些錯誤輸入概率的答案，你一定要考慮的count-min sketch數據結構。它專門設計用於使用盡可能少的內存來估計流中的頻繁元素，而且大多數實現都支持流中前k個元素的非常時間和空間高效的近似。此外，該結構還可以調整空間使用情況，這對於這類情況非常理想。谷歌IIRC使用它來確定他們最常見的搜索查詢。

還有several implementations of this data structure在線提供。

希望這會有所幫助！

來源

2013-01-02 05:44:57 templatetypedef

查找最後一天或最後一小時或最後一分鐘的前k個訪問網址？

回答

相關問題