有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)
作者:
CaptainH (Cannon)
0000-00-00 00:00:00hash table ?
作者: chunhsiang (= =) 0000-00-00 00:00:00
有個疑問是運算順序是否會影響效率?如果會 那是否存在一個最好的順序?還是說會隨資料內容不同而有所不同如果會隨資料改變 那平均最佳的選法是否存在?
作者:
EdisonX (卡卡獸)
0000-00-00 00:00:00我想到用 bitwise...這效率應該是超高,不過會受限就是了.
作者: chunhsiang (= =) 0000-00-00 00:00:00
您是說將原本的set轉為01的型式再作運算? 但宇集很大
作者:
EdisonX (卡卡獸)
0000-00-00 00:00:00bitwise 在意的是,set 是否為整數,及其最大、最小值
作者: aceldama (2-4) 0000-00-00 00:00:00
用java的話, 請愛用utils.MultiKeyMap