作者WWWZZZXXXMMM (WZXM)
看板C_and_CPP
標題[問題] find second-largest 的平行演算法
時間Wed Mar 30 14:36:12 2011
一個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
→ hilorrk:切成小block 找出各block的1st,2nd(排序或兩次搜尋) 判斷 03/30 15:48
→ hilorrk:出global 1st之後再拿該block的2nd與其他block的1st比對? 03/30 15:49
→ hilorrk:不過如果資料型態較複雜 move data會有很大的overhead... 03/30 15:51
→ yauhh:不必,先把各段前二大數字收集起來找第二大即可 03/30 16:03
→ firejox:快排可以找第n大的 03/31 02:07