--- The hyper sequencer ---
( Click to English light version )
クイックソートは高性能で、世界的にも広く普及しています。
特定の条件がそろっているときは、クイックソートよりも高速なソート技法もあります。しかし、条件に関係なく、一般的に幅広く使えるソート法としてはクイックソートは世界最速であり、50 年以上にわたって世界中で広く使われている実績を持ちます。
ソートと言えばクイックソート。プログラミングの世界では、定番です。
ところが、人間の欲望にはきりがなくて、クイックソートを使っているにもかかわらず、遅くてイライラすることもあったりします。わがままな動物ですよね。
ただ、クイックソートには弱点があります。処理が極めて遅くなるデータ列があるということ。
♪ドレミファソートは、そのあたりの問題が解決できないかなぁと、筆者が約１か月の時間をかけて改造しまくって生み出した、クイックソートよりも速く動作し、メディアンキラーなどのデータ列に負けない高速性能を持ちあわせた高速ソート技法です。最初の「♪」も名前です。
♪ドレミファソートは、クイックソートよりも高速に動きますから、一般向け用途として、世界最速のソート技法と言えるでしょう。
なぜなら、その正体もクイックソートですから。
レコードの仕様などは、このサイトの最初の方にある、caution（注意書き）を参照してください。
win32 環境で実行させた例。レコード数５千万件、数値の単位はミリ秒。レコード長は８バイト。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer qsort(VC) 12027.68 12012.08 6801.64 6739.24 3369.62 3572.42 280.80 20358.13 QuickSort(VC) 5881.24 5881.24 3837.62 3837.62 1170.01 1185.61 1575.61 6021.64 QuickSort2(VC) 5740.84 5725.24 3822.02 3853.22 1014.01 1029.61 1560.01 5834.44 QuickSortP(VC) 5522.44 5538.04 3603.62 3634.82 1014.01 1014.01 1357.21 5709.64 DoReMiFaSort(VC) 4648.83 4633.23 2730.02 2714.42 748.80 764.40 31.20 1950.01
この数値を、クイックソートの速度を 100% としたときの比率に書き直すと、
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer qsort(VC) 204.51 204.24 177.24 175.61 288.00 301.32 17.82 338.08 QuickSort(VC) 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 QuickSort2(VC) 97.61 97.35 99.59 100.41 86.67 86.84 99.01 96.89 QuickSortP(VC) 93.90 94.16 93.90 94.72 86.67 85.53 86.14 94.82 DoReMiFaSort(VC) 79.05 78.78 71.14 70.73 64.00 64.47 1.98 32.38
クイックソートが苦手とするメディアンキラーのデーターも、速く処理されています。
同じように、x64 版の実行速度の時間を掲載すると、（レコード長は 16 バイト）
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer qsort(VC) 11980.88 11980.88 6848.44 6817.24 3229.22 3525.62 265.20 20935.33 QuickSort(VC) 6255.64 6255.64 4258.83 4258.83 1341.61 1404.01 2012.41 7534.85 QuickSort2(VC) 6068.44 6068.44 4212.03 4227.63 1232.41 1294.81 1981.21 7425.65 QuickSortP(VC) 5460.04 5444.43 3666.02 3697.22 1185.61 1216.81 1669.21 7160.45 DoReMiFaSort(VC) 4820.43 4820.43 2854.82 2854.82 951.61 982.81 78.00 2308.81
比率は次のようになります。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer qsort(VC) 191.52 191.52 160.81 160.07 240.70 251.11 13.18 277.85 QuickSort(VC) 100.00 100.00 100.00 100.00 100.00 100.00 100.00 100.00 QuickSort2(VC) 97.01 97.01 98.90 99.27 91.86 92.22 98.45 98.55 QuickSortP(VC) 87.28 87.03 86.08 86.81 88.37 86.67 82.95 95.03 DoReMiFaSort(VC) 77.06 77.06 67.03 67.03 70.93 70.00 3.88 30.64
♪ドレミファソートの正体はクイックソートと表現しましたが、実際には Quick3 ソートと呼ばれる技法がベースです。これは、 3 way partition とか、3 way segmentation などと呼ばれる技法です。言葉は難しいのですが、ピボットよりも小さなデータ、ピボットと同一キーを持つデータ、ピボットより大きなデータの３つに分離する方法です。
えぇっ、普通のクイックソートもそうじゃないの？ と考えてしまいますが、普通のクイックソートでは、ピボットと同じ値のキーを持つデータが複数あるとき、ピボットよりも小さいはずのグループにも、ピボットよりも大きいはずのグループにも両方に存在します。正確には両方に存在することもありますと表現するのが正解ですが。
でも、重複値が無いデータだったら、ピボットは１個しかない。そんなデータにも余計な if 文やスワップ処理をやると、逆に遅くなるんじゃないの？ という考え方もあります。重複値がある場合でも、ピボットデータだらけというケースは少なくて、せいぜい数個ということが多いはずです。ですから、Quick3 の技法は発表されてはいるものの、イマイチ人気が無いというのが正直な実体かもしれません。
一方で筆者は速い方法を求めていろいろなテストを行いました。クイックソートだけではなく、他の方法や、自分で見つけた独自の方法なども含まれます。XMM レジスターを効果的に使えないかとか、L1 キャッシュを積極的に利用できないかなど、項目は多岐にわたります。マルチピボットで、ピボットを３個にすれば、5% 程度高速化が期待できるという面白くもない論文も読んだものです。しかし、どうやってもクイックソートをベースにするのが転送回数も少なくて済み、最も高速になるという結論になろうとしていました。
ただし条件があって、データ分離後の比率が 50% に近いことと、１個でも少ない範囲で呼び出せれば、その後の呼び出し回数も大幅に減るので処理が速くなるという結論でした。
50% の比率に近くなるかどうかは、データの並びに由来しますから、ある意味では運もあることでしょう。ただ、ピボットの選び方を工夫することで、わずかばかりの努力はできそうですが。
ところが、「１個でも少ない範囲で呼び出せれば」という内容は、Quick3 を使うと実現できます。通常のクイックソートでは、ソースの書き方によってはピボットのデータも次回のソートデータとして範囲に含まれます。ですが、Quick3 を使うと、ピボットのデータをはずした範囲で呼出しをかけられますから、まさにぴったりの条件です。ただしそれを実現するには、原作の Quick3 に、ちょっとだけ工夫が必要になります。
そんな Quick3 でも、やはりメディアンキラーは苦手なデータで、処理速度が大幅に遅くなってしまいます。
そこで、２つの問題を同時に解決するために考案したのが、タイトルの名前にもなっている、ドレミファソート技法です。これは、ピボットを選ぶとき、３か所から中央の値を採用するのではなく、５か所の値から中央値を採用します。このとき、５か所の中から中央の値を単純に選ぶのではなく、故意に5か所をソートします。
この故意にソートすることで、メディアンキラーのようなデータ列でも無効にし、自分の処理に都合の良い状態に変えることができます。
この特定の５か所（任意の場所ではありません）を、A、B、C、D、E と名前を付けてもいいんですが、あまりに味気がない。そこで、「ド」「レ」「ミ」「ファ」「ソ」という名前を付けたというのが名前の由来です。ただし、５か所全部を完全にソートしているのではなく、最後の「ド」と「レ」は省略して高速化しています。中央値は必ず「ミ」の位置にありますから、その値をピボットとして採用しているわけです。個人的には、「ドミソセレクター」と呼んでいます。「ドミソ」は３度と５度の和音の基本ですし。関係ないか。
処理系によっては、９個の候補の中から中央の値を選ぶこともやっているようですが、９個も事前処理をやると、さすがにオーバーヘッドが大きすぎて遅くなってしまいます。５個がちょうどよい速さになりました。
これだけでは、ピボットデータを含まない範囲で次回の呼出しを行う部分はまだ解決していません。Quick3 の原本のままでは、重複ピボットがあるとき、ちょっとだけ処理効率が低下する部分が含まれています。
そこで、Quick3 の処理をする前に、重複データの連続性の範囲を確認し、もしピボット位置の隣の値もピボット値であれば、ピボットの範囲をあらかじめ広げておきます。こうすることで、最終的にきれいな 3 way partition が出来上がります。同時に、重複データが多いデータをソートしているとき、大量の重複データを発見した時はすみやかに処理を中断させる効果があります。VC++ だと、たった１つの while 文のブロック。
Forward データなどは、並べ替える必要がありません。ですから、クイックソートでも、♪ドレミファソートでも、同じ処理速度になるはずです。しかも、♪ドレミファソートは冒頭で余計な処理をやっていることになるので、本来ならクイックソートより遅くなることになります。ところが、実際はクイックソートよりも速く終了します。このあたりの処理に、影響を出しています。もちろん、ハイブリッド構成の効果もありますが。レコード数が多いときは、ピボットより小さな範囲とピボットより大きな範囲をきちんと分離するだけで、性能が変わるということです。たった１個のピボットでも、次回の処理に含めるのか、次回の処理から外すのかという意味になります。
クイックソートでは、ピボットデータそのものを次回の整列範囲に含める。
（ピボットの座席指定が無いので、どこに格納されているかわからないから）
+0 +1 +2 +3 +4 +5 +6 +7 +8 +9 small small small large pivot large large pivot large large // next calling procedure:
Quick( Array, 0, 2 );
Quick( Array, 3, 9 ); // with 2 pivot♪ドレミファソートでは、ピボットデータは、次回の整列範囲から確実にはずす。
（ピボットの座席指定をしている）（仮定）ピボットの格納位置が正確であれば、ピボットデータは次回の範囲に含める必要がない。
なぜなら、ピボットより小さい範囲と、大きい範囲だけを次回の依頼に回せば良いから。
+0 +1 +2 +3 +4 +5 +6 +7 +8 +9 small small small pivot pivot large large large large large // next calling procedure:
Quick( Array, 0, 2 );
Quick( Array, 5, 9 ); // lost 2 pivot ( Intention )例えば、100 件のレコードで重複データが無いとき、おおむね中心で分離されたとする。
クイックソートの2回目の処理範囲合計は、 50 + 50 の 100 件になり、もともとの依頼レコード数と同じになる。
処理が進んで、呼出しの範囲がどんなに小さな範囲になっても、処理範囲の合計は 100 件のまま。これに対し、♪ドレミファソートの２回目の処理範囲の合計は、49 + 50 の 99 件になり、１件お得
３回目になると、処理範囲の合計は 97 件になり、３件お得
つまり、処理が進めば進むほど、処理対象外の数がどんどん増えていく。
重複データで、pivot の数が多いときは、次回の呼出し範囲は更に狭くなり、好都合。
メディアンキラーは重複データなので、むしろ高速処理が可能な大好物になる。
レコード数が多いときは、この後何千万回コールされるかわからない。
しかし、♪ドレミファソートのピボットは一度対象範囲から外すと、最後の最後まで範囲に含まれない。
対象外の数が、処理が進めば進むほど、どんどん増える。
これを、仮定の条件から、本物に変えれば良いだけのお話。
理論は大変簡単だが、実装がものすごく難しい。ピボットを正確な位置に、高速に移動させる必要がある。
高速に移動しなければ、ここまでの苦労は水の泡。意味がなくなる。何としても高速性を守る。Quck3 は、この理論に基づいて設計しているはずだが、実装が不完全なので、希望どおりにはならない。
Quick3 のデータの動きに、ほんのちょっとだけ改造すれば、それが手に入る！！！
などと、書いていますが、実は答えは簡単です。
ピボットよりも小さなグループと、ピボットよりも大きなグループの２つに分け、それぞれの範囲を処理すればよいという理論は、実はクイックソートの本来の理想論そのものです。
ところが、理想はきれいだけれど、実装するとなると、あーだこーだと、余計な処理の記述を入れなければならない。
余計な処理を入れると、せっかくの高速性が失われてしまう。だから、これ以上余計なことはやらない ― と、途中であきらめてしまっていただけの話です。「遅くなるに違いない」という判断は、実際にやってみた判断だったのか、机上の理論で終わらせたのか。
結局のところ、これまで使っていたクイックソートは、クイックソートの本来の理想ではない動きをしていたソースリストを使っていただけのことになります。クイックソートの理論に限りなく近いけれど、どこかで理論を満たしていない部分があった。そう考えると、ちょっと残念。ただ、ソースリストが短くて済むという効果はありますけどね。視覚的にもそうですし、少ないレジスタ変数で OK という意味もあります。
つまりは、クイックソートの理想の理論どおりに動くソートが、50 年以上経って、ようやく出てきたという話になります。そのようやく出てきたクイックソートに、独特のピボットセレクターを加えているものが、♪ドレミファソートなんです。世界中で研究されているはずなのに、何故かこれまでは登場しなかったんです。何とも不思議です。
Quick3 が、最後の最後でひとひねりしてあれば、その時点で世界最速のソートになっていたはずですし、クイックソートの理論を完全に踏襲した手法として注目されていたはずです。惜しい！ Quick3
たぶん、Quick3 の作者さんは、時間が無かったので、処理が中途半端になったと思います。
データ処理の流れ：
ピボットセレクター → ピボットレンジアジャスター → Quick3
高速処理の工夫は、これ以外にも小さな部分でも行っています。例えば、順方向スキャン、逆方向スキャンのあと、左右のスワップ処理を行ってから、ピボットの値かどうかを判定する部分があります。これはQuick3 のもともとのソースがそうなっているという理由で採用しているのではなく、高速化を考えた上でこの方法を採用しています。
スワップして書き込んでからもう一度ピボットの値と比較するくらいだったら、スワップする前にピボットの値と比較すれば、スワップ行為をしなくても良いから、その方が速いんじゃないか？ と考えてしまいがちです。MS-DOS 全盛期の頃のマイクロプロセッサだったらそうでしょう。ですが、時代は変わっています。バブルソートのところで、「値を書き込んでいるために L1 キャッシュにデータがあるので、そのあとの処理も速くなる現象がある」と書きましたが、まさにこの現象がここでも起きているわけです。無駄とも思える先行書き込み行為は、L1 キャッシュにデータを書き込む行為でもありますから、その後に引き続く処理も高速に行えます。
余談ですが、ピボットより小さなデータと、ピボットより大きなデータが完全に分離されていますから、マルチスレッドで残りを処理しても、アドレスが重なる部分がありえないために、安心してマルチスレッド処理を行うこともできます。もっとも、スレッドを起動する行為自体が体力が必要なので、遅くなることもあります。筆者は個人的に、スレッドを使ってまで高速化はしませんが。
このままの状態でも♪ドレミファソートは速いのですが、レコード数が少なくなったときに、Insertion ソートに切り替えると、約 100ms 程度速くなる傾向があったので、結局 Insertion ソートとのハイブリッド構成にしています。ただし、通常は残り８件とか、16 件の程度で切り替えますが、♪ドレミファソートの処理部分がオーバーヘッドが大きい関係で、切り替えのスレッショルドは 48 件に設定しています。また、Insertion ソートを採用することになったので、本来収録されていた小さなレコード数のときの独自処理などをはずし、ソースリストをすっきりとさせています（いや、十分複雑に見えますが…）。
なお、ソースリストですが、win32 用では再帰コールのオーバーヘッドを少なくするため、自前でスタックを用意する非再帰呼出し型で記述しています。一方で x64 用は、引数がレジスタ渡しという仕様でもあり、再帰コールのままの方が動作速度が速いので、再帰コール型で記述してあります。もし、あなたのシステムが Windows でなければ、両方試してみるのも１つの方法かもしれません。ただ、win32 用のスタック用メモリ確保関数は、malloc 関数ではなく、Windows の HeapAlloc 関数を使っていますので、適切な関数に置き換えてください。また、非再帰型では、if 文を１つ減らすことができます。どこの if 文が少なくなっているか探してみるのも面白いかもしれません。
非再帰型では、スタックの消費レベルが極めて少なくなる特性があります。通常の再帰呼出し型でも、一般のクイックソートよりは、少ない消費量になります。速度も大事だけれど、スタックの消費量をとにかく押さえたいという事情があるときは、非再帰型を使うと、わずか数キロバイトのスタック領域でも十分に高速ソートが実現できます。なぜそうなるのかは、非再帰型のソースリストを、ご自分で解析してみてください。何の変哲もないソースリストの中に、大きな意味を持った内容がかくれんぼしています。
ソースリストは、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理やコピー処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。テスト用ですので、比較用のクイックソートも一緒に収録されています。なお、比較用のクイックソートの再起呼び出し処理は重複レコードがない場合または、重複レコードがあってもごく少数の場合に有効な呼び出し方法で、重複レコードが多数ある場合などの最適化には対応していません。あくまでも基本パターンのソースです。重複レコードが多い可能性がある場合は、呼び出し部分をきちんとコーディングする必要があります。
static void __stdcall SwapUU(void* p1, void* p2)
{
char *c1 = ( char* ) p1, *c2 = ( char* ) p2, cdata;
size_t sztRecLength = sizeof( SortRecStruct );
__m128i XmmTemp;
DWORD dwTemp;
while( sztRecLength >= 16 )
{
XmmTemp = _mm_loadu_si128( ( __m128i* ) c1 );
_mm_storeu_si128( ( __m128i* ) c1, _mm_loadu_si128( ( __m128i* ) c2 ) );
_mm_storeu_si128( ( __m128i* ) c2, XmmTemp );
c1 += 16; c2 += 16; sztRecLength -= 16;
}
if( sztRecLength >= 8 )
{
XmmTemp = _mm_loadl_epi64( ( __m128i* ) c1 );
_mm_storel_epi64( ( __m128i* ) c1, _mm_loadl_epi64( ( __m128i* ) c2 ) );
_mm_storel_epi64( ( __m128i* ) c2, XmmTemp );
c1 += 8; c2 += 8; sztRecLength -= 8;
}
if( sztRecLength >= 4 )
{
dwTemp = *( ( DWORD* ) c1 );
*( ( int* ) c1 ) = *( ( DWORD* ) c2 );
*( ( DWORD* ) c2 ) = dwTemp;
c1 += 4; c2 += 4; sztRecLength -=4;
}
while( sztRecLength-- )
{
cdata = *c1; *c1++ = *c2; *c2++ = cdata;
}
}
static void __stdcall CopyRec(void* pDest, void* pSrc)
{
char *cDest = ( char* ) pDest, *cSrc = ( char* ) pSrc, cdata;
size_t sztRecLength = sizeof( SortRecStruct );
while( sztRecLength >= 16 )
{
_mm_storeu_si128( ( __m128i* ) cDest, _mm_loadu_si128( ( __m128i* ) cSrc ) );
cDest += 16; cSrc += 16; sztRecLength -= 16;
}
if( sztRecLength >= 8 )
{
_mm_storel_epi64( ( __m128i* ) cDest, _mm_loadl_epi64( ( __m128i* ) cSrc ) );
cDest += 8; cSrc += 8; sztRecLength -= 8;
}
if( sztRecLength >= 4 )
{
*( ( int* ) cDest ) = *( ( DWORD* ) cSrc );
cDest += 4; cSrc += 4; sztRecLength -= 4;
}
while( sztRecLength-- )
{
cdata = *cDest; *cDest++ = *cSrc; *cSrc++ = cdata;
}
}
static void __stdcall DualSort(SortRecStruct* p1, SortRecStruct* p2)
{
if( p1->Key > p2->Key )
SwapUU( p1, p2 );
}
static void __stdcall TriSort(SortRecStruct* p1, SortRecStruct* p2, SortRecStruct* p3)
{
DualSort( p1, p2 );
DualSort( p2, p3 );
DualSort( p1, p2 );
}
static void __stdcall InsertionP(SortRecStruct* pTop, SortRecStruct* pBtm)
{
SortRecStruct TempData;
SortRecStruct *ScanPtr, *CopyPtr;
ScanPtr = pBtm - 1;
while( ScanPtr >= pTop )
{
if( ( ScanPtr + 1 )->Key < ScanPtr->Key )
{
CopyRec( &TempData, ScanPtr ); CopyPtr = ScanPtr;
do
{
CopyRec( CopyPtr, CopyPtr + 1 ); CopyPtr++;
}
while( ( CopyPtr < pBtm ) && ( ( CopyPtr + 1 )->Key < TempData.Key ) );
CopyRec( CopyPtr, &TempData );
}
ScanPtr--;
}
}
#ifdef _M_X64
static DWORD __stdcall DoReMiFaSortP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *nPtrL, *nPtrR, *nPivotL, *nPivotR, *nTemp;
SortRecStruct *RecRe, *RecMe, *RecFa;
SortRecStruct Pivot;
if( pBtm > pTop )
{
if( ( pBtm - pTop ) > 48 ) // win32, x64 とも 48 が最速だった。
{
// Do-Re-Mi-Fa-Sort
RecMe = ( pBtm - pTop ) / 2 + pTop; RecRe = ( RecMe - pTop ) / 2 + pTop; RecFa = ( pBtm - RecMe ) / 2 + RecMe;
TriSort( pTop, RecRe, RecMe ); TriSort( RecRe, RecMe, RecFa ); TriSort( RecMe, RecFa, pBtm );
DualSort( pTop, RecRe ); DualSort( RecRe, RecMe );
SwapUU( RecMe, pBtm );
//Pivot = *pBtm;
CopyRec( &Pivot, pBtm );
// adjust pivot range
nPivotR = pBtm;
while( ( nPivotR > pTop ) && ( nPivotR[ -1 ].Key == Pivot.Key ) )
{
nPivotR--;
}
if( nPivotR == pTop ) return 0; // 全レコードが同一データだった。
nPtrR = nPivotR; nPivotL = pTop - 1; nPtrL = pTop - 1;
for( ; ; )
{
while( ( ++nPtrL )->Key < Pivot.Key );
while( Pivot.Key < ( --nPtrR )->Key )
if( nPtrR == pTop ) break;
if( nPtrL >= nPtrR ) break;
SwapUU( nPtrL, nPtrR );
if( nPtrL->Key == Pivot.Key )
{
nPivotL++; SwapUU( nPivotL, nPtrL );
}
if( Pivot.Key == nPtrR->Key )
{
nPivotR--; SwapUU( nPtrR, nPivotR );
}
}
SwapUU( nPtrL, pBtm ); nPtrR = nPtrL - 1; nPtrL = nPtrL + 1;
for( nTemp = pTop; nTemp <= nPivotL; nTemp++, nPtrR-- )
{
SwapUU( nTemp, nPtrR );
}
for( nTemp = pBtm - 1; nTemp >= nPivotR; nTemp--, nPtrL++ )
{
SwapUU( nPtrL, nTemp );
}
if( *pAbort ) return 1223;
if( nPtrR > pTop )
DoReMiFaSortP( pTop, nPtrR, pAbort );
if( nPtrL < pBtm )
DoReMiFaSortP( nPtrL, pBtm, pAbort );
}
else
{
InsertionP( pTop, pBtm );
}
}
return 0;
}
DWORD __stdcall DoReMiFaSort(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
DWORD dwResult = 0;
if( pRecCount > 1 )
dwResult = DoReMiFaSortP( pArray, &pArray[ pRecCount - 1 ], pAbort );
return dwResult;
}
#else
DWORD __stdcall DoReMiFaSort(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
struct QuickStackStruct
{
SortRecStruct *Top, *Btm;
};
QuickStackStruct *Stack;
HANDLE hStack;
size_t StackPtr = 0;
SortRecStruct *nPtrL, *nPtrR, *nPivotL, *nPivotR, *nTemp, *pTop, *pBtm;
SortRecStruct *RecRe, *RecMe, *RecFa;
SortRecStruct Pivot;
DWORD dwResult = 0;
if( pRecCount > 1 )
{
hStack = HeapCreate( 0, 0, 0 );
Stack = ( QuickStackStruct* ) HeapAlloc( hStack, 0, sizeof( QuickStackStruct ) * sizeof( size_t ) * 512 );
if( Stack )
{
Stack[ StackPtr ].Top = pArray; Stack[ StackPtr ].Btm = &pArray[ pRecCount - 1 ];
//
do
{
pTop = Stack[ StackPtr ].Top; pBtm = Stack[ StackPtr ].Btm;
if( ( pBtm - pTop ) > 48 ) // win32, x64 とも 48 が最速だった。
{
// Do-Re-Mi-Fa-Sort
RecMe = ( pBtm - pTop ) / 2 + pTop;
RecRe = ( RecMe - pTop ) / 2 + pTop; RecFa = ( pBtm - RecMe ) / 2 + RecMe;
TriSort( pTop, RecRe, RecMe ); TriSort( RecRe, RecMe, RecFa ); TriSort( RecMe, RecFa, pBtm );
DualSort( pTop, RecRe ); DualSort( RecRe, RecMe );
SwapUU( RecMe, pBtm );
//Pivot = *pBtm;
CopyRec( &Pivot, pBtm );
// adjust pivot range
nPivotR = pBtm;
while( ( nPivotR > pTop ) && ( nPivotR[ -1 ].Key == Pivot.Key ) )
{
nPivotR--;
}
if( nPivotR == pTop )
{
goto IncStack;
}
nPtrR = nPivotR; nPivotL = pTop - 1; nPtrL = pTop - 1;
for( ; ; )
{
while( ( ++nPtrL )->Key < Pivot.Key );
while( Pivot.Key < ( --nPtrR )->Key )
if( nPtrR == pTop ) break;
if( nPtrL >= nPtrR ) break;
SwapUU( nPtrL, nPtrR );
if( nPtrL->Key == Pivot.Key )
{
nPivotL++; SwapUU( nPivotL, nPtrL );
}
if( Pivot.Key == nPtrR->Key )
{
nPivotR--; SwapUU( nPtrR, nPivotR );
}
}
SwapUU( nPtrL, pBtm ); nPtrR = nPtrL - 1; nPtrL = nPtrL + 1;
for( nTemp = pTop; nTemp <= nPivotL; nTemp++, nPtrR-- )
{
SwapUU( nTemp, nPtrR );
}
for( nTemp = pBtm - 1; nTemp >= nPivotR; nTemp--, nPtrL++ )
{
SwapUU( nPtrL, nTemp );
}
StackPtr--;
if( nPtrL < pBtm )
{
//DoReMiFaSortP( nPtrL, pBtm, pAbort );
StackPtr++; Stack[ StackPtr ].Top = nPtrL; Stack[ StackPtr ].Btm = pBtm;
}
if( nPtrR > pTop )
{
//DoReMiFaSortP( pTop, nPtrR, pAbort );
StackPtr++; Stack[ StackPtr ].Top = pTop; Stack[ StackPtr ].Btm = nPtrR;
}
}
else
{
InsertionP( pTop, pBtm );
IncStack:
StackPtr--;
}
CheckStack:
if( *pAbort )
{
dwResult = 1223; break;
}
}
while( StackPtr != ( size_t ) -1 );
HeapFree( hStack, 0, Stack ); HeapDestroy( hStack );
}
else
{
dwResult = 8;
}
}
return dwResult;
}
#endif
あくまで、汎用ソートとしての高速性についてこれまで記述してきました。
もっとも、このテストデータの形式は、キーが符号なし 32 ビットと決まっていますから、その場合は MSD radix ソートなど、専用ソートが使えることにもなります。専用設計できるようであれば、もちろん考えるべきです。ただ、レコード長が大きいときは、メモ書きを利用するタイプのソートは思ったほどには速度が上がらないことが多いです。マルチスレッドが使える環境なら、♪ドレミファソートの初段が終わったら、スレッドで２つに分離したほうが速くなることが多いです。シングルコアの CPU がまだまだ健在なので、あまりお勧めしませんが。
win32 での実行例（単位はミリ秒）
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer DoReMiFaSort(VC) 4648.83 4633.23 2730.02 2714.42 748.80 764.40 31.20 1950.01 MSD radix(VC) 2964.02 2979.62 889.21 873.61 1170.01 1404.01 655.20 1513.21
x64 での実行例（単位はミリ秒）
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer DoReMiFaSort(VC) 4820.43 4820.43 2854.82 2854.82 951.61 982.81 78.00 2308.81 ByteScan B(VC) 3806.42 3806.42 1326.01 1357.21 1606.81 1794.01 764.40 1887.61
マルチチャネルメモリの環境で、スレッドを４段にしてみると実行速度は基本的なクイックソートロジックの場合の半分以下にまで短縮できます。
Copyright (C) 2013 BlackCat.
突然ですが、フロントホックのブラジャーって、どういうのか知っていますか?
男性に聞くと、「前ではずすヤツ」と答えます。
女性に聞くと、「前で止めるヤツ」と答えます。
同じ答えになりませんでした。固定観念を持っていると、広い視野から物事を見ることができなくなります。それにしても、男どもは普段から何を考えているのか。
固定観念を持たず、机上の理論ではなく、実際に試して結論を出す。でも、その結論はその時に使ったコンパイラとそのときに使ったプロセッサでの答えであって、すべての結論ではない。たった１つの結論で、世の中すべてそうだと勘違いしてはいけない。
遅くなったなら、遅くなった原因をしっかりと把握。速くなったなら速くなった原因をしっかりと把握。それを繰り返して成長していく。
それがモノ作りの基本ではないですかね？ アイディアを実際に形にするのが技術屋の醍醐味じゃないですかね？ その技術を他人様が使ったとき、嬉しそうに笑顔を見せてくれれば、最高の喜びじゃないですかね？
このソート技法では、Quick3 によって希望する特性が得られました。
筆者がやったのは、Quick3 の高速性能を実証しただけの話です。
Quick3 を開発し、無償公開されました、Robert Sedgewick さん、Jon Bentley さんに御礼申し上げます。
もちろん、ホーア先生にも。
← Quick Sort ｜ chat →
| contents |
| Top Page caution Bubble Sort Odd Even Sort Cocktail Sort Gnome Sort Selection Sort Min Max Sort Insertion Sort Shell Sort Heap Sort Comb Sort Merge Sort Quick Sort Do-Re-Mi-Fa Sort chat |