[問題] 多個set作交集

[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)


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.240.173
→ CaptainH:hash table ?
→ chunhsiang:有個疑問是運算順序是否會影響效率?
→ chunhsiang:如果會 那是否存在一個最好的順序?
→ chunhsiang:還是說會隨資料內容不同而有所不同
→ chunhsiang:如果會隨資料改變 那平均最佳的選法是否存在?
※ 編輯: chunhsiang      來自: 118.160.240.173      (10/02 22:36)
推 EdisonX:我想到用 bitwise...這效率應該是超高,不過會受限就是了.
→ chunhsiang:您是說將原本的set轉為01的型式再作運算? 但宇集很大
推 EdisonX:bitwise 在意的是,set 是否為整數,及其最大、最小值
→ aceldama:用java的話, 請愛用utils.MultiKeyMap