algorithm - 实时显示一段时间内最常见/重复的元素

Question

我有用户生成的字符串以未定义的速率传入，其中一些是重复数据，我想实时保留前 20 个最常见重复项的计数，在给定的固定时间段内(例如，在过去一小时内)，在 Go 中。

唯一字符串的数量不受任何限制，因此，为了避免 DoS，数据结构可能必须定义最多元素的大小(例如，top-10k-elements 和/或1MB 整体大小)，并删除最近最少插入的元素(如果它们还没有任何重复项)(但永远不要删除任何新传入的元素!)。

我的理解是这正是ngx_http_limit_req_module.c是implemented , 此方法在 documentation 中被引用然而，作为“漏桶”，wikipedia页面似乎表明它是将从队列中删除的新数据，而不是旧数据，因此不确定该概念是否适用。

无论如何，我尝试在 Golang 中寻找“漏桶”实现，到目前为止，我找到的最受欢迎的结果是 uber-go/ratelimit ，它的 API 似乎根本不符合我的问题陈述——它只是实现了一些实际的速率限制队列，而不是实时的前 X 超过最后 Y 计数。

任何人都可以为我正在寻找的东西建议适当的名称，以及实现这一目标的最佳方法，最好是在 Go 中吗？

Answer 1

这是两个问题。

1. 记录您选择记录的姓名。
2. 注意不在您要跟踪的列表中的热门名称。

对于第一个问题，我建议跟踪每个名称、每分钟有多少个。当他们完成时，将它们添加到运行总数中，并添加到要在一小时内减去的事物队列中。这为每个名称提供 60 个小对象，并且在运行的基础上，您将保持哈希运行。

第二个问题更具挑战性。为此，我会使用概率方法。这个想法是每个名字都用一个唯一的 id 进行散列，并且你只保留你在一分钟内看到的千个最小的散列值(和相关的名字)。 (我会在一分钟内给出一个算法。)你的散列值应该独立于名字均匀分布在最大的 2^64 中，所以普通名字最终会出现在这个列表中。当他们这样做时，你开始数他们! (您将丢失前几个，但是通过更多的工作，您可以估计您错过了多少。尽管如此，这种优化可能需要做更多的工作。)

现在我们如何保留千个最小的哈希值？您使用优先级队列，它通常通过堆 实现，以创建可更新的数据结构，在其中很容易提取最大的哈希值。因此，您运行以下伪代码。

create your priority queue of (hash, name)
for each name:
   hash hash of name and unique new id
   entry = (hash, name)
   if queue size < 1000:
       insert entry
   else if hash is smaller than the current max in the queue
      insert entry
      remove the largest entry