algorithm - top-k选择/合并

Question

我有 n 个排序列表(5 < n < 300)。这些列表很长(300000 多个元组)。选择单个列表的前 k 个当然是微不足道的——它们就在列表的开头。

k = 2 的示例:

top2 (L1: [ 'a': 10, 'b': 4, 'c':3 ]) = ['a':10 'b':4]
top2 (L2: [ 'c': 5, 'b': 2, 'a':0 ]) = ['c':5 'b':2]

当我想要所有排序列表中的前 k 个组合时变得更有趣。

top2(L1+L2) = ['a':10, 'c':8]

仅组合单个列表的前 k 个不一定会给出正确的结果:

top2(top2(L1)+top2(L2)) = ['a':10, 'b':6]

目标是减少所需空间并保持排序后的列表较小。

top2(topX(L1)+topX(L2)) = ['a':10, 'c':8]

问题是是否有一种算法可以计算出在某个位置切掉列表的长尾的同时具有正确顺序的组合top k。如果存在:如何找到可以安全切割的极限 X？

注意:正确的计数并不重要。只有顺序是。

top2(magic([L1,L2])) = ['a', 'c']

Answer 1

此算法使用 O(U) 内存，其中 U 是唯一键的数量。我怀疑是否可以实现较低的内存界限，因为在所有 key 已求和。

1. 制作一个包含 (key:total_count) 个元组的主列表。只需一次遍历每个列表中的一项，记录每个键出现的次数。
2. 使用任何 top-k selection algorithm在不使用额外内存的主列表上。一个简单的解决方案是就地对列表进行排序。