给定的原始问题是包含 5GB URL 的文件，该文件包含最后一天访问的 URL，找到前 k 个频繁访问的 URL。该问题可以通过使用哈希映射来计算不同 URL 的出现次数并在最小堆的帮助下找到前 k 个来解决，花费 O(n log k) 时间。
现在我在想，如果输入的是无限的在线数据流（而不是静态文件），那我怎么知道最后一天的前k个URL呢？
或者我可以对系统进行任何改进，使我能够动态获取最后一分钟、最后一天和最后几个小时的前 k 个 URL？
任何提示将不胜感激！
问问题
3047 次
1 回答
1
如果您愿意接受可能包含一些错误条目的概率答案，那么您绝对应该查看count-min 草图数据结构。它专门设计用于使用尽可能少的内存来估计流中的频繁元素，并且大多数实现都支持对流中的前 k 个元素进行非常节省时间和空间的近似。此外，该结构可让您调整空间使用情况，这使其成为此类情况的理想选择。IIRC Google 使用它来确定他们最频繁的搜索查询。
该数据结构有多种在线实现。
希望这可以帮助！
于 2013-01-02T05:44:57.530 回答