それだけの価値があるリンクされたリストの並列ソートを行うアルゴリズムはありますか?
マージ ソートがリンク リストのソートに使用する最適なアルゴリズムであることはよく知られています。
ほとんどのマージ ソートは、各半分が再帰的にソートされる配列の観点から説明されています。これにより、並列化が簡単になります。各半分を個別にソートしてから、2 つの半分をマージします。
しかし、リンクされたリストには「中間」ポイントがありません。リンクされたリストは最後まで続く：
頭 → [a] → [b] → [c] → [d] → [e] → [f] → [g] → [h] → [i] → [j] → ...
私が今持っている実装は、リストを一度歩いてカウントを取得し、ノードをそれと比較するまでカウントを再帰的に分割しますNextNode。再帰は、2 つの半分がどこにあるかを記憶するように処理します。
これは、リンクされたリストの MergeSort がリストを直線的に進むことを意味します。リストを直線的に進める必要があるように見えるので、並列化できないと思います。私が想像できる唯一の方法は、次のとおりです。
- リストをたどってカウントを取得する
O(n) - 中間点に到達するためにリストの半分を歩く
O(n/2) - 次に、各半分を並べ替えます
O(n log n)
しかし、(a,b) と (c,d) の並べ替えを別のスレッドNextNodeで並列化したとしても、並べ替え中の誤った共有によって並列化の利点が失われると思います。
リンクされたリストをソートするための並列アルゴリズムはありますか?
配列マージソートアルゴリズム
配列に対してマージソートを実行するための標準アルゴリズムは次のとおりです。
algorithm Merge-Sort
input:
an array, A (the values to be sorted)
an integer, p (the lower bound of the values to be sorted)
an integer, r (the upper bound of the values to be sorted)
define variables:
an integer, q (the midpoint of the values to be sorted)
q ← ⌊(p+r)/2⌋
Merge-Sort(A, p, q) //sort the lower half
Merge-Sort(A, q+1, r) //sort the upper half
Merge(A, p, q, r)
このアルゴリズムは、任意のインデックス アクセスを使用して、配列用に設計され、意図されています。リンクされたリストに適したものにするには、変更する必要があります。
リンク リスト マージ ソート アルゴリズム
これは、（シングルスレッド）単一リンクリスト、マージソート、単一リンクリストをソートするために現在使用しているアルゴリズムです。これは、Gonnet + Baeza Yates Handbook of Algorithmsから来ています。
algorithm sort:
input:
a reference to a list, r (pointer to the first item in the linked list)
an integer, n (the number of items to be sorted)
output:
a reference to a list (pointer to the sorted list)
define variables:
a reference to a list, A (pointer to the sorted top half of the list)
a reference to a list, B (pointer to the sorted bottom half of the list)
a reference to a list, temp (temporary variable used to swap)
if r = nil then
return nil
if n > 1 then
A ← sort(r, ⌊n/2⌋ )
B ← sort(r, ⌊(n+1)/2⌋ )
return merge( A, B )
temp ← r
r ← r.next
temp.next ← nil
return temp
Pascalの実装は次のようになります。
function MergeSort(var r: list; n: integer): list;
begin
if r = nil then
Result := nil
else if n > 1 then
Result := Merge(MergeSort(r, n div 2), MergeSort(r, (n+1) div 2) )
else
begin
Result := r;
r := r.next;
Result.next := nil;
end
end;
トランスコーディングが機能する場合は、オンザフライの C# 変換を次に示します。
list function MergeSort(ref list r, Int32 n)
{
if (r == null)
return null;
if (n > 1)
{
list A = MergeSort(r, n / 2);
list B = MergeSort(r, (n+1) / 2);
return Merge(A, B);
}
else
{
list temp = r;
r = r.next;
temp.next = null;
return temp;
}
}
私が今必要としているのは、リンクされたリストをソートするための並列アルゴリズムです。マージソートである必要はありません。
n個のアイテムが単一のキャッシュラインに収まる次のn 個のアイテムをコピーし、それらを使用してタスクを生成することを提案する人もいます。
サンプルデータ
algorithm GenerateSampleData
input:
an integer, n (the number of items to generate in the linked list)
output:
a reference to a node (the head of the linked list of random data to be sorted)
define variables:
a reference to a node, head (the returned head)
a reference to a node, item (an item in the linked list)
an integer, i (a counter)
head ← new node
item ← head
for i ← 1 to n do
item.value ← Random()
item.next ← new node
item ← item.next
return head
したがって、次のように呼び出して、300,000 個のランダムなアイテムのリストを生成できます。
head := GenerateSampleData(300000);
ベンチマーク
Time to generate 300,000 items 568 ms
MergeSort
count splitting variation 3,888 ms (baseline)
MergeSort
Slow-Fast midpoint finding 3,920 ms (0.8% slower)
QuickSort
Copy linked list to array 4 ms
Quicksort array 5,609 ms
Relink list 5 ms
Total 5,625 ms (44% slower)
ボーナスリーディング
- Stackoverflow:リンクされたリストをソートするための最速のアルゴリズムは何ですか?
- Stackoverflow:リンクされたリストのマージソート
- リンクされたリストのマージソート
- Parallel Merge Sort
O(log n)pdf、1986 - Stackoverflow: Parallel Merge Sort (クローズド、典型的な SO オタクの怒りのやり方)
- 並列マージソート Dr. Dobbs、2012 年 3 月 24 日
- 虚偽の共有を排除 Dr. Dobbs、2009 年 3 月 14 日
