我想知道是否有一种算法可以计算“最常见的项目”而不必对每个项目进行计数？例如，假设我是一个搜索引擎，想要跟踪 10 个最受欢迎的搜索。我不想做的是为每个查询保留一个计数器，因为我可能有太多查询无法计数（而且大多数都是单例）。有一个简单的算法吗？也许是概率性的东西？谢谢！
问问题
449 次
4 回答
4
好吧，如果您有大量查询（可能像搜索引擎那样），那么您可以对查询进行“抽样”。因此，您每秒可能会收到 1,000 个查询，但如果您只保持每秒一个计数，那么在较长的一段时间内，您会得到一个相对接近“真实”答案的答案。
例如，“采样”分析器就是这样工作的。它每隔n毫秒查看当前正在执行的函数。在很长一段时间（几秒钟）内，您会很好地了解“昂贵”的功能，因为它们是您的示例中出现频率更高的功能。
您仍然需要进行“计数”，但通过定期采样，而不是计算每个查询，您可以获得实际必须存储的数据量的上限（例如，每秒最多一次查询等）
于 2010-05-05T06:41:09.100 回答
2
如果您想在任何给定时间进行最频繁的搜索，则不需要无穷无尽的计数器来跟踪每个提交的查询。相反，您需要一种算法来衡量任何给定查询的提交量除以设定的时间段。这是一个非常简单的算法。提交给您的搜索引擎的任何搜索，例如“缓存”一词，都会存储一段固定的时间，称为刷新率，（刷新率的长度取决于您的搜索引擎获得的流量类型和数量您想要跟踪的“最佳结果”）。如果刷新率时间段到期并且没有持续搜索“缓存”一词，则查询被删除内存。如果对“cache”这个词的搜索持续存在，你的算法只需要跟踪“cache”这个词被搜索的速度。为此，只需将所有搜索存储在“泄漏计数器”上。每个条目都被推送到具有到期日期的计数器上，之后查询将被删除。您的活动计数器是您的热门查询的指标。
于 2010-05-05T20:24:40.960 回答
0
Storing each and every query would be expensive, yet necessary to ensure the top 10 are actually the top 10. You'll have to cheat.
One idea is to store a table of URLs, hit counters, and timestamp indexed by count, then timestamp. When the table reaches some arbitrary near-maximum size, start removing low-end entries that are older than a given number of days. Although old, infrequent queries won't be counted, the queries likely to make the top 10 should make it on the table because of the faster query rate.
Another idea would be to write a 16-bit (or more) hash function for search queries. Have a 65536-entry table holding counters and URLs. When a search is performed, increment the respective table entry and set the URL if necessary. However, this approach has a major drawback. A spam bot could make repeated queries like "cheap viagra", possibly making legitimate queries increment the spam query counters instead, placing their messages on your main page.
于 2010-05-05T06:51:17.137 回答