シェルソート

　これまで紹介した、バブルソートからインサーションソートまでは、どちらかといえば低速グループになります。低速ですが、ソースリストが短いものが多く、少ないレジスタで動く特徴を持つタイプもあります。手軽に使える便利さというのも良いことです。まるで、原付スクーターと新幹線のようなもので、原付スクーターは間違いなく新幹線より遅いのですが、余計な準備なしにいきなり動き始めますから、短い距離なら新幹線より速く移動できます。

　これから説明するのは、どちらかというと高速グループになります。高速グループのソートだと、テスト用のレコード数 10 万件では、実行速度が速すぎるために計測した速度が「ゼロミリ秒」になってしまいます。

　そこで、これからの高速ソートグループは、レコード数を ５千万件に増やしてテストを行います。

　シェルソート（shell sort）は、インサーションソートをとびとびの間隔で事前に行っておくことで、入れ替えの回数を少なくできるかも（入れ替えられる領域をある程度確保しておく）という発想を持つ技法です。

　インサーションソートからすると、劇的に速度性能が改善されていますから、インサーションソートの改造としては大成功といえるかと思います。

　ただ、シェルソート以外に、もっと速度の速い方法があるので、現実的にはシェルソートを何かの業務で使っているという例は聞いたことがないのですが…　シェルソートの名前は大変有名ですが。

特　徴

• 　インサーションソートよりも、はるかに高速に動作します。
• 　計算する間隔（ギャップ値）によって、性能が左右されます。
• 　最終的にはギャップ値は１で、インサーションソートになります。ですから、インサーションソートを速く実行するため、事前に下ごしらえを行うアクセラレーション操作の部分がシェルソートとも言えます。

実行速度の例

　win32 環境での速度例です。レコード数 ５千万件、レコード長８バイト、数値の単位はミリ秒です。

	Random32	Random32R	Random15	Random15R	Forward	Reverse	Constant	Med Killer
Type A(VC)	17768.51	19437.72	15288.10	16161.70	2090.41	2839.22	2090.41	2932.82

　x64 環境での速度例です。レコード数 ５千万件、レコード長 16 バイト、数値の単位はミリ秒です。

	Random32	Random32R	Random15	Random15R	Forward	Reverse	Constant	Med Killer
Type A(VC)	18891.72	20295.73	16645.31	16988.51	2152.81	2823.62	2121.61	2854.82

　ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。コピー処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。

ShellSort.txt　stdafx.txt

Type A

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; } } #ifdef _M_X64 static size_t sztGapBtm = 41; static size_t sztGap[ 41 ] = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453 , 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413 , 141214768240, 423644304721, 1270932914164, 3812798742493, 11438396227480, 34315188682441 , 102945566047324, 308836698141973, 926510094425920, 2779530283277761, 8338590849833284 , 25015772549499852, 75047317648499552, 225141952945498690, 675425858836496000, 2026277576509488100 , 6078832729528464400, 18236498188585394000 }; #else static size_t sztGapBtm = 20; static size_t sztGap[ 20 ] = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453 , 21523360, 64570081, 193710244, 581130733, 1743392200 }; #endif size_t GetGapPtr(size_t pGap) { size_t sztTop = 0, sztBtm = sztGapBtm, sztMid; for( ; ; ) { sztMid = ( sztBtm - sztTop ) / 2 + sztTop; if( sztGap[ sztMid ] > pGap ) { sztBtm = sztMid; continue; } else if( sztGap[ sztMid ] < pGap ) { if( ( sztTop + 1 ) == sztBtm ) { if( sztGap[ sztBtm ] == pGap ) return sztBtm; else return sztTop; } else sztTop = sztMid; continue; } else return sztMid; } } static DWORD __stdcall ShellSortAR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort) { SortRecStruct TempRec, *NewTbl; size_t sztPtr, sztChkPtr, sztSpan, sztCount, sztGapPtr; NewTbl = pTop; sztCount = pBtm - pTop + 1; sztGapPtr = GetGapPtr( pBtm - pTop + 1 ); sztSpan = sztGap[ sztGapPtr ]; while( sztSpan > 0 ) { for( sztPtr = 0; sztPtr < sztCount; sztPtr++ ) { sztChkPtr = sztPtr; CopyRec( &TempRec, &NewTbl[ sztPtr ] ); while( ( sztChkPtr >= sztSpan ) && ( NewTbl[ sztChkPtr - sztSpan ].Key > TempRec.Key ) ) { NewTbl[ sztChkPtr ] = NewTbl[ sztChkPtr - sztSpan ]; sztChkPtr -= sztSpan; } CopyRec( &NewTbl[ sztChkPtr ], &TempRec ); } if( *pAbort ) return 1223; if( sztSpan != 1 ) sztSpan = sztGap[ --sztGapPtr ]; else sztSpan = 0; // = return } return 0; } DWORD __stdcall ShellSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort) { if( pRecCount > 1 ) return ShellSortAR( pArray, &pArray[ pRecCount - 1 ], pAbort ); else return 0; }

• 　一応、ギャップ値のとり方が最良とされているケースのものです。

　シェルソートでは、ギャップ値の初期値を例えば４と決めつけ、シフト演算でギャップ計算を軽くする方法もあります。その場合は、_BitScanReverse( レコード数 )などを使うと、初期値を速く求められます。

　バリエーションにきりがないので、今回は１種類のみのソースを掲載します。多くの種類を掲載しても、遅いことに変わりがないですし…

ところでギャップ値

　今回のサンプルリストのギャップ値は、過去の研究の成果を純粋に掲載しています。

　ところで過去では、メモリキャッシュはありませんでした。キャッシュが装備されている現在では、本当にこのギャップ値が最適なのか、別の現象があるのかなど、検討の余地はあるんじゃないかと想像します。挑戦してみてはいかがですか？

　例えば、47 個のデータがあったとします。日本の都道府県の数ですね。root( 47 ) は、6.85… となりますから、ギャップ値は符号なし整数型で 6 でも良いわけです。シェルソートのようでもあり、行列ソートでもあり。この 6 を 2 で割ると、3 になります。どんどん整数演算で 2 で割っていきます。3 を 2 で割ると、1.5 で整数型だと 1。しかし、1 は意味がありませんから、１つ前の答え 3 を使います。ギャップ値を 3 にした状態で１回だけ（１回だけというのがミソ）シェルソートというか、飛び飛びインサーションソートを行い、その直後、普通に全データ範囲のインサーションソートを１回だけ行えば、シェルソートとほぼ同性能の効果があります。この場合は 3 * 2 = 6 ですから、最後のインサーションソートの時に最も深いレベルでも、6 未満、最大でも 5 回移動すれば、正規の位置に収まることになります。ただしこの方法は、レコード数が多くなると、当然シェルソートの方が速くなります。飛び飛びソート自身も最適化すると、もっと高速になります。

　いろいろ試してみると良いかと思います。ただ、シェルソート系は、クイックソートの 2 〜 3 倍の実行時間になるので、実用的にはちょっと…　比較回数は、たまにクイックソートより少なくなることもありますが、転送サイズが多いのが最大のネックです。