作者Arton0306 (Ar藤)
看板Prob_Solve
标题Re: [问题] 多个set作交集
时间Thu Oct 4 01:30:18 2012
※ 引述《chunhsiang (= =)》之铭言：
: 有n的不同大小的set
: t1,t2,...,tn
: 将其n个set全部交集(这里用and当运算符号)起来
: t1 and t2 and ... and tn
: 请问如何做效率能最好?
: 比如
: A = {1, 2, 3}
: B = {2, 3}
: C = {1, 2}
: D = {2}
: (A and B) and (C and D)
: = {2, 3} and {2}
: = {2}
: (((A and D) and B) and C
: = (({2} and B) and C)
: = {2} and C
: = {2}
: 有不同的运算顺序
: 假设集合A与B作交集 n=|A| m=|B|
: 只需要O(n+m)
利用到顺序的话 看看这个方法如何
首先把元素数最少的set 以hash的方式储存 先称此hash为H
接着考虑另一个set (若有排列过，那就拿元素数第二少的)
作交集：看哪些有在H中，做个记号，之後删掉H中没有被记号的元素，变成H'
再看另一个set，重覆这个步骤，得到H''...
loop 到最後一个hash得到全部set的交集
假设hash表现的不错 search delete 都O(1)
那就只需O(|S_1|+|S_2|+...|S_n|)
而且做交集的动作会越快，因为hash中的元素越来越少
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.42.50.130
1F：→ chunhsiang:A = 元素最少的集合 B = 剩下来任意集合 这样做 10/05 08:21
2F：→ chunhsiang:与 B = 剩下来最大的开始做(第二大) 10/05 08:22
3F：→ chunhsiang:哪个效率会比较好 10/05 08:22
4F：→ Arton0306:从最小的开始是因为要让一开始的交集就很小 10/05 13:48
5F：→ Arton0306:之後的选择如果有办法让交集快速减少是最好 10/05 13:49
6F：→ Arton0306:如果没有任何set的额外资讯 理应从小的开始 10/05 13:51
7F：→ chunhsiang:所以? B没有一定的 A要选最小 10/05 14:00
8F：推 eieio:我觉得这篇的方法比较好 10/05 15:00