- - PR -
C# マージソートの高速化について
1
投稿者 | 投稿内容 | ||||
---|---|---|---|---|---|
|
投稿日時: 2009-01-31 07:11
C#を使い、下のようなコードでマージソートを実現していますが
自分のソフトの中では特にパフォーマンスが要求される部分です。 より高速化するにはどうしたらいいでしょう。 諸先輩方、アドバイスお願い致します //配列のインデックス[n,1]をキーにソート //flipf=true 小さい順に並べる private void mergesort(ref decimal[,] tmp, ref decimal[,] data, int keyindex, int First, int Last, Boolean flipF)//マージソート { int i, j, k, p, mid; if (First < Last) { mid = (int)((First + Last) / 2); mergesort(ref tmp, ref data, keyindex,First, mid, flipF); mergesort(ref tmp, ref data, keyindex, mid + 1, Last, flipF); p = 0; //作業領域のインデックス for (i = First; i <= mid; i++) { tmp[p,0] = data[i,0]; tmp[p,1] = data[i,1]; tmp[p,2] = data[i,2]; p++; } i = mid + 1; j = 0; k = First; while ((i <= Last) && (j < p)) { if ((flipF && (tmp[j, keyindex] > data[i, keyindex])) || (!flipF && (tmp[j, keyindex] < data[i, keyindex]))) { data[k,0] = data[i,0]; data[k, 1] = data[i, 1]; data[k, 2] = data[i, 2]; k++; i++; } else { data[k,0] = tmp[j,0]; data[k, 1] = tmp[j, 1]; data[k, 2] = tmp[j, 2]; k++; j++; } } while (j < p) { data[k,0] = tmp[j,0]; data[k, 1] = tmp[j, 1]; data[k, 2] = tmp[j, 2]; k++; j++; } } } | ||||
|
投稿日時: 2009-01-31 09:41
ソートプログラムを高速化するために最適化を行う場合、
1)実際に運用で使用する予定のデータ件数で実行検証を行う必要がある データ件数がわからないと、どのような最適化が効果的であるか予想できません。 2)元のプログラムでどれ位実行時間が掛かるのか計測してみる。 実際に実行時間を計測し、目標とする実行時間を提示し、最適化方法を模索しないと、 どこまで最適化を進めるべきなのか明確にならない。 3)再帰処理は2重ループに書き直しましょう。 再帰処理を使うとアルゴリズムの実装は簡単になりますが、 2重ループの方が、消費メモリを大幅に節約できます。 2重ループに書き直した方がパフォーマンスも幾分か改善されるでしょう。 (データ件数によっては誤差程度しか高速化しないかもしれません) また、データの特性によってはマージソート以外のアルゴリズム の方が、高速化できるかもしれませんので、こちらも検討の必要があると思います。 また、使用可能メモリの制限が厳しく、マージソートを使用せざるを得ない場合でも、 マージソートと他のソートアルゴリズムを組み合わせる事によって、 高速化を行える場合があります。 (実際に、ソートアルゴリズムを複数組み合わせて、最適化を行う事はよくあります) | ||||
|
投稿日時: 2009-01-31 09:51
ソートというものは、速度は基本的にどのソートアルゴリズムを使うかで決まってしまいます。あとは実装をどうするかだけなのですが、そんなに工夫する余地は残っていません。通常は、標準で付属のライブラリーを使う以外の選択肢はなく、C# でしたら Array.Sort メソッドあたりを使うことになると思います。 提示されたコードはそれより速いのでしょうか?まずはそこから調べられることをお勧めします。 | ||||
|
投稿日時: 2009-02-01 10:22
現在のコードはかなり最適化を進めた結果ですが、
行き詰って、質問させていただきました。 配列のデータ入出力にポインタが使えていないのがネックのように感じています。 >unibonさん Arrayクラスに2次元配列のソートはあるのでしょうか? あれば比較が可能です。もしやり方があれば、ご教示お願い致します。 | ||||
|
投稿日時: 2009-02-01 13:18
私は、よっぽどのことがないかぎり、標準のライブラリーが使うインターフェースに合わせておくほうが良いと思います。すなわち Arrays.Sort や List クラスの Sort メソッドなどに、自分のプログラムを合わせます。 ソートは古典的なものですので、C# も Java もすでに十分洗練されたインターフェースを持っていると私は考えます。 最悪の場合、インターフェースを合わせるために、要素すべてのコピーが必要になるかもしれませんが、メモリーは最大でも今の2倍ほど必要になるだけですし、コピーの速度は O(n) ですので、さほど問題にはならないはずです。(ここで O はいわゆるラージオー。) | ||||
|
投稿日時: 2009-02-02 00:09
ためしに Arrays.Sort を使うサンプルコードを書いてみました。ケアレスミス的なバグはあるかもしれませんが、コピーの手間を入れても、提示されたコード(mergesort)よりも、3割ほど速かったです。
| ||||
|
投稿日時: 2009-02-02 01:28
コンパレーター(じゃなくて .NET だとコンパラー?コンペアラー?)を最適化するともう少し(さっきより1〜2割ほど)速くなるみたいです。
私はこのへんが限界で、あとはそもそも Sort が必要なのか、や、件数を減らせないか、や、ソートは別スレッドで裏で動かすなどのようなことはできないか、などというあたりを検討したほうが良いと思います。 | ||||
|
投稿日時: 2009-02-02 18:40
>>私は、よっぽどのことがないかぎり、標準のライブラリーが使うインターフェースに>>合わせておくほうが良いと思います。 私もこの意見に賛成です。ごちゃごちゃ小細工しても、結局大差ないか遅くなるのがオチのような気がします。 それから、 サンプルコードありがとうございました。大変参考になります。いただいたコードを元に実装テストをしてみます。 |
1