作者Arton0306 (Ar藤)
看板Prob_Solve
標題Re: [問題] 多個set作交集
時間Thu Oct 4 01:30:18 2012
※ 引述《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)
利用到順序的話 看看這個方法如何
首先把元素數最少的set 以hash的方式儲存 先稱此hash為H
接著考慮另一個set (若有排列過，那就拿元素數第二少的)
作交集：看哪些有在H中，做個記號，之後刪掉H中沒有被記號的元素，變成H'
再看另一個set，重覆這個步驟，得到H''...
loop 到最後一個hash得到全部set的交集
假設hash表現的不錯 search delete 都O(1)
那就只需O(|S_1|+|S_2|+...|S_n|)
而且做交集的動作會越快，因為hash中的元素越來越少
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.50.130
1F：→ chunhsiang:A = 元素最少的集合 B = 剩下來任意集合 這樣做 10/05 08:21
2F：→ chunhsiang:與 B = 剩下來最大的開始做(第二大) 10/05 08:22
3F：→ chunhsiang:哪個效率會比較好 10/05 08:22
4F：→ Arton0306:從最小的開始是因為要讓一開始的交集就很小 10/05 13:48
5F：→ Arton0306:之後的選擇如果有辦法讓交集快速減少是最好 10/05 13:49
6F：→ Arton0306:如果沒有任何set的額外資訊 理應從小的開始 10/05 13:51
7F：→ chunhsiang:所以? B沒有一定的 A要選最小 10/05 14:00
8F：推 eieio:我覺得這篇的方法比較好 10/05 15:00