Re: [問題] 多個set作交集

[EdisonX (閉上眼的魚)]

※ 引述《chunhsiang (= =)》之銘言：
: 假設集合A與B作交集 n=|A| m=|B|
: 只需要O(n+m)

推 EdisonX:我想到用 bitwise...這效率應該是超高,不過會受限就是了.
→ chunhsiang:您是說將原本的set轉為01的型式再作運算? 但宇集很大
推 EdisonX:bitwise 在意的是,set 是否為整數,及其最大、最小值
回文說明較清楚。虛碼部份以 C 大致示之。

假設 A = {200,-1,2,100}, B={-100,-1,200,2}, 不一定要照順序

(1) 先掃 A, B 一遍，紀錄整體最大、最小值，Max, Min  (200, -100)

(2) 如果每個數字都用一個位元表示的話，需要 Max - Min + 1 = 301 bits
    假設一個無號數 (unsigned int ) 佔了 32 bits ，可計算出，
    需要陣列的大小約是 301 / 32 +  1 = 10 <不考慮剛好是32整數bit問題>

     unsigned ASet[10]={0U}, BSet[10]={0U};
     unsigned idx; /*這用來計算到時候放在陣列哪個 idx*/
     unsigned bit; /*這用來計算到時候放在陣列哪個 bit*/

(3) 先 polling A, B

    (3.1) 紀錄 200 : 200-Min=300, idx=300/32 = 9, bit = 300%32=12
                    ASet[idx] |= (1U<<bit);
    (3.2) 紀錄 -1 : -1-Min=99, idx=99/32 = 3, bit =99%32=3
                    ASet[idx] |= (1U<<bit);
    ....

(4) 計算結果 unsigned Rst[10];

    for(i=0; i<10; ++i) Rst[i] = ASet[i] & BSet[i];

最後要輸出的時候再根據 Rst 內容做輸出。

(1) : O(n+m)
(2) : O(1)
(3) : O(n+m)
(4) : O(n+m)

整體應該還算 O(n+m) <吧？>

但如上所見，有幾個缺點

(1) 只適用整數集合
(2) Max-Min 過大的時候就浪費記憶體 <情況不要太偏激的話，記憶體應都還堪用>

非整數、稀疏、範圍大時，可能就不適用。
不知您的情況是？？

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
※ 編輯: EdisonX         來自: 180.177.76.161       (10/02 23:28)
推 ledia:有出現的再安排位置就好啦
推 singlovesong:disjoint set + union by rank + path compression
→ singlovesong:有optimal solution in linear time 喔!
→ singlovesong:可以google 一下
→ chunhsiang:所以說運算先後順序不重要?
→ chunhsiang:disjoint set是集合間都不會有一樣的元素 與全部交集
→ chunhsiang:有何關係... 恕我愚昧一問...能不能白話點...