作者chunhsiang (= =)
看板Prob_Solve
标题[问题] 多个set作交集
时间Tue Oct 2 22:19:23 2012
有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)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.160.240.173
1F：→ CaptainH:hash table ? 10/02 22:21
2F：→ chunhsiang:有个疑问是运算顺序是否会影响效率? 10/02 22:32
3F：→ chunhsiang:如果会 那是否存在一个最好的顺序? 10/02 22:32
4F：→ chunhsiang:还是说会随资料内容不同而有所不同 10/02 22:33
5F：→ chunhsiang:如果会随资料改变 那平均最佳的选法是否存在? 10/02 22:36
※ 编辑: chunhsiang 来自: 118.160.240.173 (10/02 22:36)
6F：推 EdisonX:我想到用 bitwise...这效率应该是超高,不过会受限就是了. 10/02 22:54
7F：→ chunhsiang:您是说将原本的set转为01的型式再作运算? 但宇集很大 10/02 22:59
8F：推 EdisonX:bitwise 在意的是,set 是否为整数,及其最大、最小值 10/02 23:00
9F：→ aceldama:用java的话, 请爱用utils.MultiKeyMap 10/12 05:18