algorithm - 找到集合中出现次数最多的元素

Question

假设您正在为您的网站构建一个分析程序，您每次访问该页面时都会在其中记录该页面的地址，因此您的 log.txt 可能是

x.com/a
x.com/b
x.com/a
x.com/c
x.com/a

没有计数器，它只是一个日志文件，没有使用 sql，因为它有数千个元素，您的一千个左右的唯一域地址 (x.com/a x.com/b)，遍历此列表并吐出前 10 个 url 的最有效方法是什么。

我最好的解决方案是通过日志文件，然后如果哈希表中不存在该域，则将其添加为键，并增加其值；然后在哈希上搜索最大的 10 个值。

我不相信这是最好的解决方案，不仅因为空间复杂性(如果唯一域从几千到几百万会发生什么)，还因为我需要对哈希表进行另一次搜索以找到最大值。

Answer 1

即使对于几千或几百万条目 - 您的方法也很好 - 它具有平均线性 (O(n)) 运行时间 - 所以它还不错。

但是，您可以使用 map-reduce如果您想要更高的可扩展性，请采用这种方法。

map(file):
   for each entry in file:
         emitIntermediate(getDomainName(entry),"1"))
reduce(domain,list):
   emit(domain,size(list))

以上将有效地为您提供 (domain,count) 元组的列表，您所要做的就是选择前 10 个。

选择前 10 个元素可以使用 map-reduce(分布式)排序实现可伸缩性 - 或者使用最小堆(迭代同时维护堆中遇到的前 10 个元素)。第二个在 this thread 中有更详细的解释。

---

关于空间复杂度:如果你使用的是 64 位系统，你可以将它用作 RAM，让操作系统做它能做的(通过在需要时将元素交换到磁盘)，你不太可能需要更多那么金额Virtual Memory你有一台 64 位机器。另一种方法是使用针对文件系统优化的哈希表(或 B+ tree)，并对其执行相同的算法。

---

但是，如果情况确实如此 - 并且数据不适合 RAM，并且你不能使用 map-reduce，我怀疑排序和迭代 - 虽然将是 O(nlogn ) 会更有效率(使用外部排序)——因为磁盘访问的次数将被最小化，并且磁盘访问比 RAM 访问慢得多。