オッドイーブンソート

 

 英語のままだと、「夫の言い分相当」という、離婚調停でもやっているような泥沼夫婦を連想をしますが…

 日本語版の Wikipedia を見ると、「奇偶転置ソート」と書いてありますが、本当にこんな呼び方の日本語があるのか、筆者は知りません。

 オッドイーブンソート(odd even sort)は、バブルソートを行うに当たり、偶数アドレスをベースに隣どうしの比較と交換をするというプロセスと、奇数アドレスをベースに隣同士の比較交換をするプロセスを交互に繰り返します。こうすると、ソート後の位置まで距離が離れているデーターも、バブルソートに比べれば少しは速く移動する効果があると発想したものじゃないかと、勝手に想像しています。

 結果的にはそれほど速いわけではありません。しかし、固定観念を持たず、実際に試してみてどのような現象や効果が得られるのかを把握するのは大切なことです。速くなったなら速くなった原因を正確に理解し、遅くなったのなら遅くなった原因を正確に把握することで、学習し、新たな課題に取り組んでいけます。

 この技法も処理速度が遅くてとても実用的ではないため、実測値の掲載は省略します。

特 徴

 なお Wikipedia によると、偶数ベースの処理と奇数ベースの処理は同時並行動作できると書いてありますが、実際には両者で同一アドレスをアクセスする可能性があるため、安易にマルチスレッドにするのは危険です。同一アドレスを同時にアクセスしないよう、制御機構を組み込んだ処理が必要になりますが、そのようなハンドシェークを行う方がむしろ時間がかかって速度を落とす原因になることがあります。

 上記マルチスレッドでの同期制御機構は、自分で共有メモリを用意しても良いですし、Windows の Critical Section を使っても良いですし、いろいろな方法があります。しかし、その説明だけでも本1冊が作れるくらいの情報量がありますから、挑戦する人は、専門に解説した記事を別途参照してください。メモリに対して XCHG 命令を使うと特異な動作をして速度も遅くなりますが、その理由もわかるようになるでしょう。

 マルチスレッドで同一アドレスの競合を避けたいのであれば、2分割して1つおきのデータをソートする方法ではなく、4分割してそのうちの2つのブロックを同時並行動作にすることで競合が避けられるという方法もあります。2つのスレッドが終了するのを待合せたら、次は残った別の2つのブロックをソートします。もっとも、その部分で苦労してソースを書くよりは、他のソート技法を試した方が速く問題解決すると思いますが。

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

OddEvenSort.txt stdafx.txt

Type A

static DWORD __stdcall OddEvenSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // reverse scan
size_t sztPtr;
bool bRefresh;

do
{
bRefresh = false;
// section A
for( sztPtr = pBtm; sztPtr > pTop; sztPtr-- )
{
if( pArray[ sztPtr - 1 ].Key > pArray[ sztPtr ].Key )
{
SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] ); bRefresh = true;
}
// sztPtr を2回にわけてデクリメントしている理由を考えてね。
sztPtr--; if( sztPtr <= pTop ) break;
}
// section B
for( sztPtr = pBtm - 1; sztPtr > pTop; sztPtr-- )
{
if( pArray[ sztPtr - 1 ].Key > pArray[ sztPtr ].Key )
{
SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] ); bRefresh = true;
}
// sztPtr を2回にわけてデクリメントしている理由を考えてね。
sztPtr--; if( sztPtr <= pTop ) break;
}
if( *pAbort ) return 1223;
}
while( bRefresh );
return 0;
}

DWORD __stdcall OddEvenSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return OddEvenSortAR( pArray, 0, pRecCount - 1, pAbort );
}

Type B

static DWORD __stdcall OddEvenSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // forward scan
size_t sztPtr;
bool bRefresh;

do
{
bRefresh = false;
// section A
for( sztPtr = pTop; sztPtr < pBtm; sztPtr++ )
{
if( pArray[ sztPtr + 1 ].Key < pArray[ sztPtr ].Key )
{
SwapUU( &pArray[ sztPtr + 1 ], &pArray[ sztPtr ] ); bRefresh = true;
}
// sztPtr を2回にわけてインクリメントしている理由を考えてね。
sztPtr++; if( sztPtr >= pBtm ) break;
}
// section B
for( sztPtr = pTop + 1; sztPtr < pBtm; sztPtr++ )
{
if( pArray[ sztPtr + 1 ].Key < pArray[ sztPtr ].Key )
{
SwapUU( &pArray[ sztPtr + 1 ], &pArray[ sztPtr ] ); bRefresh = true;
}
// sztPtr を2回にわけてインクリメントしている理由を考えてね。
sztPtr++; if( sztPtr >= pBtm ) break;
}
if( *pAbort ) return 1223;
}
while( bRefresh );
return 0;
}

DWORD __stdcall OddEvenSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return OddEvenSortBR( pArray, 0, pRecCount - 1, pAbort );
}

Type C

static DWORD __stdcall OddEvenSortCR(SortRecStruct* pTop, SortRecStruct *pBtm, bool* pAbort)
{ // reverse scan
SortRecStruct *RecPtr;
bool bRefresh;

do
{
bRefresh = false;
// section A
for( RecPtr = pBtm; RecPtr > pTop; RecPtr -= 2 )
{
if( ( RecPtr - 1 )->Key > RecPtr->Key )
{
SwapUU( RecPtr - 1, RecPtr ); bRefresh = true;
}
}
// section B
for( RecPtr = pBtm - 1; RecPtr > pTop; RecPtr -= 2 )
{
if( ( RecPtr - 1 )->Key > RecPtr->Key )
{
SwapUU( RecPtr - 1, RecPtr ); bRefresh = true;
}
}
if( *pAbort ) return 1223;
}
while( bRefresh );
return 0;
}

DWORD __stdcall OddEvenSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return OddEvenSortCR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

Type D

static DWORD __stdcall OddEvenSortDR(SortRecStruct* pTop, SortRecStruct *pBtm, bool* pAbort)
{ // forward scan
SortRecStruct *RecPtr;
bool bRefresh;

do
{
bRefresh = false;
// section A
for( RecPtr = pTop; RecPtr < pBtm; RecPtr += 2 )
{
if( ( RecPtr + 1 )->Key < RecPtr->Key )
{
SwapUU( RecPtr + 1, RecPtr ); bRefresh = true;
}
}
// section B
for( RecPtr = pTop + 1; RecPtr < pBtm; RecPtr += 2 )
{
if( ( RecPtr + 1 )->Key < RecPtr->Key )
{
SwapUU( RecPtr + 1, RecPtr ); bRefresh = true;
}
}
if( *pAbort ) return 1223;
}
while( bRefresh );
return 0;
}

DWORD __stdcall OddEvenSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return OddEvenSortDR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

 ありがちなCコンパイラでは、Type C や Type D のほうが高速になります。あなたのコンパイラではどうなるでしょうか。

注意事項

 このサイトの冒頭でも記事にしていますが、比較の順序を左右逆にすると処理速度が速くなることもあります。いろいろなパターンのうち、どの方法が最良なのかはそれぞれの環境で異なります。


Bubble Sort | Cocktail Sort


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
inserted by FC2 system