Re: [問題] 多個set作交集
看板Prob_Solve (計算數學 Problem Solving)作者Arton0306 (Ar藤)時間12年前 (2012/10/04 01:30)推噓1(1推 0噓 7→)留言8則, 3人參與討論串3/3 (看更多)
※ 引述《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
→
10/05 08:21, , 1F
10/05 08:21, 1F
→
10/05 08:22, , 2F
10/05 08:22, 2F
→
10/05 08:22, , 3F
10/05 08:22, 3F
→
10/05 13:48, , 4F
10/05 13:48, 4F
→
10/05 13:49, , 5F
10/05 13:49, 5F
→
10/05 13:51, , 6F
10/05 13:51, 6F
→
10/05 14:00, , 7F
10/05 14:00, 7F
推
10/05 15:00, , 8F
10/05 15:00, 8F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
