Re: [問題] find second-largest 的平行演算法
※ 引述《WWWZZZXXXMMM (WZXM)》之銘言：
: 一個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可提供
: 感激不盡 謝謝
將資料分成幾個段落,每個段落各由一個節點處理. 每個節點找出最大二個數字拋回來,
由中樞節點收集並找出其中第二大的數字.
可以證明給你看: 令陣列數字構成集合 N, 有 l_1, l_2 屬於 N 且 l_1 > l_2 為
N 中最大二個數字. 由 N 取子集合 Z, 並知道 z_1, z_2 屬於 Z 且 z_1 > z_2 為
Z 中最大二個數字. 於是我們知道有下列敘述成立,
對每個屬於 N 的 x, l_1 = x 或 l_2 = x 或 l_2 > x.
對每個屬於 Z 的 x, z_1 = x 或 z_2 = x 或 z_2 > x.
目標是要證明以下二句敘述成立:
對每個屬於 Z 的 x, 若 x = z_1 或 x = z_2, 則 z_1 = l_1 或 z_i = l_2
或 z_i < l_2
對每個屬於 Z 的 x, 若 x 不等於 z_1 也不等於 z_2, 則 x 既不等於 l_1
也不等於 l_2.
如果以上二句可以證實,則你對每個節點處理的片段陣列數字可以相信一件事: 任何
不是頭二個最大數字的數字一定不會是整個陣列的頭二個最大數字.
證明:
1. 因為 z_i 屬於 Z, 且 Z 包含於 N, 所以 z_1 可能等於 l_1 或小於 l_1.
又因為 z_2 < z_1, 所以 z_2 小於 l_1. 且因 l_2 < l_1, z_2 可能等於 l_2 或
小於 l_2.
2. 對每個屬於 Z 的 x, 若 x 不等於 z_1 也不等於 z_2, 則 x < z_2.
又因前一條證明結果, x 既小於 z_2 也小於 l_1, 並且 x 必定小於 l_2,
所以 x 既不等於 l_1 也不等於 l_2.
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.114.217
推
03/30 22:53, , 1F
03/30 22:53, 1F
→
03/31 00:20, , 2F
03/31 00:20, 2F
推
03/31 01:10, , 3F
03/31 01:10, 3F
推
03/31 19:27, , 4F
03/31 19:27, 4F
推
03/31 20:27, , 5F
03/31 20:27, 5F
→
04/01 01:46, , 6F
04/01 01:46, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：