分岐しないソート

ソートについて

データをソートする場合に、どのアルゴリズムが最速かというのは、実に悩ましい問題である。使われかたの状況や、データの性質等、様々なことを考慮しなければ決めらないし、ソートアルゴリズムをそのまま利用するのではなく、他のアルゴリズムと組み合わせる方がよい場合もある。また、データをあらかじめソートしやすいように前処理を施すなどをするとよいこともある。とはいえ、どんなソートを使うべきか、という何らかの基準はほしいものである。平均的に高速といわれるのはクイックソートである。ただ、この「平均的」というがクセモノで、ソートするデータが決まっている場合、その最速のソート方法はクイックソートでない場合がかなり多い。しかも安定でないという弱点をもつ。以下に、よく知られているソートアルゴリズムを表にしてみた。アルゴリズムの詳細については各自で調べてほしい。

  安定か、否か 実行時間 備考
逆写像ソート 安定 O(n) 作業領域が必要。
分布数えソート 安定 O(n) 作業領域が必要。
ラディックスソート 安定 O(mn) 作業領域が必要。
クイックソート 安定でない O(n log n) 最悪O(n^2)になる場合がある。
ヒープソート 安定でない O(n log n)  
マージソート 安定 O(n log n) 作業領域が必要。
挿入ソート 安定 O(n^2) ほとんどソートされているデータでは非常に高速。
選択ソート 安定 O(n^2)  
バブルソート 安定 O(n^2)  

今日のように、メモリが十分にある場合、まず、O(n)のアルゴリズムを選択できないか考えるのがよいだろう。それが適用できない場合は、データの種類に応じて、クイックソート、マージソート、挿入ソートを使うのがよいようである。あと、ソートする要素のサイズが大きい場合は、その要素へのポインタを作成し、ポインタをソートすると、要素の移動が最小限で済み、高速化できる。

 

少ない要素数の高速ソート

ソート数要素がある程度多い場合(数十から数百以上)は、前述のとおりだが、比較する要素数は少ないが、呼び出される回数が非常に多いために高速性が要求されるような特殊な場合は、状況が変わってくる。オーダの問題はあまり関係なくなり、アルゴリズム自体の処理のオーバーヘッドが問題になってくる。ソートする要素数が4つや5つになると、O(n)やO(n log n)のアルゴリズムより、O(n^2)のアルゴリズムの方が速くなる場合が起きてくる。そういう極限的な状況で最適なソートというものを考えてみる。その答えの一つがバイトニックソートである。そのコードを以下に示す。

このコード片は、小瀬氏がNetNewsに投稿したものを元にしている。
    Newsgroups: fj.comp.lang.c,fj.comp.lang.c++,fj.comp.lang.misc
    Message-ID: <8l1mc5$rv$1@nw042.infoweb.ne.jp>

// 4要素に対するバイトニックソートのコード

#define lswap2(a,b) {t=d[a];d[a]=d[b];d[b]=t;}
#define lswap3(a,b,c) {t=d[a];d[a]=d[b];d[b]=d[c];d[c]=t;}
#define lswap4(p,q,r,s) {t=d[p];d[p]=d[q];d[q]=d[r];d[r]=d[s];d[s]=t;}

void sort4l(unsigned int *d){
    unsigned int t;
    if(d[0]<d[1])if(d[2]<d[3])if(d[0]<d[2])if(d[1]<d[3])if(d[1]<d[2])return;
                    else lswap2(1,2)
                else lswap3(3,1,2)
            else if(d[1]<d[3]) lswap3(1,0,2)
                else if(d[0]<d[3])lswap4(3,1,0,2)
                    else{lswap2(3,1);lswap2(0,2);}
        else if(d[0]<d[3])if(d[1]<d[2])if(d[1]<d[3])lswap2(3,2)
                    else lswap3(1,3,2)
                else lswap2(1,3)
            else if(d[1]<d[2]) lswap4(2,1,0,3)
                else if(d[0]<d[2])lswap3(0,3,1)
                    else lswap4(2,0,3,1)
    else if(d[2]<d[3])if(d[0]<d[3])if(d[1]<d[2])if(d[0]<d[2])lswap2(0,1)
                else lswap3(2,0,1)
            else lswap2(2,0)
        else if(d[1]<d[2]) lswap4(1,2,3,0)
            else if(d[1]<d[3])lswap3(3,0,2)
                else lswap4(1,3,0,2)
    else if(d[0]<d[2])if(d[1]<d[3])if(d[0]<d[3]){lswap2(0,1);lswap2(3,2);}
                else lswap4(0,1,3,2)
            else lswap3(0,3,2)
        else if(d[1]<d[3]) lswap3(1,3,0)
            else if(d[1]<d[2])lswap2(3,0)
                else {lswap2(1,2);lswap2(3,0);}
}

何をやっているのか簡単に説明すると、全要素に対して必要最小限の比較を行った後、最小限の移動回数でデータを一気にソートしているのである。まさに究極のソートに思えるのであるが、この方式には致命的な弱点が存在する。それは分岐するコードが、要素数の階乗というオーダで増加するということである。O(n!)に比べれば、O(n^2)なんて実にかわいらしいものである。4要素で4!=24、5要素で5!=120、6要素で720、7要素で5040、8要素で40320(このあたりでコンパイルできるか怪しくなる)、10要素で3628800、16要素で2.09×10^13、55要素で1.27×10^73(無量大数を突破)・・・行き過ぎた。とにかくこの方式はごく少数の要素にしかつかえないのである。

 

分岐しないソート

ようやく本題である。前述のバイトニックソートは確かに比較回数も移動回数も少ない。が、分岐の仕方はCPU泣かせである。最近のCPUで最適化をするのであれば、パイプライン、分岐予測、キャッシュを考慮しなければならない。そこで、プロセッサ依存ではあるが、分岐をしないソートを作成し、高速化した。

分岐しないソート(32bit, 4要素, PentiumPro以降)の例を以下に示す。

void sort4(unsigned int *d)
{
    __asm{
        mov ebp, d
        mov eax, [ebp]
        mov ebx, [ebp+4]
        mov ecx, [ebp+8]
        mov edx, [ebp+12]

        cmp eax, ebx
        cmova eax, ebx
        cmova ebx, [ebp]

        cmp ecx, edx
        cmova ecx, edx
        cmova edx, [ebp+8]

        mov esi, eax
        cmp eax, ecx
        cmova eax, ecx
        cmova ecx, esi

        mov esi, ebx
        cmp ebx, edx
        cmova ebx, edx
        cmova edx, esi

        mov esi, ebx
        cmp ebx, ecx
        cmova ebx, ecx
        cmova ecx, esi

        mov [ebp], eax
        mov [ebp+4], ebx
        mov [ebp+8], ecx
        mov [ebp+12], edx
    }
}