use*_*469 6 algorithm hash binary-heap data-structures streaming-algorithm
最初的问题是给出了前一天访问过的5GB URL的文件,找到了前k个常用URL.这个问题可以通过使用哈希映射计算不同URL的出现来解决,并在min heap的帮助下找到前k个,获取O(n log k)时间.
现在我在想如果输入是无限的在线数据流(而不是静态文件),那我怎么知道最后一天的前k个URL呢？
或者我是否可以对系统进行任何改进,使我能够动态地获取最后一分钟,最后一天和最后几小时的前k个URL？
任何提示将不胜感激!
如果您愿意接受可能包含一些错误条目的概率答案，那么您一定应该研究一下count-min sketch数据结构。它专门设计用于使用尽可能少的内存来估计流中的频繁元素，并且大多数实现都支持对流中前 k 个元素进行时间和空间高效的近似。此外，该结构允许您调整空间使用情况，这使其成为此类情况的理想选择。IIRC Google 使用它来确定他们最频繁的搜索查询。
这种数据结构有多种在线实现。
希望这可以帮助！