algorithm - 今天发生次数最多的 N 个事件

Question

假设我们为网站构建分析并想显示今天 N 个最流行的页面。该算法应满足两个要求 - 常量内存 和移动计数器。

常量内存

可能有数十亿个页面，我们不想对所有页面进行计数。该算法应该使用某种使用常量内存的智能概率计数器。有 Count–min sketch但它似乎试图估计所有元素的计数，这里我们不关心所有元素，只关心前 N 个，所以也许有一些更好更简单的估计器？

移动计数器

前 N 个页面每天都不同，今天前 2 个页面可能是 /cats.html 和 /dogs.html 但明天可能是一些完全不同的东西，比如 /pizza.html 和 /donuts.html。最简单的方法是每天重新启动计数器，这很好，但也许有一些更聪明的方法，比如移动平均线？

事件流示例:

[
 { page: '/cats.html',   time: 'today, 12:00' }, 
 { page: '/cats.html',   time: 'today, 11:00' }, 
 { page: '/dogs.html',   time: 'today, 10:00' }, 
 { page: '/dogs.html',   time: 'today, 09:00' }, 
 { page: '/donuts.html', time: 'today, 08:00' }, 
 { page: '/donuts.html', time: 'yesterday, 20:00' }, 
 { page: '/cats.html',   time: 'yesterday, 19:00' }, 
 ...
]

Answer 1

如果我没记错的话，你可以用常量内存获取最频繁的值，但我认为它不适用于多个值。

如果近似答案足够好，您可能需要查看 HyperLogLog算法。这不是完全相同的问题，因为它计算唯一值的数量，但那里使用的技术可能对解决您的问题很有用。

This question也相关，但它没有常量内存约束。