algorithm - 分组、排序和返回前 N 个结果的有效方法

Question

我有一个流(或一长串元素，可能是数千或数百万)，我必须返回前 N 个组(在我的情况下是 24 个)按组的平均值排序。所以项目的形式是:

{groupId: 1, value: 10}, {groupId: 2, value: 4}, {groupId: 1: value: 2}

并组成小组:

{groupId: 1, average: 6}, {groupId: 2: average}

显然，天真的解决方案是迭代、分组、按平均值对组进行排序并返回前 24 个组。对可以处理数百万个项目的高性能解决方案有什么想法吗？

Answer 1

您无法避免遍历整个列表以获取给定组的每个成员。一旦您获得了每个组的均值，您就可以执行以下操作:

1. 将 N 个第一组放入一个向量/数组中。
2. 从该数组中创建一个堆，堆的顶部是具有最大平均值的组。
3. 对于每个剩余的组，将其与堆的顶部进行比较:
   • 如果当前组大于堆顶，则丢弃
   • 如果较小，弹出堆顶，插入当前组

最后，所有 N 个第一组都在一个堆中。您可以通过应用堆排序的最后一步并反转您获得的容器来按顺序排列它们(因为堆是最大堆)。

整体复杂度:(其中 K 是上面定义的组总数和 N)

O(N + (K-N).ln(N) + N.ln(N) = O(N + K.ln(N))

• N 项来自前 N 组并构成初始最大堆。
• (K-N).ln(N) 项来自(删除顶部/插入当前组)操作对(最多 K - N 个) .
• 最后一项 (N.ln(N)) 用于最终堆的排序。