倒排列表联盟

给k排序倒排列表，我想要一个有效的算法来获得这些k列表的联合？每个反转列表是内存中的只读数组，每个列表都包含按排序顺序的整数。结果将被保存在足够大的预定义数组中。有什么算法比k路合并更好吗？倒排列表联盟

2012-02-26 Fan Zhang

将被倒置？ – sizzzzlerz 2012-02-26 15:10:19

（1）请注意，k-way合并不会这样做，因为可能会在元素之间产生混淆，您需要删除这些元素。（2）你如何实现倒排索引？数组？一棵B +树？ – amit 2012-02-26 15:10:26

@amit一个排序的数组。 – 2012-02-26 15:14:00

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

这是很容易看到它不能做的更好 - 因为@jpalecek提到的，否则你可能会整理所有阵列更好，然后通过O(nlogn)其分割成大小1.

注意大块[倒排索引]：这个答案假定重要的是倒排索引 [结果数组]将被排序。对于使用倒排索引的大多数应用程序，这种假设是正确的，尤其是在信息检索区域。此功能[排序索引]允许优雅和快速交叉的索引。
注意：标准的k-way合并允许重复，你将不得不确保如果一个元素出现在两个列表中，它将会只添加一次 [容易做到这一点只需检查最后一个元素添加前的目标数组]。

2012-02-26 15:16:08 amit

k路合并是否至少有'O（log（k）* n）'时间复杂度，而不是'O（n）'？否则，你可以对'O（n）'中的任何数组进行排序（将每个元素作为一个列表）。 – jpalecek 2012-02-26 15:25:13

@jpalecek：你绝对是对的，我不知道是什么让我写这个谬论的声明[猜测我认为'k'是一个常数，而且显然不在这里]。 editted。 – amit 2012-02-26 15:37:57

-1

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

沿（Perl的）东西线：

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

都包含在一个列表什么样的价值观，什么意思

2012-02-26 15:40:16 jpalecek

倒排索引默认排序 - 结果不会是倒排索引。 – amit 2012-02-26 15:42:49

回答