LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～

Last updated at Posted at 2025-05-18

はじめに

これまで下記の記事で GNU C ライブラリの qsort について勉強してきた。

GNU C ライブラリの qsort はマージソートであり，再帰関数（トップダウン型）として作られていることから，非再帰型（ボトムアップ型）に書き直すことでパフォーマンスアップを狙ったが，期待したほどの効果（劇的な効果）を得られなかった。

そもそも明確な利点があったら GNU C ライブラリで採用しているだろうから，非再帰型（ボトムアップ型）には他に何か致命的な欠陥？があるのではないかと思うようになったのが前回の記事である。

だがしかし，先日，パフォーマンスアップを期待できるアイディアを思いついたのだ。

改善案

部屋の模様替えを行うとき，部屋が狭いわりに大きな家具や荷物が多いといろいろ悩ましい。まず，移動先の空きスペースを確保しないといけないし，かつての倉庫番ゲームのように動かす順番を考えないといけないからだ。こういうとき隣の部屋が空いていたりするととても便利である。ある日，ふと思いついたのだ。いっそのこと隣の空き部屋に家具を全部持って行ってそこに住んでしまえばいいんじゃねと？

マージソートでも同様だ。マージソートでは基本的にソート対象となる配列と同サイズの作業用エリアを必要とする。二つの区間をマージする際，いったん作業用エリア上でマージして，それから元の配列に書き戻しているのだが，わざわざ書き戻さなくても良くないか？つまり，作業用エリアをそのまま使ってしまい，今度は元の配列の領域を作業用として使おうというアイディアだ。こうして二つのエリアを交互に作業用として使えば，データ転送量を約半分に済ませられるはず。

ちなみにこのアイディアは非再帰型（ボトムアップ型）マージソートでないと成立しない。

実装コード

とても簡単にできたので全容を示そう。

merge4（ボトムアップ型・データ転送節約版）
/* 001 */ #include <stdlib.h>
/* 002 */ typedef int     (*COMPARE)(int, int);
/* 003 */ #define TEMP_SIZE   256
/* 004 */ static  void    swap(int *p, int *q) {
/* 005 */     int temp = *p;
/* 006 */     *p = *q;
/* 007 */     *q = temp;
/* 008 */ }
/* 009 */ static  void    merge(int *buf, int *a, int n1, int n2, COMPARE compare) {
/* 010 */     int *p1 = a;
/* 011 */     int *p2 = a + n1;
/* 012 */     int *q = buf;
/* 013 */     for(;;) {
/* 014 */         if(compare(*p1, *p2) <= 0) {
/* 015 */             *q++ = *p1++; if(--n1 == 0) break;
/* 016 */         } else {
/* 017 */             *q++ = *p2++; if(--n2 == 0) break;
/* 018 */         }
/* 019 */     }
/* 020 */     while(n1 > 0) {
/* 021 */         *q++ = *p1++; n1--;
/* 022 */     }
/* 023 */     while(n2 > 0) {
/* 024 */         *q++ = *p2++; n2--;
/* 025 */     }
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = 0; i + 1 < len; i += 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     int *x = a;
/* 031 */     int *y = buf;
/* 032 */     for(int s = 2; s < len; s = s * 2) {
/* 033 */         int i, adj;
/* 034 */         for(i = 0; i + s * 2 < len; i += s * 2)
/* 035 */             merge(&y[i], &x[i], s, s, compare);
/* 036 */         if((adj = len - (i + s)) > 0)
/* 037 */             merge(&y[i], &x[i], s, adj, compare);
/* 038 */         else
/* 039 */             for(; i < len; i++) y[i] = x[i];
/* 040 */         int *temp = x; x = y; y = temp;
/* 041 */     }
/* 042 */     if(x != a)
/* 043 */         for(int i = 0; i < len; i++) a[i] = x[i];
/* 044 */ }
/* 045 */ void    msort4(int *a, int len, COMPARE compare) {
/* 046 */     if(len < 2) return;
/* 047 */     if(len <= TEMP_SIZE) {
/* 048 */         int tmp[TEMP_SIZE];
/* 049 */         sort(tmp, a, len, compare);
/* 050 */     } else {
/* 051 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 052 */         if(buf == (int*)NULL) return;
/* 053 */         sort(buf, a, len, compare);
/* 054 */         free(buf);
/* 055 */     }
/* 056 */ }
/* 057 */

アルゴリズム解説

それでは自作コードを頭から解説していきたい。同じ非再帰型（ボトムアップ型）マージソートと比べれば実装の違いがよく分かると思う。

マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita

1. 交換関数

交換関数 swap は全く同じである。

2. ソート関数本体

ソート関数本体である。関数名のみ異なり，あとは全く同じである。

3. マージソートエンジン

マージソートエンジンである。領域の大きさが１の場合の処理は同じである。隣接する要素の大小を比較して入れ替えれば良いので，交換関数 swap の呼び出しで済ませている。

領域の大きさ s が２以上になると本実装の特徴が表れる。元の配列 a[] と作業用エリア buf[] を直接参照せず，読出し側が x，書き込み側が y とポインタによる間接参照にして，マージを一段実行する毎にポインタ x と y を交換しているのだ。

他に注意事項としては以下の二つ。

  • 末尾にある未結合要素も忘れずにコピーする必要がある
  • 最後に元の配列 a[] に書き戻すことを忘れないこと

4. マージ関数

マージ関数も少し違う。作業用エリア buf[] に書き込むのみで元の配列 a[] に書き戻さない。

比較回数・転送回数の比較

試験条件は下記の通りである。

  • 200,000,000 個の 32bit 整数を昇順ソートする。
  • データの順序は以下の四種類である。
    • ゼロ（すべて同値）
    • 昇順：0 → 199,999,999
    • 降順：199,999,999 → 0
    • 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
  • 乱数発生器は XorShift である。
  • 比較対象のソートアルゴリズムは以下の四つとする。
    • uCRT：クイックソート
    • glibc：再帰型マージソート
    • merge：非再帰型マージソート
    • merge4：非再帰型マージソート・データ転送節約版　※今回作成したもの
表１　比較回数の比較（単位は回）
順序 uCRT glibc merge merge4
ゼロ 399,999,999 2,728,894,208 2,804,304,128 2,804,304,128
昇順 5,363,792,412 2,728,894,208 2,804,304,128 2,804,304,128
降順 5,363,792,412 2,802,670,336 2,728,894,208 2,728,894,208
乱数 6,400,427,154 5,265,836,886 5,280,310,523 5,280,310,523
表２　転送回数の比較（単位は回）
順序 uCRT glibc merge merge4
ゼロ 0 5,457,788,416 5,408,608,256 5,600,000,000
昇順 265,782,274 5,457,788,416 5,408,608,256 5,600,000,000
降順 465,782,278 11,063,129,088 10,866,396,672 5,800,000,000
乱数 2,736,238,624 10,752,119,342 10,613,478,548 5,700,000,344

今回作成した merge4 について，比較回数は merge（非再帰型マージソート）と全く変わらない。一方，データ転送回数について，ゼロや昇順などソートする必要がないデータについては微増となっているが，降順と乱数についてはほぼ半減していることが分かる。これは実行時間に期待できそうだ。

■uCRT，■glibc，■merge，■merge4

実行時間の比較

試験条件を以下に示す。

  • Cコンパイラは下記の三種類とし，かつターゲットを 32bit (x86)と64bit (x64)の二種類の組み合わせで合計六種類とする。
    • Microsoft Visual C++ 2022
    • LLVM clang 17.0.3
    • intel C++ compiler：oneAPI 2024.2, Compiler Release 2024.2.1
  • 評価マシンのスペックは下記の通り
    Windows10 2022H2，Core i7-13700 5.1GHZ，32GB

試験結果を以下に示す。

表３　実行時間の比較（単位は秒）
コンパイラ 順序 uCRT glibc merge merge4
Visual C++
32bit版		 ゼロ 0.090 2.660 2.835 3.796
昇順 1.433 2.656 2.848 3.797
降順 1.475 3.914 4.668 3.752
乱数 15.505 17.996 19.431 17.495
Visual C++
64bit版		 ゼロ 0.093 2.470 2.158 2.984
昇順 1.582 2.473 2.148 2.961
降順 1.617 3.769 3.370 2.927
乱数 15.500 21.129 20.050 18.346
LLVM clang-cl
32bit版		 ゼロ 0.098 2.066 2.095 3.729
昇順 1.627 2.060 2.109 3.415
降順 1.688 3.642 3.015 3.393
乱数 15.636 16.487 15.981 17.146
LLVM clang-cl
64bit版		 ゼロ 0.089 1.958 1.679 2.259
昇順 1.460 1.997 1.663 2.262
降順 1.523 2.942 2.456 2.240
乱数 15.710 16.022 15.853 15.296
intel icx-cl
32bit版		 ゼロ 0.070 2.488 2.038 2.971
昇順 1.592 2.498 2.050 2.973
降順 1.691 3.333 2.877 2.643
乱数 17.120 17.809 17.767 16.481
intel icx-cl
64bit版		 ゼロ 0.064 1.811 1.621 2.049
昇順 1.366 1.797 1.608 2.046
降順 1.491 2.507 2.418 2.074
乱数 16.584 15.969 15.682 15.010

グラフにすると分かり易い。

■uCRT，■glibc，■merge，■merge4

結論

  • 配列のデータが全てゼロや昇順のようなソート済みの特殊データについては比較回数・転送回数ともにほとんど変わらないにも関わらず，実行時間は微増となっている。

  • 降順や乱数のようにデータを入れ替える必要があるものについては，ほとんどのコンパイラで（LLVM clang-cl 32bit 版を除いて）高速化を実現できている。

  • LLVM clang-cl 32bit 版でパフォーマンスが上がらなかった点については謎である。おそらくループアンローリングや関数のインライン展開などの最適化を積極的に行ったが，汎用レジスタの少ない x86 アーキテクチャでは逆効果だったと推察している。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?