LoginSignup
1
1

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-04

はじめに

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

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

ボトムアップ型の課題その２

ボトムアップ型の課題といっても実装によるが，配列の先頭からマージを行う場合，配列の末尾に未結合の要素が残ってしまう。とくに配列の要素数が２のべき乗＋１の場合，末端の要素がマージされるのは最後になる。最後にマージする二つの区間の要素数がバランスを欠いており，後半部の要素数が１つしかない。

ここで GNU C ライブラリの qsort では前後二つに分割した配列のうち，後半部の要素数を多くした方が得になることを思い出して欲しい。

また，配列 a[] を前半部と後半部に分割する際，配列の要素数が奇数だと等分割できない。非均等に分割するのであれば，後半部の要素数を多くした方が得だと分かるだろう。これは後半部の要素数のほうが多いと，後半部の要素が残ってしまう確率が高くなるが，その場合，残った要素を転送しなくても済むからだ。実際，配列の要素数 len が奇数の場合，前半部の要素数 n1 よりも後半部の要素数 n2 がのほうが一つだけ多くなるよう分割される。

前半部の要素数を少なくした方が効率良いのであれば，以下に示すように配列の先頭に未結合の要素を置いたほうが良いだろう。

改善案

配列の全要素数 $n$，領域の大きさ $s$ とおくと，

  • $n \bmod 2s \le s$ のとき，先頭から $n \bmod 2s$ 個の要素は未結合のまま残される。
  • $n \bmod 2s > s$ のとき，先頭から $n \bmod 2s$ 個の要素も余さず結合され，前半部が $n \bmod 2s -s$ 個，後半部が $s$ 個となる。

のように場合分けが必要となる。$2s$ で割った余り（剰余演算）を避けるのであれば，初期値 $i = n - 2s$ として $i$ 番目の要素から $s$ 個，$i + s$ 番目の要素から $s$ 個の要素をマージしていき，$i$ は $2s$ ずつ減らしていけばよい。最後の $i \ge 0$ が $n$ を $2s$ で割った余りである。

とりあえずこれをバックワード型と呼ぶことにしよう。

しかし，領域の大きさ $s$ は２のべき乗数なので，$2s$ で割った余りを求める剰余演算は単に $2s - 1$ との論理積（AND）を求めるだけでよい。したがって $i = n \bmod 2s$ として，$i$ を $2s$ ずつ増やしていく方法も考えられる。これをフォワード型と呼ぶことにする。

なぜ，いきなりバックワード型とフォワード型の二種類を作成したのかというと，まず最初にバックワード型を作ったとき，なんとなくキャッシュメモリのヒット率が悪くなるような予感がしたからだ。

一般にメモリアクセス，とくにリード（読出し）動作はランダクアクセスよりもシーケンシャルアクセスのほうが高速だが，それはキャッシュメモリにヒットする確率が高くなるからだ。ただし，シーケンシャルアクセスといっても参照方向が正順と逆順で大差ないのか，あるいは差が生じるのかについては興味深いテーマであろう。
※筆者はフォワード型のほうが速いと思っている。

実装コード

実装コードを以下に示す。

ボトムアップ型マージソート関数その２（バックワード型）
ボトムアップ型マージソート関数その２
/* 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 n = n1 + n2;
/* 011 */     int *p1 = a;
/* 012 */     int *p2 = a + n1;
/* 013 */     int *q = buf;
/* 014 */     for(;;) {
/* 015 */         if(compare(*p1, *p2) <= 0) {
/* 016 */             *q++ = *p1++; if(--n1 == 0) break;
/* 017 */         } else {
/* 018 */             *q++ = *p2++; if(--n2 == 0) break;
/* 019 */         }
/* 020 */     }
/* 021 */     while(n1 > 0) {
/* 022 */         *q++ = *p1++; n1--;
/* 023 */     }
/* 024 */     for(int i = 0; i < n - n2; i++)
/* 025 */         a[i] = buf[i];
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = len - 2; i >= 0; i -= 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     for(int s = 2; s < len; s = s * 2) {
/* 031 */         int i, adj;
/* 032 */         for(i = len - s * 2; i >= 0; i -= s * 2)
/* 033 */             merge(buf, &a[i], s, s, compare);
/* 034 */         if((adj = i + s) > 0)
/* 035 */             merge(buf, a, adj, s, compare);
/* 036 */     }
/* 037 */ }
/* 038 */ void    msort2(int *a, int len, COMPARE compare) {
/* 039 */     if(len < 2) return;
/* 040 */     if(len <= TEMP_SIZE) {
/* 041 */         int tmp[TEMP_SIZE];
/* 042 */         sort(tmp, a, len, compare);
/* 043 */     } else {
/* 044 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 045 */         if(buf == (int*)NULL) return;
/* 046 */         sort(buf, a, len, compare);
/* 047 */         free(buf);
/* 048 */     }
/* 049 */ }
ボトムアップ型マージソート関数その３（フォワード型）
ボトムアップ型マージソート関数その３
/* 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 n = n1 + n2;
/* 011 */     int *p1 = a;
/* 012 */     int *p2 = a + n1;
/* 013 */     int *q = buf;
/* 014 */     for(;;) {
/* 015 */         if(compare(*p1, *p2) <= 0) {
/* 016 */             *q++ = *p1++; if(--n1 == 0) break;
/* 017 */         } else {
/* 018 */             *q++ = *p2++; if(--n2 == 0) break;
/* 019 */         }
/* 020 */     }
/* 021 */     while(n1 > 0) {
/* 022 */         *q++ = *p1++; n1--;
/* 023 */     }
/* 024 */     for(int i = 0; i < n - n2; i++)
/* 025 */         a[i] = buf[i];
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = len & 1; i + 1 < len; i += 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     for(int s = 2; s < len; s = s * 2) {
/* 031 */         int i = len & (s * 2 - 1);
/* 032 */         int adj;
/* 033 */         if((adj = i - s) > 0)
/* 034 */             merge(buf, a, adj, s, compare);
/* 035 */         for(; i + s < len; i += s * 2)
/* 036 */             merge(buf, &a[i], s, s, compare);
/* 037 */     }
/* 038 */ }
/* 039 */ void    msort3(int *a, int len, COMPARE compare) {
/* 040 */     if(len < 2) return;
/* 041 */     if(len <= TEMP_SIZE) {
/* 042 */         int tmp[TEMP_SIZE];
/* 043 */         sort(tmp, a, len, compare);
/* 044 */     } else {
/* 045 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 046 */         if(buf == (int*)NULL) return;
/* 047 */         sort(buf, a, len, compare);
/* 048 */         free(buf);
/* 049 */     }
/* 050 */ }

試験条件

  • 要素数 200,000,000 個のint 型の配列の昇順ソートを行う。マージソートの場合，同サイズの配列がもう一つ必要になることから，32bit プログラムではほぼ上限値である。
    4×200,000,000 bytes = 0x2FAF0800 bytes
  • データの順序は以下の四種類とする。
    • ゼロ
    • 昇順：0 → 199,999,999
    • 降順：199,999,999 → 0
    • 乱数：0～199,999,999 の範囲の一様乱数，乱数発生器は XorShift とした3
  • 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：クイックソート，uCRT 版 qsort の意訳版
    • glibc：再帰型（トップダウン型）マージソート，GNU C ライブラリの qsort の意訳版
    • merge：非再帰型（ボトムアップ型）マージソート，
      未結合要素は末尾
    • merge2：非再帰型（ボトムアップ型）マージソート，
      未結合要素は先頭（バックワード型）※今回作成
    • merge3：非再帰型（ボトムアップ型）マージソート，
      未結合要素は先頭（フォワード型）※今回作成

実行時間の比較

実行時間の比較を示す。

表１　実行時間の比較（単位は秒）
コンパイラ 順序 uCRT glibc merge merge2 merge3
Visual C++
32bit版		 ゼロ 0.090 2.660 2.835 2.841 2.264
昇順 1.433 2.656 2.848 2.851 2.267
降順 1.475 3.914 4.668 4.862 3.829
乱数 15.505 17.996 19.431 19.789 17.524
Visual C++
64bit版		 ゼロ 0.093 2.470 2.158 2.123 2.086
昇順 1.582 2.473 2.148 2.126 2.087
降順 1.617 3.769 3.370 3.517 3.432
乱数 15.500 21.129 20.050 20.192 20.114
LLVM clang-cl
32bit版		 ゼロ 0.098 2.066 2.095 2.018 1.963
昇順 1.627 2.060 2.109 2.049 1.974
降順 1.688 3.642 3.015 3.278 3.063
乱数 15.636 16.487 15.981 16.199 15.876
LLVM clang-cl
64bit版		 ゼロ 0.089 1.958 1.679 1.547 1.492
昇順 1.460 1.997 1.663 1.563 1.488
降順 1.523 2.942 2.456 2.626 2.512
乱数 15.710 16.022 15.853 15.922 15.539
intel icx-cl
32bit版		 ゼロ 0.070 2.488 2.038 1.979 1.945
昇順 1.592 2.498 2.050 1.989 1.954
降順 1.691 3.333 2.877 2.964 2.871
乱数 17.120 17.809 17.767 17.107 17.582
intel icx-cl
32bit版		 ゼロ 0.064 1.811 1.621 1.582 1.542
昇順 1.366 1.797 1.608 1.583 1.550
降順 1.491 2.507 2.418 2.526 2.428
乱数 16.584 15.969 15.682 15.497 15.673

こういうのはグラフにすると分かり易い。

■uCRT，■glibc，■merge，■merge2，■merge3

結論

あれこれ工夫しても大して変わらんな・・・

1
1
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
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?