作者EdisonX (閉上眼的魚)
站內Prob_Solve
標題Re: [問題] 多個set作交集
時間Tue Oct 2 23:23:28 2012
※ 引述《chunhsiang (= =)》之銘言：
: 假設集合A與B作交集 n=|A| m=|B|
: 只需要O(n+m)
1F：推 EdisonX:我想到用 bitwise...這效率應該是超高,不過會受限就是了.10/02 22:54
2F：→ chunhsiang:您是說將原本的set轉為01的型式再作運算? 但宇集很大10/02 22:59
3F：推 EdisonX:bitwise 在意的是,set 是否為整數,及其最大、最小值10/02 23:00
回文說明較清楚。虛碼部份以 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)
4F：推 ledia:有出現的再安排位置就好啦 10/03 00:36
5F：推 singlovesong:disjoint set + union by rank + path compression 10/03 11:44
6F：→ singlovesong:有optimal solution in linear time 喔! 10/03 11:44
7F：→ singlovesong:可以google 一下 10/03 11:44
8F：→ chunhsiang:所以說運算先後順序不重要? 10/03 15:09
9F：→ chunhsiang:disjoint set是集合間都不會有一樣的元素 與全部交集 10/03 15:17
10F：→ chunhsiang:有何關係... 恕我愚昧一問...能不能白話點... 10/03 15:19