- 題名: クイックソートの末尾再帰をループに置換する手段
- 日時: 2011/10/23 8:19:09
- ID: 29284
- この記事の返信元:
- （なし）
- この記事への返信:
- [29286] Re[1]: クイックソートの末尾再帰をループに置換する手段2011/10/23 19:25:04
- [29288] Re[1]: クイックソートの末尾再帰をループに置換する手段2011/10/24 10:12:08
- ツリーを表示
DOBON.NETプログラミング掲示板過去ログ
■No29286に返信(itiさんの記事)
おっしゃるとおり実験です。理論の検証ではなくて実際に経験するという意味の実験です。
関数Swapを呼び出さないようにしたところかなり効果がありました。25%ほど速くなりました。
枢軸を選択する関数QuicksortPivotも挿入ソートで並び替えるようにしてSwap関数を
呼ばないようにしました。
static Int32 QuicksortPivot(Int32[] a, Int32 low, Int32 hig) {
var mid = ((hig - low) >> 1) + low;
var t = 0;
if (a[mid] < a[low]) {
t = a[mid];
a[mid] = a[low];
a[low] = t;
}
if (a[hig] < a[mid]) {
if (a[hig] < a[low]) {
t = a[hig];
a[hig] = a[mid];
a[mid] = a[low];
a[low] = t;
} else {
t = a[hig];
a[hig] = a[mid];
a[mid] = t;
}
}
return a[mid];
}
■No29288に返信(itiさんの記事)
unsafeのコードは*がポインタの宣言なのか、掛け算なのか、値なのか、アドレスなのか
私にはよくわかりません。難しそうなので今回は使用を避けようと思いますが、お教え
いただいたコードは後学のために保存しておきたいと思います。ありがとうございます。
全体をループで囲って引数に値を代入することで末尾再帰をループに置き換える
ことができました。処理速度はほとんど変わりませんでした。並び替えを行う配列の
内容によってはスタックオーバーフローが起こる可能性があるのでStackクラスを使う
やり方の方がよさそうですね。もうすこし検証してみます。
static Int32[] QuicksortSort(Int32[] a, Int32 low, Int32 hig) {
var t = 0;
while (low < hig) {
if (QuicksortIsSorted(a, low, hig)) return a;
var v = QuicksortPivot(a, low, hig);
var l = low + 1;
var h = hig - 1;
do {
while (a[l] < v) l++;
while (a[h] > v) h--;
if (l > h) break;
t = a[l];
a[l] = a[h];
a[h] = t;
l++; h--;
} while (true);
if (low < h) QuicksortSort(a, low, h);
low = l;
}
return a;
}
2011/11/03(Thu) 18:54:38 編集(投稿者)
3つの要素の中央値を枢軸に選ぶクイックソートにはキラーシーケンスがあるようで
キラーシーケンスをソートするばあいにマージソートよりも遅くなりました。なので
9つの要素の中央値を枢軸に選ぶようにしました。
要素数が少ないばあいに挿入ソートを行うようにしました。10%ほど速くなりました。
スタックオーバーフローを避けるために要素数が少ない方を再帰で処理して、要素数が
多い方をループで処理するようにしました。
static Int32[] QuicksortSort(Int32[] a, Int32 low, Int32 hig) {
var t = 0;
while (low < hig) {
if (QuicksortIsSorted(a, low, hig)) {
return a;
}
if (hig - low < 10) {
Insertionsort(a, low, hig);
return a;
}
var v = 0;
var l = 0;
var h = 0;
if (hig - low < 32) {
v = QuicksortPivot(a, low, hig);
l = low + 1;
h = hig - 1;
} else {
var step = (hig - low) >> 3;
var mid = ((hig - low) >> 1) + low;
v = Median(
Median(a[low], a[low + step], a[low + step + step]),
Median(a[mid - step], a[mid], a[mid + step]),
Median(a[hig - step - step], a[hig - step], a[hig]));
l = low;
h = hig;
}
while (l < h) {
while (a[l] < v) {
l++;
}
while (a[h] > v) {
h--;
}
if (l > h) {
break;
}
t = a[l];
a[l] = a[h];
a[h] = t;
l++;
h--;
}
if (h - low < hig - l) {
if (low < h) {
QuicksortSort(a, low, h);
}
low = l;
} else {
if (l < hig) {
QuicksortSort(a, l, hig);
}
hig = h;
}
}
return a;
}
分類:[.NET]
Array.Sortよりも速いクイックソートを実装したいです。 ソート済みであれば処理を抜けるようにして、配列の最初の要素と中央の要素と 最後の要素をソートして、中央の要素を枢軸に選ぶようにして、最初から2番目 の要素と最後から2番目の要素から比較するようにしました。 static Int32[] QuicksortSort(Int32[] a, Int32 low, Int32 hig) { if (QuicksortIsSorted(a, low, hig)) return a; var v = QuicksortPivot(a, low, hig); var l = low + 1; var h = hig - 1; do { while (a[l] < v) l++; while (a[h] > v) h--; if (l > h) break; Swap(a, l++, h--); } while (true); if (low < h) QuicksortSort(a, low, h); if (l < hig) QuicksortSort(a, l, hig); return a; } ソート済みの配列やソート済みのものを逆順にした配列をソートするばあいには Array.Sortより速くなりました。しかし、要素の値が一意でランダムにかき混ぜ られた配列ではまだArray.Sortより遅いです。 10000の要素をもつInt32のランダムな配列をソートしたばあいの結果は以下でした。 [Array.Sort] time(ns) : 20001 sorted : True [Quicksort] time(ns) : 50003 sorted : True 末尾再帰をループに置換すれば速くなると思い以下のようにしました。 static Int32[] QuicksortSort(Int32[] a, Int32 low, Int32 hig) { var l = low; var h = hig; do { if (QuicksortIsSorted(a, l, h)) return a; var v = QuicksortPivot(a, l, h); l++; h--; do { while (a[l] < v) l++; while (a[h] > v) h--; if (l > h) break; Swap(a, l++, h--); } while (true); if (low < h) QuicksortSort(a, low, h); h = hig; } while (l < h); return a; } 結果は以下でした。約300倍の時間が掛かるようになりました。解せません。 そしてわかりません。クイックソートの末尾再帰をループに置換する手段を教え てください。あと、他にクイックソートを高速にする方法がありましたらお教え いただけるとありがたいです。よろしくお願いします。 [Array.Sort] time(ns) : 0 sorted : True [Quicksort] time(ns) : 15420034 sorted : True