Chinaunix

标题: 有什么算法可以很快地取到交集。 [打印本页]
作者: fender0107401    时间: 2013-04-01 08:02
标题: 有什么算法可以很快地取到交集。
本帖最后由 fender0107401 于 2013-04-01 08:25 编辑

  2. a = {1, 2, 3, 4, 5, 6, 7};
  3. b = {2, 3, 5};
复制代码
如何知道a和b的交集？

数据量可能比较大，所以需要一个快一点的算法。

原始问题在这里：http://bbs.chinaunix.net/thread-4074355-1-1.html
作者: fender0107401    时间: 2013-04-01 08:50
如果总共有M个数组的长度分别是：N_1 N_2 .... N_max。

那我使用quick sort先排序的话，那么每次的排序算法的计算复杂性是O(nlog(n))，所有排序的复杂性加起来是M*O(N_max*log(N_max))。

然后把所有数组连成一个，再次排序那么复杂性是：(M*N_max)*log(M*N_max)，

然后我要对整个数组进行遍历，找出连续重复出现次数等于M的元素，这个复杂性是M*N_max。

所以整个的复杂性是M*N_max + (M*N_max)*log(M*N_max) + M*O(N_max*log(N_max)) = M*(N_max + N_max*log(M*N_max) + O(N_max*log(N_max)))。

这样应该是最快了吧？
作者: fender0107401    时间: 2013-04-01 08:50
:wink:
作者: hellioncu    时间: 2013-04-01 08:58
合并应该可以省去
作者: cokeboL    时间: 2013-04-01 09:26
比如都是int数组
计数：
分配个大数组清零，每个int数组元素作为大数组下标对大数组元素做++，各个数组都弄完之后，遍历一次大数组看哪些元素值和数组个数相等，取其下标为交集

如果是字符串之类的并且字符串数量不是特别大，弄个字符串和int的映射表，一样可以用上面的方法
数量巨大弄映射伤不起的话，楼主描述下数据特点吧，然后再想牛逼的算法吧。。。
作者: fender0107401    时间: 2013-04-01 09:56
hellioncu 发表于 2013-04-01 08:58
合并应该可以省去


作者: fender0107401    时间: 2013-04-01 10:03
cokeboL 发表于 2013-04-01 09:26
比如都是int数组
计数：
分配个大数组清零，每个int数组元素作为大数组下标对大数组元素做++，各个数组都 ...


全都是int的整数。

但是数字范围可能很大，都是数据库里面的主键。

我也想过弄个大点的数组，然后往里面填数据，但是实际中集合里面的整数可能“千”或者“万”为单位的，声明一个大的数组可能需要消耗很多没必要的存储空间。

除非是先映射一下，但是这样似乎比较麻烦。
作者: cokeboL    时间: 2013-04-01 10:37
本帖最后由 cokeboL 于 2013-04-01 10:39 编辑

如果遍历的话，各数组长度分别是 N_MIN， N_1， N_2 。。。 N_MAX

1.先N_MIN和N_1中找，N_MIN中每个元素和N_1中比较看是否有相等的，复杂度为O(N_MIN * N_1)
2.结果再和N_2比较，1中交集个数<= N_MIN，这里复杂度为O(N_MIN * N_2)
。。。
总复杂度为O(N_MIN * （N_1 + N_2 + ... N_MAX))也很大

我去搜搜
作者: selfrun    时间: 2013-04-01 10:45
回复 2# fender0107401


    c++的话用map;  c的话用红黑树做关联数组,标签id做key， value就是标签次数。
往map里或者红黑树里扔一遍，key存在就把value+1。
时间复杂度=sum(N_1....N_max) * log(sum(N_1...N_max);
空间复杂度=标签数。
遍历一遍关联数组，遇到value是M的就取出来。
作者: shan_ghost    时间: 2013-04-01 10:46
先分别排序，设需要求交集的集合共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)
作者: cokeboL    时间: 2013-04-01 10:47
回复 9# selfrun


    树本身的操作带来的额外复杂度可能已经太大了
作者: shan_ghost    时间: 2013-04-01 10:51
selfrun 发表于 2013-04-01 10:45


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

设各集合总数据量为N，则空间复杂度O(N)（用hash_map的话，应该是O(N*(1+x%))，x为额外保留、用于避免key冲突的空间），时间复杂度O(2N)=O(N)。
作者: cokeboL    时间: 2013-04-01 10:51
回复 10# shan_ghost


    我感觉排序没必要，直接遍历比较应该更省
作者: selfrun    时间: 2013-04-01 10:54
回复 11# cokeboL


    红黑树增删查的复杂度都是log(n)，空间嘛，每个节点3*sizeof(void*) + sizeof(byte) + sizeof(key) + sizeof(value)；百万数量级的小case
作者: cokeboL    时间: 2013-04-01 11:01
回复 14# selfrun


我是说，map或树本身的操作，就一堆代码，同样的O(n)，用树和for(  i < n  )相比，实际操作数上树、map要多很多

而且你看看遍历比较的，复杂度也没多高
作者: selfrun    时间: 2013-04-01 11:14
回复 15# cokeboL


    你说的方法复杂度是o(n)的,n=sum(N_1....N_max);若能实现当然最好；
不过实际问题里key的值域是很大的范围，空间复杂度太高； 若是用hash算法把key转成0~n-1的值，又很难保证不重复；或者用关联数组从key映射到索引，又回到关联数组上了...
作者: cokeboL    时间: 2013-04-01 11:18
回复 16# selfrun


空间复杂度没多大的，用C++的话也可以vector之类的，如果事先就找出各个数组中长度最小的n_min，空间复杂度最大也不会超过n_min，而且还可以不超过

第一个找出的交集长度，时间却会省很多
作者: hbmhalley    时间: 2013-04-01 12:04
本帖最后由 hbmhalley 于 2013-04-01 12:16 编辑

开一个大小可以忍受的 bool 数组，比如 bool its[0x10000] = {false..}
扫每个集合，过程略，最终: 对于 m，若所有集合里都存在某个 X 使得 (X&0xffff)=m，则 its[m] == true 否则 false
每个集合的每个元素 X 都附带一个 flag (初始true) ，扫完一遍后， flag &= its[X&0xffff]
这样筛掉后 16 位，用同样的方法筛 32 48 64位等等
最终 flag 为 true 的就是交集中的元素

复杂度 O(mn*log(65536,maxnum))，约等于下限 O(mn)

+实际上，这应该就是下限
因为判断两个数是否相等下限是 log(2^32,maxnum)=log(2^16,maxnum)/2
+排序是不必要的，而且楼上复杂度里都忽略了大数比较的复杂度
作者: __BlueGuy__    时间: 2013-04-01 13:29
数组 1 排序后， 对数组2进行二分查找

这是最自然的了， 看看速度再说吧.
作者: __BlueGuy__    时间: 2013-04-01 13:35
看你们说的津津乐道， 我就想笑
作者: cokeboL    时间: 2013-04-01 14:22
本帖最后由 cokeboL 于 2013-04-01 14:23 编辑
  1. #include <stdio.h>

  3. #define NON_EXIST (-1)
  4. #define ARR_SIZE_MAP(arr_n) { arr_n, sizeof(arr_n)/sizeof(arr_n[0]) }

  6. int n_1[] = {1, 2, 3, 5, 8, 9, 14};
  7. int n_2[] = {2, 3, 6, 7, 10, 14};
  8. //...
  9. int n_max[] = {1, 3, 14, 15, 28};

  11. static int *arr_mixed = 0;

  13. static struct Arr_map{
  14.     int *array_n;
  15.     int array_size;
  16. }array_size_map[] = {
  17.     ARR_SIZE_MAP(n_1),
  18.     ARR_SIZE_MAP(n_2),
  19. //    ...
  20.     ARR_SIZE_MAP(n_max)
  21. };

  23. void arr_mixed_init(struct Arr_map *am)
  24. {
  25.     if(arr_mixed){
  26.         free(arr_mixed);
  27.         arr_mixed = 0;
  28.     }
  29.    
  30.     arr_mixed = (int*)malloc(am->array_size + 1);
  31.     if(!arr_mixed){
  32.         printf("arr_mixed malloc failed: %m");
  33.         return;
  34.     }
  35.         for(int i = 0; i < am->array_size; i++){
  36.                 arr_mixed[i] = am->array_n[i];
  37.     }
  38.     arr_mixed[am->array_size] = NON_EXIST;
  39. }

  41. void arr_mixed_destroy()
  42. {
  43.         if(arr_mixed){
  44.             free(arr_mixed);
  45.         arr_mixed = 0;
  46.         }
  47. }

  49. //function for test print
  50. void print_arr_map(struct Arr_map am[], int am_len)
  51. {
  52.         for(int i = 0; i < am_len; i++){
  53.                 printf("am[%d] size %d: ", i, am[i].array_size);
  54.                 for(int j = 0; j < am[i].array_size; j++){
  55.                         printf("%2d ", am[i].array_n[j]);
  56.                 }
  57.                 printf("\n");
  58.         }
  59. }

  61. void find_mixed(struct Arr_map am[], int am_len)
  62. {
  63.         print_arr_map(am, am_len);
  64.     arr_mixed_init(&am[0]);

  66.     for(int i = 1; i < am_len; i++){
  67.         int count = 0;     
  68.         for(int j = 0; arr_mixed[j] != NON_EXIST; j++){
  69.             for(int k = 0; k < am[i].array_size; k++){
  70.                 if(arr_mixed[j] == am[i].array_n[k]){
  71.                     arr_mixed[count++] = arr_mixed[j];
  72.                                         break;
  73.                 }
  74.                                
  75.             }        
  76.         }
  77.         arr_mixed[count] = NON_EXIST;
  78.     }
  79. }

  81. int main()
  82. {
  83.     find_mixed(array_size_map, sizeof(array_size_map)/sizeof(array_size_map[0]));
  84.         printf("\nmixed foud: ------------>\n");
  85.         for(int i = 0; arr_mixed[i] != NON_EXIST; i++){
  86.         printf("arr_mixed[%d]: %d\n", i, arr_mixed[i]);
  87.     }
  88.     arr_mixed_destroy();
  89. }
复制代码
作者: cokeboL    时间: 2013-04-01 14:24
回复 20# __BlueGuy__


    排序太浪费了吧
作者: __BlueGuy__    时间: 2013-04-01 14:32
本帖最后由 __BlueGuy__ 于 2013-04-01 14:34 编辑
cokeboL 发表于 2013-04-01 14:24
回复 20# __BlueGuy__


我不知道你的程序速度是多少
排序 + 二分 也就 nlgn

你们都不要再回复我， 我拒绝回复这样的弱智题
作者: cokeboL    时间: 2013-04-01 14:35
回复 23# __BlueGuy__


    那你写一个排序+二分的然后比较下速度试试
作者: __BlueGuy__    时间: 2013-04-01 14:38
楼主不适合写程序， 鉴定完毕 ！
作者: freshxman    时间: 2013-04-01 14:40
提示: 作者被禁止或删除 内容自动屏蔽
作者: __BlueGuy__    时间: 2013-04-01 14:43
你们对算法的理解完全停留在幼儿园的水平， 跟你们都没法交流
作者: fender0107401    时间: 2013-04-01 16:10
__BlueGuy__ 发表于 2013-04-01 14:38
楼主不适合写程序， 鉴定完毕 ！


装逼男。

别动不动的就在那里“笑而不语”，我相信众多版友都知道你装逼装到没话说的时候经常整一句“笑而不语”。
作者: __BlueGuy__    时间: 2013-04-01 16:26
本帖最后由 __BlueGuy__ 于 2013-04-01 16:28 编辑
fender0107401 发表于 2013-04-01 16:10
装逼男。

别动不动的就在那里“笑而不语”，我相信众多版友都知道你装逼装到没话说的时候经常整一句 ...


排序 + 二分 比你的算法不高明？ 我哪里装了？
查个数连个 二分都想不到， 你写JB个程序啊 ...

你那个破算法，都不知道你是怎么想出来的？傻B

笑而不语 ！
作者: fender0107401    时间: 2013-04-01 16:35
本帖最后由 fender0107401 于 2013-04-01 16:36 编辑
__BlueGuy__ 发表于 2013-04-01 16:26
排序 + 二分 比你的算法不高明？ 我哪里装了？
查个数连个 二分都想不到， 你写JB个程序啊 ...


果然又笑而不语了。。。

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

注：别以为二分查询很牛逼，二分查询的计算复杂性是O(1)，但是这并不代表你说的那个方法跑的快，以你这种经常“笑而不语”的智商，我相信你肯定能理解。
作者: __BlueGuy__    时间: 2013-04-01 16:46
fender0107401 发表于 2013-04-01 16:35
果然又笑而不语了。。。

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

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


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

你他妈学过程序没有啊 ？
作者: __BlueGuy__    时间: 2013-04-01 16:49
本帖最后由 __BlueGuy__ 于 2013-04-01 16:50 编辑

还有，你都不知道引入 计算复杂度 的目的是什么？
计算复杂度低， 程序能不快吗 ， 还不一定， 不一定你妹啊 ！
作者: shan_ghost    时间: 2013-04-01 16:54
二分查询是O(ln N)；求交集需要对至少一个集合里的每个元素做一次二分查询，复杂度是O(N lnN)，达到排序的复杂度了。加上前面排序的O(N lnN)，是现在最差的一个方案。


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

hash方案需要额外N*(1+x%)的空间，但复杂度可以达到O(N)，是现在时间效率最高的方案。
作者: __BlueGuy__    时间: 2013-04-01 17:02
回复 33# shan_ghost

数主有一步是顺序查的， 总比他顺序查要快吧   
作者: shan_ghost    时间: 2013-04-01 17:05
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    时间: 2013-04-01 17:09
求楼主贴用各种算法的代码和实际测试结果
作者: shan_ghost    时间: 2013-04-01 17:23
根据微软的文档，它的算法是基于已排序的列表（Algorithms based on Ordered Lists）的。

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


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

——没仔细看整个文档，不能确定微软做测试时，究竟有无计算排序时间。
作者: shan_ghost    时间: 2013-04-01 17:40
看了你的原始问题。这个用数据库可能是最好的。因为数据库本身是有组织的，提供的集合算法优化的也比较好。

另外写代码，一个是不可能利用数据库本身的数据结构（重建太浪费时间了），第二是自己搞的算法，很难比数据库专业人员搞的更好。
作者: fender0107401    时间: 2013-04-01 17:49
__BlueGuy__ 发表于 2013-04-01 16:49
还有，你都不知道引入 计算复杂度 的目的是什么？
计算复杂度低， 程序能不快吗 ， 还不一定， 不一定你妹 ...


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

那你这水平就不用谈了。

你还是在自己找个地方笑而不语去吧。
作者: __BlueGuy__    时间: 2013-04-01 21:51
fender0107401 发表于 2013-04-01 17:49
你真以为O(1)就快吗？

那你这水平就不用谈了。


你找个O（1）不快的例子我看看
作者: linux_c_py_php    时间: 2013-04-01 22:15
总结一下：

1, 2个数组都排序, 然后求merge.
2, 对数组1建哈希表, 遍历数组2查哈希表.

第二种方法冲突随着规模增大迅速升高, 不过如果支持rehash的哈希表可能会强点.
作者: folklore    时间: 2013-04-01 23:05
回复 41# linux_c_py_php


    支持不支持rehash对本题无影响的
个人支持Hash为比较好的方案。 因为Hash就算只利用了1%的Key空间， 在大规模下也只是匹配100次而已， 这个数目不算大。
当然，前提是Key空间要能自适应目标的规模的大小 。
作者: starwing83    时间: 2013-04-02 03:31
judy array？
作者: fender0107401    时间: 2013-04-02 07:50
不是2个数组是M个数组。 :wink:
作者: fender0107401    时间: 2013-04-02 07:52
__BlueGuy__ 发表于 2013-04-01 21:51
你找个O（1）不快的例子我看看


你要是保证以后在CU上不骂人，我就给你举个例子出来。
作者: insnowind    时间: 2013-04-02 10:31
回复 1# fender0107401

为啥不使用位数组呢，假设你有100万个数，定义一个100万位数组也才需要空间123KB，位数组初始化为0.
然后遍历第一个数组，将对应的元素位置1，然后遍历第二个数组，查看对应的位是否为1即可。

复杂度就是M + N。


   
作者: insnowind    时间: 2013-04-02 10:36
回复 46# insnowind

上面是两个数组的情况，N个数组也是一样，把前两个交集的结果作为一个数组，与后面的持续遍历即可；


   
作者: linux_c_py_php    时间: 2013-04-02 10:55
位图是高效, 面试经常问.
作者: cokeboL    时间: 2013-04-02 11:07
回复 46# insnowind


    如果数组里最大的数字式1 0000 0000呢
作者: shan_ghost    时间: 2013-04-02 11:29
本帖最后由 shan_ghost 于 2013-04-02 11:33 编辑
cokeboL 发表于 2013-04-02 11:07


+1024

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


PS：位图的确高效。但能用位图的前提是：目标数字本身取值范围较窄。
作者: insnowind    时间: 2013-04-02 11:40
回复 49# cokeboL

分治法，根据值范围划分成你内存可容忍的组大小。

   
作者: linux_c_py_php    时间: 2013-04-02 11:44
cokeboL 发表于 2013-04-02 11:07
回复 46# insnowind


位图是数组, 还需要考虑容量吗..

作者: 乱叶    时间: 2013-04-02 13:21
  我想问下 集合内可能出现重复的数不，如果不出现  我就把两个集合给合并了 处理了
作者: cokeboL    时间: 2013-04-02 13:31
回复 51# insnowind


    怎么分？假如数字的大小从1到((unsigned)-1)都可能，范围比较广
作者: cokeboL    时间: 2013-04-02 13:37
回复 52# linux_c_py_php


我不太懂位图，我的理解是以目标数字作为下标，比如3，可以看成整个数组的第三位（也就是第一个字节的第三位），如果是利用下标，那特别大的数字，

比如((unsigned)-1)对应的下标很大，即使除以8，所要生成的位图数组也需要很大空间，这样太难弄了


不知道我理解的位图是不是这个意思，不对请指正，学习下
作者: insnowind    时间: 2013-04-02 14:34
回复 55# cokeboL

你的理解是正确的，数字范围越大，确实会存在内存用量大的问题，
但目前为止，我还没遇到过因为存储导致位图算法不可行，
如最大数为1亿，你需要的内存也才12MB，相比现在的存储，简直是九牛一毛了

如果非的要对内存做限制，如仅有12M内存，但你有最大数为10亿，
可以按照0-1E,1-2E进行10次交集，最后合并起来就是最终的交集。
   
作者: cokeboL    时间: 2013-04-02 14:58
本帖最后由 cokeboL 于 2013-04-02 14:59 编辑

回复 56# insnowind


1亿只是我随便举的例子，如果是((unsigned)-1)/8，那就要512M左右了，或者64位机器，可以更大

您下面这个：

如果非的要对内存做限制，如仅有12M内存，但你有最大数为10亿，
可以按照0-1E,1-2E进行10次交集，最后合并起来就是最终的交集。

10次交集，不明白是什么意思，求解答~
作者: 网鬼    时间: 2013-04-02 15:10
__BlueGuy__ 发表于 2013-04-01 14:43
你们对算法的理解完全停留在幼儿园的水平， 跟你们都没法交流


那个连线程基础也搞不明白的__BlueGuy__，不管你是多么的精通算法，多么扎实的基础
这里是大家交流学习，有人说的不对，你大可说你的看法，如果你牛，请针对这个问题写一个你的C实现出来供大家学习
而不是“笑而不语”的乱喷，这种态度，会让人觉得很装B，哦，我不是觉得，我就是认为你在装B
作者: __BlueGuy__    时间: 2013-04-02 20:03
网鬼 发表于 2013-04-02 15:10
那个连线程基础也搞不明白的__BlueGuy__，不管你是多么的精通算法，多么扎实的基础
这里是大家交流学习 ...


哥哥做了几年游戏客户端，也没用到过线程
作者: __BlueGuy__    时间: 2013-04-02 20:17
CU 基本是做服务器的， 对客户端一点不了解
作者: ilogo1    时间: 2013-04-08 16:50
本帖最后由 ilogo1 于 2013-04-08 16:59 编辑

算法题，最长公共子集，O(mn)。。动态规划。。
O(m+n)的位图算法，会面临位图初始化问题，当然可用语言关键字特性解决。。。
作者: leejqy    时间: 2013-05-09 09:23
1.hash法，理想状况O(m+n)；
2.排序+二分,O(nlogn+mlogn)
3.如果都是整形，位图，O(m+n);




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2