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

__BlueGuy__

fender0107401 发表于 2013-04-01 16:35
果然又笑而不语了。。。

用这种方式装逼的还真是少见，基本上算得是硬装逼流了。

注：别以为二分查询很牛逼，二分查询的计算复杂性是O(1)，但是这并不代表你说的那个方法跑的快，以你这种经常“笑而不语”的智商，我相信你肯定能理解。

太搞了吧， 你
计算机的基本术语都不知道， 是 "复杂度"， 不是 "复杂性"
二分查找的复杂度也不是 O(1) 是 lgn

你他妈学过程序没有啊 ？

__BlueGuy__

还有，你都不知道引入 计算复杂度 的目的是什么？
计算复杂度低， 程序能不快吗 ， 还不一定， 不一定你妹啊 ！

shan_ghost

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


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

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

__BlueGuy__

回复 33# shan_ghost

数主有一步是顺序查的， 总比他顺序查要快吧   

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.

cokeboL

求楼主贴用各种算法的代码和实际测试结果

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

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

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

fender0107401

__BlueGuy__ 发表于 2013-04-01 16:49
还有，你都不知道引入 计算复杂度 的目的是什么？
计算复杂度低， 程序能不快吗 ， 还不一定， 不一定你妹 ...

你真以为O(1)就快吗？

那你这水平就不用谈了。

你还是在自己找个地方笑而不语去吧。

__BlueGuy__

fender0107401 发表于 2013-04-01 17:49
你真以为O(1)就快吗？

那你这水平就不用谈了。

你找个O（1）不快的例子我看看