algorithm - 倒排列表并集

Question

给 k 个排序倒排列表，我想要一个有效的算法来获得这些 k 个列表的并集？每个倒排列表都是内存中的只读数组，每个列表都包含排序后的整数。结果将保存在一个足够大的预定义数组中。有没有比 k-way 合并更好的算法？

Answer 1

K-Way 合并是最优的。它有O(log(k)*n)ops [其中n是所有列表中元素的组合数]。

很容易看出它不能做得更好 - 正如@jpalecek 提到的那样，否则你可以更好地对任何数组进行排序，然后O(nlogn)将其拆分为大小为 1 的块 [倒排索引]。

• 注意：此答案假定对倒排索引 [结果数组] 进行排序很重要。对于大多数使用倒排索引的应用程序来说，这个假设是正确的，尤其是在信息检索领域。这个特性[排序索引]允许优雅和快速的索引交叉。
• 注意：标准的 k 路合并允许重复，您必须确保如果一个元素出现在两个列表中，它只会被添加一次]。

Answer 2

如果您不需要对结果数组进行排序，最好的方法是使用哈希表来标记您看到了哪些元素。这样，您可以获得O(n)（n元素总数）时间复杂度。

类似于（Perl）的东西：

my %seen;
@merged = grep { exists $seen{$_} ? 0 : ($seen{$_} = 1) } (map {(@$_)} @inputs);