[問題] find second-largest 的平行演算法

看板C_and_CPP作者 (WZXM)時間14年前 (2011/03/30 14:36), 編輯推噓0(0推 0噓 5→)
留言5則, 3人參與, 最新討論串1/2 (看更多)
一個array a[0],...a[n-1] ps：每個element的key可能有相同的 目的：use parallel algorithm 找出second-largest key 目前只有想到用parallel reduction找max的方式來做 找出max之後 回去砍掉此值 然後再跑一次parallel reduction 找max 應該就可以找到second-largest key 不知道版上高手有無其他idea可提供 感激不盡 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.4.180
→
03/30 15:48, , 1F
切成小block 找出各block的1st,2nd(排序或兩次搜尋) 判斷
03/30 15:48, 1F
→
03/30 15:49, , 2F
出global 1st之後再拿該block的2nd與其他block的1st比對?
03/30 15:49, 2F
→
03/30 15:51, , 3F
不過如果資料型態較複雜 move data會有很大的overhead...
03/30 15:51, 3F
→
03/30 16:03, , 4F
不必,先把各段前二大數字收集起來找第二大即可
03/30 16:03, 4F
→
03/31 02:07, , 5F
快排可以找第n大的
03/31 02:07, 5F
‣ 更多 WWWZZZXXXMMM 的文章
文章代碼(AID): #1DaizUZR (C_and_CPP)
‣ 更多 WWWZZZXXXMMM 的文章
文章代碼(AID): #1DaizUZR (C_and_CPP)