algorithm - 从电子商务网站订购的 Top-k 商品

Question

什么是最好的方法(使用的算法/数据结构)来获得在购物网站上订购的前 k 项商品，相关信息在其 n 个服务器中的每一个的日志中？
我正在考虑一种方法，该方法涉及维护一个固定大小的双向链表 k 每个节点都有一个计数变量(可能是一个范围)一组共享相同计数的产品 ID。随着每个事件(productId)的到来，列表被遍历并更新计数，如果可能的话，提升到下一个更高的计数范围。
上述做法是否正确？还有哪些其他更好的解决方案？

Answer 1

您的方法不正确，您说列表的大小是固定的，但这表明您已经知道哪些是前 k 个元素 - 显然不是这种情况。假设您已经有一个大小为 k 的填充列表，并且您遍历了一半的项目——现在，下一个项目在整个集合中重复(n/2 次重复)——它显然应该在前 k 个中，但你从未将它放入列表中——所以结果是错误的。

您可以通过某些方式解决问题，具体取决于限制(主要是日志文件的大小)。

方法 1:构建直方图并找到前 k 个元素

首先，迭代列表，构建一个histogram (基于散列/树的映射 map<item,int> ) - 然后，在找到每个元素重复出现的数量后，它只是找到前 k 个元素，这在 this thread 中有介绍。在细节。
查找top k是通过维护一个最小堆来完成的，迭代你的集合，为每个项目检查它是否高于你堆中的最小项目，如果是，从堆中弹出元素并插入这个项目相反。

构建直方图的方法很简单:

histogram = new map<item,int>
for each element x in the list:
  val = (x is a key in map? map.get(x) : 0) + 1
  map.put(x,val)

此方法的复杂度为 O(nlogn)如果使用基于树的 map ，或 O(nlogk)如果使用基于哈希的 map 。这是非常有效的，但是如果您的日志文件包含数万亿个条目，则可能无法在合理的时间内在一台机器上完成，您需要将工作分配到多台机器上。这引导我们采用下一种方法。

方法 2: map-reduce

此方法适用于非常大的日志文件，并且通过将问题分布在大型集群上来完成。这是一种更复杂的方法 - 但对于非常大的文件，可能无法使用一台机器找到前 k 个元素。

map(file):
  for each item in file:
      emit(item,1)
reduce(item,list)
  sum = 0
  for each x in list:
      sum = sum + x
  emit(item,sum)

在这个阶段，你处理了列表并构建了一个直方图，现在我们需要找到前 k 个，想法是拆分数据，这样每台机器都会得到一部分，并产生它的本地前 K 个元素，然后将所有#machines*K 元素发送到将选择全局前 k 的单个“master”机器