てきとうなメモ

本の感想とか技術メモとか

Perlのstable quicksort

stableなquicksortないかなと思っていろいろ探していたらPerlのquicksortがstableな実装だった.

perl5.10.0のpp_sort.cより引用.

Perlのquicksortについては以下のようなデータ構造を利用している.

  indir                  list1
 +----+                 +----+
 |    | --------------> |    | ------> first element to be sorted
 +----+                 +----+
 |    | --------------> |    | ------> second element to be sorted
 +----+                 +----+
 |    | --------------> |    | ------> third element to be sorted
 +----+                 +----+
  ...
 +----+                 +----+
 |    | --------------> |    | ------> n-1st element to be sorted
 +----+                 +----+
 |    | --------------> |    | ------> n-th element to be sorted
 +----+                 +----+

list1がソートしたい配列でindirというのはlist1の各要素を指すポインタの配列.ソートする時にlist1をソートするのではなくindirの方をindirのi番目の要素がi番目になるべきデータを指すlist1要素のアドレスを指すようにソートする.で,ソート時に値の比較で等しい場合はポインタの値を比較することで同じ値のものの順序を保っている.

STATIC void
S_qsortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp, U32 flags)
{
    dVAR;
    if ((flags & SORTf_STABLE) != 0) {
         ...
         PL_sort_RealCmp = cmp; /* Put comparison routine where cmpindir can find it */

         /* sort, with indirection */
         if (flags & SORTf_DESC)
            qsortsvu((gptr *)indir, nmemb, cmpindir_desc);
         else
            qsortsvu((gptr *)indir, nmemb, cmpindir);
    ...
    } else if ((flags & SORTf_DESC) != 0) {
         const SVCOMPARE_t savecmp = PL_sort_RealCmp;   /* Save current comparison routine, if any */
         PL_sort_RealCmp = cmp; /* Put comparison routine where cmp_desc can find it */
         cmp = cmp_desc;
         qsortsvu(list1, nmemb, cmp);
         /* restore prevailing comparison routine */
         PL_sort_RealCmp = savecmp;
    } else {
         qsortsvu(list1, nmemb, cmp);
    }

qsortsvがstableなquicksortでqsortsvuがunstableなquicksort.STABLEフラグが立っているときはindirに対してcmpindir/cmpindir_descを,そうでなければlist1に対してcmp/cmp_descを実際の比較関数として用いている.

static I32
cmpindir(pTHX_ gptr a, gptr b)
{
    dVAR;
    gptr * const ap = (gptr *)a;
    gptr * const bp = (gptr *)b;
    const I32 sense = PL_sort_RealCmp(aTHX_ *ap, *bp);

    if (sense)
        return sense;
    return (ap > bp) ? 1 : ((ap < bp) ? -1 : 0);
}

cmp/cmp_descは元の比較関数とその符号を逆にした値を返す関数なんだけども,cmpindir/cmpindir_descは元の比較関数で値が等しい(sense==0)時,ポインタの比較を行っている.

         pp = indir;
         q = list1;
         for (n = nmemb; n--; ) {
              j = pp[n] - q;            /* This sets j so that q[j] is
                                         * at pp[n].  *pp[j] belongs in
                                         * q[j], by construction.
                                         */
              if (n != j) {             /* all's well if n == j */
                   tmp = q[j];          /* save what's in q[j] */
                   do {
                        q[j] = *pp[j];  /* put *pp[j] where it belongs */
                        i = pp[j] - q;  /* the index in q of the element
                                         * just moved */
                        pp[j] = q + j;  /* this is ok now */
                   } while ((j = i) != n);

                   q[n] = tmp;          /* put what belongs into
                                         * the n-th element */
              }
         }

後はindirの順番にlist1をソートしている.

当たり前と言えば当たり前な実装だなあ.間接的な配列の初期化とindirの順序にlist1をソートするのにO(n)ぐらいの計算時間がかかるけど,そんなに悪くはなさそう.

ちなみにperl5.10.0だとデフォルトのソート関数はmerge sortであり,quicksortを利用するにはuse sort '_quicksort'としなければならないし,stableなソートにするためにはuse sort 'stable'としなければならない.