ヒープソート（heap sort）は、バイナリヒープを利用してソートする方法です。
簡単なプログラムを作って、データ領域のメモリダンプを表示させたままデバッグモードで動かすと、データがくるくると回って見ていて面白いのですが、それは最初だけ。あまりにくるくる回っているので、「どう考えても無駄な動き。もっと腰を落ち着かせなさい」と思ってしまいますが… 腰がないので、落ち着けないみたいです。
バイナリヒープは、データの前側がルート側、後ろ側が子ノード側という構築方法が一般的ですが、この方法は考え方は難しくはありませんが、実装するのが大変難しくなります。
最初の位置決めで、子ノードの位置決めをするとき、データの数が偶数だったらどうしようとか、奇数だったらどうしようと考えることになります。ところが、高速ループの最中にこの判断をしなければならず、クソ真面目に教科書的なヒープを作ろうと思うと if 文ばかり増えて実行速度が落ちます。かといって、多少形が崩れたとしても、一応バイナリヒープのルールを保つ必要があります。
このあたりを、速度を落とさないように、どの程度のことをやるかというのは、作る人によって違います。
せっかくの機会なので、今回は速度向上のために反則技まで使った方法も掲載してみたいと思います。
というかですね、「これが定番！」というのが無いんですよ。ヒープの構築方法が、あまりにも人によって違いすぎます。
結論を先に申しておきますが、いずれにしても、あまりにも遅すぎてとても業務用には使えません。データの「右往左往」の回数と、得られる成果のバランスが悪すぎて、処理効率が悪いのが原因です。蒸気機関車のエネルギー効率と、VVVF 制御の電車のエネルギー効率の違いみたいな感じです。
実行速度は、掲載するとあまりにもかわいそうなので省略します。
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する 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 DualSort(SortRecStruct* p1, SortRecStruct* p2)
{
if( p1->Key > p2->Key )
SwapUU( p1, p2 );
}
static void ShiftDownAB(SortRecStruct* pArray, size_t pTop, size_t pBtm)
{
size_t root, child, unswap;
//input: end represents the limit of how far down the heap to sift.
root = pTop;
while( root * 2 + 1 < pBtm ) // (While the root has at least one child)
{
child = root * 2 + 1; // (root*2 + 1 points to the left child)
unswap = root; // (keeps track of child to swap with)
// (check if root is smaller than left child)
if( pArray[ unswap ].Key < pArray[ child ].Key )
unswap = child;
// (check if right child exists, and if it's bigger than what we're currently swapping with)
//if( child + 1 < pBtm && pArray[ unswap ] < pArray[ child + 1 ] )
if( ( child < pBtm ) && ( pArray[ unswap ].Key < pArray[ child + 1 ].Key ) )
unswap = child + 1;
//(check if we need to swap at all)
if( unswap != root )
{
SwapUU( &pArray[ root ], &pArray[ unswap ] );
root = unswap; // (repeat to continue sifting down the child now)
}
else
break;
}
}
static void siftUp(SortRecStruct *pArray, size_t pTop, size_t pBtm)
{
size_t child, parent;
// input: start represents the limit of how far up the heap to sift.
// end is the node to sift up.
child = pBtm;
while( child > pTop )
{
//parent = ( size_t ) floor( ( child - 1 ) / 2.0 );
parent = ( child - 1 ) / 2;
if( pArray[ parent ].Key < pArray[ child ].Key ) // then (out of max-heap order)
{
SwapUU( &pArray[ parent ], &pArray[ child ] );
child = parent; // (repeat to continue sifting up the parent now)
}
else
return;
}
}
static void HeapifyA(SortRecStruct* pArray, size_t pRecCount)
{
size_t start;
//(start is assigned the index in a of the last parent node)
/*
if( pRecCount & 1 )
start = ( pRecCount ) / 2;
else
start = ( pRecCount - 1 ) / 2;
*/
start = pRecCount / 2 + ( pRecCount & 1 );
//while( start >= 0 )
while( start != ( size_t ) -1 )
{
//( sift down the node at index start to the proper place such that all nodes below
//the start index are in heap order )
ShiftDownAB( pArray, start, pRecCount - 1 );
start = start - 1;
}
//(after sifting down the root all nodes/elements are in heap order)
}
DWORD __stdcall HeapSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
size_t sztPtr;
if( pRecCount > 1 )
{
HeapifyA( pArray, pRecCount );
if( *pAbort ) return 1223;
sztPtr = ( int ) ( pRecCount - 1 ); // in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while( sztPtr > 0 )
{
//(swap the root(maximum value) of the heap with the last element of the heap)
SwapUU( &pArray[ sztPtr ], &pArray[ 0 ] );
//(decrease the size of the heap by one so that the previous max value will stay in its proper placement)
sztPtr = sztPtr - 1;
//(put the heap back in max-heap order)
ShiftDownAB( pArray, 0, sztPtr );
if( *pAbort ) return 1223;
}
DualSort( pArray, &pArray[ 1 ] );
DualSort( &pArray[ pRecCount - 2 ], &pArray[ pRecCount - 1 ] );
}
return 0;
}
static void heapifyB(SortRecStruct* pArray, size_t count)
{
size_t sztPtr;
//(sztPtr is assigned the index of the first (left) child of the root)
sztPtr = 1;
while( sztPtr < count )
{
//(sift up the node at index end to the proper place such that all nodes above the end index are in heap order)
siftUp( pArray, 0, sztPtr );
sztPtr = sztPtr + 1;
}
// (after sifting up the last node all nodes are in heap order)
}
DWORD __stdcall HeapSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
size_t sztPtr;
if( pRecCount > 1 )
{
heapifyB( pArray, pRecCount );
if( *pAbort ) return 1223;
sztPtr = ( int ) ( pRecCount - 1 ); // in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while( sztPtr > 0 )
{
//(swap the root(maximum value) of the heap with the last element of the heap)
SwapUU( &pArray[ sztPtr ], &pArray[ 0 ] );
//(decrease the size of the heap by one so that the previous max value will stay in its proper placement)
sztPtr = sztPtr - 1;
//(put the heap back in max-heap order)
ShiftDownAB( pArray, 0, sztPtr );
if( *pAbort ) return 1223;
}
DualSort( pArray, &pArray[ 1 ] );
DualSort( &pArray[ pRecCount - 2 ], &pArray[ pRecCount - 1 ] );
}
return 0;
}
static void __stdcall ShiftDownC(SortRecStruct* pArray, size_t pRoot, size_t pBtm)
{
size_t sztChild;
sztChild = pRoot * 2;
while( sztChild <= pBtm )
{
if( sztChild != pBtm && pArray[ sztChild ].Key <= pArray[ sztChild + 1 ].Key )
sztChild++;
//
if( pArray[ sztChild ].Key > pArray[ pRoot ].Key )
{
SwapUU( &pArray[ sztChild ], &pArray[ pRoot ] );
pRoot = sztChild; sztChild = pRoot * 2;
}
else
{
break; // = return
}
}
}
static DWORD __stdcall HeapSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
size_t sztPtr, sztCount;
SortRecStruct *nNewArray;
sztCount = pBtm - pTop + 1;
if( sztCount >= 2 )
{
nNewArray = &pArray[ pTop ];
for( sztPtr = sztCount / 2; sztPtr != ( size_t ) -1; sztPtr-- )
{
//ShiftDownC( nNewArray, sztPtr, sztCount - 1 );
ShiftDownC( nNewArray, sztPtr, pBtm );
}
if( *pAbort ) return 1223;
//
for( sztPtr = sztCount - 1; sztPtr >= 1; sztPtr-- )
{
SwapUU( &nNewArray[ 0 ], &nNewArray[ sztPtr ] );
ShiftDownC( nNewArray, 0, sztPtr - 1 );
if( *pAbort ) return 1223;
}
}
return 0;
}
DWORD __stdcall HeapSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return HeapSortCR( pArray, 0, pRecCount - 1, pAbort );
}
Type C の説明にもありますが、ヒープの構築方法で随分と性能が変わりますから、もしかすると、次はあなたがもっと速いヒープ構築法を見つけるかもしれません。せめて、２倍くらい速くなれば、世間でも喜んでくれるかと思いますが…
← Shell Sort ｜ Comb 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 |