有什么算法可以很快地取到交集。

shan_ghost

先分别排序，设需要求交集的集合共M个，则这样做的复杂度是M*O(N logN);这比先合并后排序的O(M*N log(M*N))要好一些。


分别排序完成后，再以定制的、类归并排序算法处理M个集合的交集。方法是：
0、假设按升序排序
1、从任意集合A开始，找到其他集合中不大于A首元素的元素（前面的全部丢弃）
2、检查所有这些元素是否相同
2.1、都相同，则把这个元素放入交集
2.1.2、从集合A的下一个元素开始，跳到1继续执行
2.2、不相同，以这些元素中最大的一个为准，以该元素所在集合为A，跳到1继续执行


上面这个算法的复杂度大概是O(M*N)。

最终，总体复杂度大约是O(M*N)+M*O(N logN)，即： O(M*N logN)

shan_ghost

selfrun 发表于 2013-04-01 10:45

这个好。不排序时间复杂度就下去了。

设各集合总数据量为N，则空间复杂度O(N)（用hash_map的话，应该是O(N*(1+x%))，x为额外保留、用于避免key冲突的空间），时间复杂度O(2N)=O(N)。

shan_ghost

二分查询是O(ln N)；求交集需要对至少一个集合里的每个元素做一次二分查询，复杂度是O(N lnN)，达到排序的复杂度了。加上前面排序的O(N lnN)，是现在最差的一个方案。


最开始那个先排序后用“变形归并算法”合并的方案，最后一步可以做到O(N)，但前面排序的O(N lnN)无法省略。

hash方案需要额外N*(1+x%)的空间，但复杂度可以达到O(N)，是现在时间效率最高的方案。

shan_ghost

http://research.microsoft.com/pubs/142850/p255-DingKoenig.pdf

微软的一篇论文：

Fast Set Intersection in Memory
Bolin Ding and Arnd Christian König
26 January 2011

Set intersection is a fundamental operation in information retrieval and database systems. This paper introduces linear space data structures to represent sets such that their intersection can be computed in a worst-case efficient way. In general, given k (preprocessed) sets, with totally n elements, we will show how to compute their intersection in expected time O(n / sqrt(w) + kr), where r is the intersection size and w is the number of bits in a machine-word. In addition,we introduce a very simple version of this algorithm that has weaker asymptotic guarantees but performs even better in practice; both algorithms outperform the state of the art techniques for both synthetic and real data sets and workloads.

shan_ghost

根据微软的文档，它的算法是基于已排序的列表（Algorithms based on Ordered Lists）的。

在这个前提下，hash算法在实际测试上是性能最差的。这可能和hash函数本身以及冲突有关。merge算法（没仔细看，应该和我的想法相同）效率不错，微软的算法只比它优秀一点点。


不过，另一方面，由于原始数据已排序对hash算法无意义，所以直接拿它和其他算法比较，可能是不公平的。
换句话说，其他算法和hash方法比较时，应把排序时间也计算在内。此时hash算法就仍然是最好的。（因为排序复杂度是O(N lnN)，当然，对总数为N的若干集合，复杂度肯定比这个低；而merge已排序集合算法复杂度只有O(N)。hash算法甚至可以直接和这类算法比较，那么，当merge类算法加上之前“作弊”忽略的排序过程，很难比hash更好）。

——没仔细看整个文档，不能确定微软做测试时，究竟有无计算排序时间。

shan_ghost

看了你的原始问题。这个用数据库可能是最好的。因为数据库本身是有组织的，提供的集合算法优化的也比较好。

另外写代码，一个是不可能利用数据库本身的数据结构（重建太浪费时间了），第二是自己搞的算法，很难比数据库专业人员搞的更好。

shan_ghost

cokeboL 发表于 2013-04-02 11:07

+1024

32位机器上，max_int=2,147,483,647
比你这个数字狠太多了……


PS：位图的确高效。但能用位图的前提是：目标数字本身取值范围较窄。