作者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