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

クイックソートにおける小型ソートの効果

Posted at

世の中のクイックソートの実装の多くは，分割された領域のサイズが小さくなると挿入ソートや選択ソートのような別のアルゴリズムに切り替える。このように切替の仕組みを持つクイックソートをハイブリッド・クイックソート，もしくは単にハイブリッドソートと呼ぶらしい。この切替後のソートを筆者は勝手に「小型ソート」と呼んでいる。

0. はじめに

これまで uCRT の qsort から始まって .NET Framework，そして .NET Core の Array.Sort のソースコードを読み，これらの動きを模倣したC言語コードを作成してパフォーマンスを比較してきた。

これまでに学んだクイックソートの各実装を比較すると下記のようになる。

表１　クイックソート実装の比較
項目 uCRT .NET
Framework
3.5		 .NET
Framework
4.8		 .NET Core
ヒープソート なし なし あり あり
ヒープソート
への切り換え		 － － 再帰深さ32 再帰深さ
$2(\lfloor \log_2 n \rfloor + 1)$
小型ソート 選択ソート なし なし 挿入ソート
小型ソート
への切り換え		 要素8個以下 － － 要素16個以下

これ以外にも細かい違いがあって表には書き切れないが，例えば uCRT の qsort では再帰呼び出しを行わず，goto 文を使って再帰呼び出しを模擬するなどの涙ぐましい努力が行われていたが，現代のプロセッサでは無意味な努力であることが分かっている。普通に再帰関数を呼び出してもパフォーマンスは変わらないのだ。

一方，小型ソートとして実装された選択ソートと挿入ソートの違いが気になる。

後ほど説明するが，選択ソートと挿入ソートの計算量（比較量）はいずれも $O(n^2)$ であるのに対し，データの移動量はまったく異なる。選択ソートのデータ移動量が $O(n)$ で済むのに対し，挿入ソートは平均 $O(n^2)$ となるため，あまり優れた手法とは思えないからだ。

つまり .NET Core の挿入ソートを選択ソートに差し替えたらもっと速くならないだろうか？

1. 選択ソートとは？

Windows の uCRT の qsort の内部で用いられている小型ソートである。特徴を示すと下記のようになる。

  • 計算量は多い：平均・最悪・最良すべて $O(n^2)$
  • in-place ソート，追加メモリは不要
  • 不安定ソート
  • データ交換回数は少ない：最大で $n - 1$ 回

1.1 選択ソートの実行例

実例を示した方が分かり易いと思うので下記の例で示そう。

初期状態で８個の整数がランダムに並んでいる。このうち最大値を赤字，領域の最終要素の背景を緑色■で示し，捜索範囲外の要素の背景を灰色■で示す。

  1. まず配列の要素８個すべてを捜索して最大要素（この場合は８）を選び，最終要素（この場合は２）と入れ替える。
  2. 次に先頭から７個の要素を捜索して最大要素（この場合は７）を選び，最終要素（この場合も２）と入れ変える。
  3. その次に先頭から６個の要素を捜索して最大要素（この場合は６）を選び，最終要素（この場合は５）と入れ替える。
  4. 以下，１ステップ進めるたびに捜索範囲を１つずつ減らしていけば最終状態に到達する。

1.2 選択ソートの比較回数

上記の例題の場合，比較回数は $7 + 6 + 5 + 4 + 3 + 2 + 1 = 28$ 回必要である。要素数 $n$ とすると一般的に比較回数は $n (n - 1) / 2$ となる。

1.3 選択ソートのデータ入れ替え回数

一方，入れ替えの回数について，最大要素が最終要素と一致する場合は入れ替えの必要がないので確率的になり，一様ランダムであると仮定すると期待値としては

$$
\frac{7}{8} + \frac{6}{7} + \frac{5}{6} + \frac{4}{5} + \frac{3}{4} + \frac{2}{3} + \frac{1}{2} \approx 5.28
$$

となる。要素数 $n$ とすると一般的には

$$
n - \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) = n - \sum_{k=1}^{n} \frac{1}{k}
$$

と表される。$\sum (1/k)$ は調和級数と呼ばれ，オイラー・マスケローニ定数 $\gamma = 0.577\ldots$ と対数を用いた近似式で表すと，入れ替え回数は

$$
n - \sum_{k = 1}^n \frac{1}{k} \approx n - \left( \gamma + \log{n} \right)
$$

となる。試しに $n = 8$ の場合の値を計算すると $5.34$ となり，思ったより使えそうな近似式である。

2. 挿入ソートとは？

.NET Core の Array.Sort の内部等で用いられている小型ソートである。特徴を示すと下記のようになる。

  • 計算量：平均・最悪 $O(n^2)$，最良 $O(n)$
  • in-place ソート　※追加メモリは不要
  • 安定ソート
  • データ交換回数は多い：平均・最悪 $O(n^2)$，最良 0 回

2.1 挿入ソートの実行例

こちらも実例を示した方が分かり易いと思うので下記の例で示そう。

初期状態で８個の整数がランダムに並んでいる。このうち領域の最終要素の背景を緑色■で示し，最終要素の挿入箇所を▼，範囲外の要素の背景を灰色■で示す。

  1. まず先頭から２番目の要素（この場合は３）をそれより前の要素（この場合は６のみ）と比較し，６の前に３を挿入する。
  2. 次に先頭から３番目の要素（この場合は４）をそれより前の要素（この場合は３，６）と比較し，６の前に４を挿入する。
  3. その次に先頭から４番目の要素（この場合は７）をそれより前の要素（この場合は３，４，６）と比較し，７の前に７を挿入する。つまり，データの移動は起こらない。
  4. 以下，１ステップ進めるたびにソート済みの領域を１つずつ広げていけば最終状態に到達する。

2.2 挿入ソートの比較回数

比較回数について考える。直感では選択ソートの半分程度に収まるものと予想される。選択ソートでは最大値を求めるために全要素と比較する必要があったが，挿入ソートでは大抵の場合比較が途中で止まるからだ。

一様ランダムと仮定して比較回数の期待値を求めてみよう。

$$
1 + \frac{1 + 2}{2} + \frac{1 + 2 + 3}{3} + \cdots + \frac{1 + 2 + 3 + \cdots + 7}{7} = 17.5
$$

となり，挿入ソートの $28$ 回に比べて小さい。※さすがに半分ではなかった。

要素数 $n$ とすると一般的には，

$$
\frac{n (n - 1)}{4} + \frac{n - 1}{2} \
$$

となる。$n^2$ の係数を比べると選択ソートが $1/2$ なのに対し，挿入ソートは $1/4$ であるから $n$ が十分大きくなれば選択ソートの半分になると予想される。

2.3 挿入ソートのデータ転送量

次に，データ転送量について考えよう。データの書き込み回数をカウントするものとする。一様ランダムとしてデータ転送量の期待値は

\begin{align}
&\frac{2}{2} + \frac{2 + 3}{3} + \frac{2 + 3 + 4}{4} + \cdots + \frac{2 + 3 + \cdots + 7}{7} \\
&= 1 + \frac{1 + 2}{2} + \frac{1 + 2 + 3}{3} + \cdots  + \cdots \frac{1 + 2 + 3 + \cdots + 7}{7} \\
&- \left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{7} \right) \\
&= 17.5 - 2.59 \\
&= 14.9
\end{align}

となる。先ほどの選択ソートはデータの入れ替えのため，１回の入れ替えあたりデータの書き込みは２回行われる。このことを加味して選択ソートの期待値 $5.28$ の２倍よりも大きいのだ。

要素数 $n$ とすると一般的には，

$$
\frac{n(n - 1)}{4} + \frac{n - 1}{2} - \sum_{k = 1}^{n - 1} \frac{1}{k} \approx \frac{n(n - 1)}{4} + \frac{n - 1}{2} - \left\lbrace \gamma + \log(n - 1) \right\rbrace
$$

となる。選択ソートのデータ転送量が $O(n)$ で収まっていたのに対し，挿入ソートは $O(n^2)$ となっており，要素数 $n$ が大きくなると転送量が爆発的に増大する。

3. テスト用コード

前回の記事で紹介した .NET Core の Array.Sort のアルゴリズムをC言語に意訳した qsort_net3 をベースにして，余分な比較を取り除いてチューニングした qsort_net4 を作成した。

なお，小型ソートとして挿入ソート or 選択ソートのいずれも選択できるようにし，小型ソートの切り換え点もマクロ定数で定義した。定数であれば，ループアンローリングなどのコンパイラ最適化技術が適用し易いからである。

3.1 マクロ定数

本プログラムのマクロ定数を以下に示す。

表２　マクロ定数一覧
マクロ 内容 デフォルト
COUNT 比較・転送回数のカウント用コード生成 なし
SHORTSORTSIZE 小型ソートに切り替える要素数 16
INSERTIONSORT 小型ソートとして挿入ソートを使用 なし
SELECTIONSORT 小型ソートとして選択ソートを使用 なし

COUNT を定義すると，比較・転送回数をカウントするコードが生成されるので実行時間は余分にかかる。実行時間を計測する場合には定義しないこと。

INERTIONSORT と SELECTIONSORT のうち，いずれか一方は必ず定義する必要がある。

3.2 ソースコード一式

Makefile を含めたソースコード一式を以下に示す。

クイックソートエンジン：qsort_net4.c
qsort_net4.c
#ifndef	SHORTSORTSIZE
#define	SHORTSORTSIZE	16
#endif
#include <intrin.h>
#ifdef	COUNT
#include <stdint.h>
extern	uint64_t	move_count;
#endif
typedef	int		(*COMPARE)(int, int);
static	void	swap(int *p, int *q) {
#ifdef	COUNT
	move_count += 2;
#endif
	int	temp = *p;
	*p = *q;
	*q = temp;
}
static	void	heap(int *a, int len, int parent, COMPARE compare) {
	int	d = a[parent];
	int	child;
	while((child = 2 * parent + 1) < len) {
		if(child + 1 < len && compare(a[child], a[child + 1]) < 0)
			child++;
		if(compare(d, a[child]) >= 0) break;
#ifdef	COUNT
		move_count++;
#endif
		a[parent] = a[child];
		parent = child;
	}
#ifdef	COUNT
	move_count++;
#endif
	a[parent] = d;
}
static	void	hsort(int *a, int len, COMPARE compare) {
	for(int i = len / 2 - 1; i >= 0; i--)
		heap(a, len, i, compare);
	for(int i = len - 1; i > 0; i--) {
		swap(&a[0], &a[i]);
		heap(a, i, 0, compare);
	}
}
static	void	sort(int *a, int top, int end, int depth, COMPARE compare) {
	while(top < end) {
		int	n = end - top + 1;
		if(n <= SHORTSORTSIZE) {
			if(n == 1) {
				/* do nothing */
			} else if(n == 2) {
				if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
			} else if(n == 3) {
				int	mid = end - 1;
				if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
				if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
				if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
			} else {
#ifdef	SELECTIONSORT
				for(int e = end; e > top; e--) {
					int	max = top;
					for(int i = top + 1; i <= e; i++)
						if(compare(a[i], a[max]) > 0) max = i;
					swap(&a[max], &a[e]);
				}
#endif
#ifdef	INSERTIONSORT
				for(int i = top; i < end; i++) {
					int	temp = a[i + 1];
					int	j;
					for(j = i; j >= top && compare(temp, a[j]) < 0; j--)
#ifdef	COUNT
					{
						move_count++;
#endif
						a[j + 1] = a[j];
#ifdef	COUNT
					}
					move_count++;
#endif
					a[j + 1] = temp;
				}
#endif
			}
			return;
		}
		if(depth == 0) {
			hsort(&a[top], end - top + 1, compare);
			return;
		}
		depth--;
		int	mid = top + (end - top) / 2;
		if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
		if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
		if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
		int	pivot = a[mid];
		swap(&a[mid], &a[end - 1]);
		int	t = top;
		int	e = end - 1;
		while(t < e) {
			while(compare(a[++t], pivot) < 0);
			while(compare(pivot, a[--e]) < 0);
			if(t >= e) break;
			swap(&a[t], &a[e]);
		}
		swap(&a[t], &a[end - 1]);
		sort(a, t + 1, end, depth, compare);
		end = t - 1;
	}
}
static	int	ilog2(int x) {
	return 31 - __lzcnt(x);
}
void	qsort_net4(int *a, int len, COMPARE compare) {
	if(len < 2) return;
	int	depth = 2 * (ilog2(len) + 1);
	sort(a, 0, len - 1, depth, compare);
}
ベンチマーク用メイン関数：bench.c
bench.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
typedef	int		(*COMPARE)(int, int);
extern	void	qsort_net4(int *a, int len, COMPARE compare);
uint32_t	xorshift( void ) {
static	uint64_t	x = 1;
	x ^= x << 13;
	x ^= x >>  7;
	x ^= x << 17;
	return (uint32_t)x;
}
#ifdef	COUNT
static	int		index = 0;
static	int		*pivot = (int*)NULL;
static	int		killer(int p, int q) {
	if(pivot[p] < 0 && pivot[q] < 0) {
		pivot[p] = index++;
		pivot[q] = index++;
		return -1;
	}
	if(pivot[p] < 0) return  1;
	if(pivot[q] < 0) return -1;
	return pivot[p] - pivot[q];
}
uint64_t	move_count = 0;
uint64_t	comp_count = 0;
#endif
static	int		compare(int p, int q) {
#ifdef	COUNT
	comp_count++;
#endif
	return p - q;
}
int	main(int argc, char *argv[]) {
	if(argc < 3) {
		fprintf(stderr, "Usage: bench(.exe) [data] [size] (debug)\n");
#ifdef	COUNT
		fprintf(stderr, " data: zero, ascend, descend, random, killer\n");
#else
		fprintf(stderr, " data: zero, ascend, descend, random\n");
#endif
		return -1;
	}
	int	size = atoi(argv[2]);
	int	*table = (int*)malloc(sizeof(int) * size);
	if(table == (int*)NULL) {
		fprintf(stderr, "cannot allocate size: %d\n", size);
		return -1;
	}
	switch(argv[1][0]) {
	  case 'z': for(int i = 0; i < size; i++) table[i] = 0;					break;
	  case 'a':	for(int i = 0; i < size; i++) table[i] = i;					break;
	  case 'd':	for(int i = 0; i < size; i++) table[i] = size - i - 1;		break;
	  case 'r':	for(int i = 0; i < size; i++) table[i] = xorshift() % size;	break;
#ifdef	COUNT
	  case 'k':
		int		*dummy = (int*)malloc(sizeof(int) * size);
		if(dummy == (int*)NULL) {
			fprintf(stderr, "cannot allocate size: %d\n", size);
			return -1;
		}
		pivot = (int*)malloc(sizeof(int) * size);
		if(pivot == (int*)NULL) {
			fprintf(stderr, "cannot allocate size: %d\n", size);
			return -1;
		}
		for(int i = 0; i < size; i++) dummy[i] = i;
		for(int i = 0; i < size; i++) pivot[i] = -1;
		qsort_net4(dummy, size, killer);
		for(int i = 0; i < size; i++) table[dummy[i]] = i;
		free(dummy);
		free(pivot);
		break;
#endif
	  default:
		fprintf(stderr, "illegal data: %s\n", argv[1]);
		return -1;
	}
#ifdef	COUNT
	qsort_net4(table, size, compare);
	fprintf(stdout, "comp_count: %lld\n", comp_count);
	fprintf(stdout, "move_count: %lld\n", move_count);
#else
	clock_t	t1 = clock();
	qsort_net4(table, size, compare);
	clock_t	t2 = clock();
	fprintf(stdout, "time: %.3f\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
#endif
	if(argc >= 4 && argv[3][0] == 'd')
		for(int i = 0; i < size; i++) fprintf(stdout, "%d\n", table[i]);
	return 0;
}
比較・転送回数の計測プログラム作成，Microsoft Visual C++ 用：Makefile.count
Makefile.count
OUTDIR=count
CC=cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /GS- /GL /DCOUNT
LFLAGS=/GL
LIBS=
!include "MAKEFILE.INC"
処理時間の計測プログラム作成，Microsoft Visual C++ 用：Makefile.vc
Makefile.vc
!ifdef VSCMD_ARG_TGT_ARCH
OUTDIR=$(VSCMD_ARG_TGT_ARCH)vc
!else
!error 環境変数 VSCMD_ARG_TGT_ARCH が未定義です。
!endif
CC=cl
CFLAGS=/c /O2 /Ob2 /W4 /arch:AVX2 /GS- /GL
LFLAGS=/GL
LIBS=
!include "MAKEFILE.INC"
処理時間の計測プログラム作成，LLVM clang 用：Makefile.clang
Makefile.clang
!ifdef VSCMD_ARG_TGT_ARCH
OUTDIR=$(VSCMD_ARG_TGT_ARCH)clang
!else
!error 環境変数 VSCMD_ARG_TGT_ARCH が未定義です。
!endif
CC=clang-cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /TC /GS- -flto
LFLAGS=-flto -fuse-ld=lld
LIBS=
!include "MAKEFILE.inc"
処理時間の計測プログラム作成，intel C++ compiler 用：Makefile.intel
Makefile.intel
!ifdef VS_TARGET_ARCH
OUTDIR=$(VS_TARGET_ARCH)intel
!else
!error 環境変数 VS_TARGET_ARCH が未定義です。
!endif
CC=icx-cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /TC /GS- -flto
LFLAGS=-flto -fuse-ld=lld
LIBS=
!include "MAKEFILE.inc"
全メイクファイル共通部：Makefile.inc
Makfile.inc
OUTDIRS=$(OUTDIR) \
        $(OUTDIR)\select \
        $(OUTDIR)\select\8 \
        $(OUTDIR)\select\16 \
        $(OUTDIR)\select\32 \
        $(OUTDIR)\select\64 \
        $(OUTDIR)\insert \
        $(OUTDIR)\insert\8 \
        $(OUTDIR)\insert\16 \
        $(OUTDIR)\insert\32 \
        $(OUTDIR)\insert\64

target: $(OUTDIRS) \
        $(OUTDIR)\select\8\bench.exe \
        $(OUTDIR)\select\16\bench.exe \
        $(OUTDIR)\select\32\bench.exe \
        $(OUTDIR)\select\64\bench.exe \
        $(OUTDIR)\insert\8\bench.exe \
        $(OUTDIR)\insert\16\bench.exe \
        $(OUTDIR)\insert\32\bench.exe \
        $(OUTDIR)\insert\64\bench.exe

$(OUTDIRS):
	@if not exist $@ mkdir $@

$(OUTDIR)\select\8\bench.exe:  $(OUTDIR)\select\8\bench.obj  $(OUTDIR)\select\8\qsort_net4.obj
$(OUTDIR)\select\16\bench.exe: $(OUTDIR)\select\16\bench.obj $(OUTDIR)\select\16\qsort_net4.obj
$(OUTDIR)\select\32\bench.exe: $(OUTDIR)\select\32\bench.obj $(OUTDIR)\select\32\qsort_net4.obj
$(OUTDIR)\select\64\bench.exe: $(OUTDIR)\select\64\bench.obj $(OUTDIR)\select\64\qsort_net4.obj
$(OUTDIR)\insert\8\bench.exe:  $(OUTDIR)\insert\8\bench.obj  $(OUTDIR)\insert\8\qsort_net4.obj
$(OUTDIR)\insert\16\bench.exe: $(OUTDIR)\insert\16\bench.obj $(OUTDIR)\insert\16\qsort_net4.obj
$(OUTDIR)\insert\32\bench.exe: $(OUTDIR)\insert\32\bench.obj $(OUTDIR)\insert\32\qsort_net4.obj
$(OUTDIR)\insert\64\bench.exe: $(OUTDIR)\insert\64\bench.obj $(OUTDIR)\insert\64\qsort_net4.obj

$(OUTDIR)\select\8\bench.exe  \
$(OUTDIR)\select\16\bench.exe \
$(OUTDIR)\select\32\bench.exe \
$(OUTDIR)\select\64\bench.exe \
$(OUTDIR)\insert\8\bench.exe  \
$(OUTDIR)\insert\16\bench.exe \
$(OUTDIR)\insert\32\bench.exe \
$(OUTDIR)\insert\64\bench.exe:
	$(CC) $** /Fe$* $(LFLAGS) $(LIBS)

.c{$(OUTDIR)\select\8}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\select\8\  /DSELECTIONSORT /DSHORTSORTSIZE=8

.c{$(OUTDIR)\select\16}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\select\16\ /DSELECTIONSORT /DSHORTSORTSIZE=16

.c{$(OUTDIR)\select\32}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\select\32\ /DSELECTIONSORT /DSHORTSORTSIZE=32

.c{$(OUTDIR)\select\64}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\select\64\ /DSELECTIONSORT /DSHORTSORTSIZE=64

.c{$(OUTDIR)\insert\8}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\insert\8\  /DINSERTIONSORT /DSHORTSORTSIZE=8

.c{$(OUTDIR)\insert\16}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\insert\16\ /DINSERTIONSORT /DSHORTSORTSIZE=16

.c{$(OUTDIR)\insert\32}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\insert\32\ /DINSERTIONSORT /DSHORTSORTSIZE=32

.c{$(OUTDIR)\insert\64}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\insert\64\ /DINSERTIONSORT /DSHORTSORTSIZE=64

clean:
	if exist $(OUTDIR) rd /s /q $(OUTDIR)

3.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

ビルト用バッチファイル build.cmd を以下に示す。下記のバッチファイルを実行すると計 56 個の実行ファイルが作られる。

ビルド用バッチファイル build.cmd
build.cmd
@echo off
setlocal
  call "c:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvarsall.bat" x86
  nmake -f Makefile.count
  nmake -f Makefile.vc
  nmake -f Makefile.clang
endlocal
setlocal
  call "c:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvarsall.bat" x64
  nmake -f Makefile.vc
  nmake -f Makefile.clang
endlocal
setlocal
  call "C:\Program Files (x86)\Intel\oneAPI\setvars.bat" -force ia32 vs2022
  nmake -f Makefile.intel
endlocal
setlocal
  call "C:\Program Files (x86)\Intel\oneAPI\setvars.bat" -force intel64 vs2022
  nmake -f Makefile.intel
endlocal
exit /b

各コンパイラ用の環境設定はバッチファイル内部で行うので，上記のバッチファイルを実行する前に Visual Studio および intel oneAPI の vcvarsall.bat を実行しないこと。

3.4 実行方法

比較・転送回数を比較するバッチファイルを以下に示す。

countall.cmd
@echo off
for %%I in (insert select) do (
  for %%J in (8 16 32 64) do (
    echo %%I %%J
    count\%%I\%%J\bench r 200000000
  )
)
exit /b

実行時間計測用バッチファイルを以下に示す。

timeall.cmd
@echo off
for %%H in (x86vc x64vc x86clang x64clang x86intel x64intel) do (
  for %%I in (insert select) do (
    for %%J in (8 16 32 64) do (
      echo %%H %%I %%J
      %%H\%%I\%%J\bench r 200000000
    )
  )
)
exit /b

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

比較・転送回数の比較を示す。試験条件は下記の通りである。

  • 200,000,000 個の 32bit 整数を昇順ソート
  • 0～199,999,999 の範囲で一様乱数（重複あり）
  • 乱数発生器はお馴染みの XorShift とした
表３　比較回数の比較（単位は回）
要素数 挿入ソート 選択ソート
8 6,129,180,398 6,248,670,789
16 6,213,723,201 6,577,692,950
32 6,557,129,012 7,446,950,037
64 7,437,400,251 9,408,881,300
表４　転送回数の比較（単位は回）
要素数 挿入ソート 選択ソート
8 2,828,814,279 2,788,295,106
16 2,969,967,591 2,707,485,990
32 3,395,766,290 2,613,290,180
64 4,381,719,028 2,517,265,866

グラフにすると分かり易いが，比較回数の増加を見ると挿入ソートは選択ソートの約半分であることが分かる。一方，転送回数は選択ソートのほうが少ない。選択ソートで要素数を大きくすると転送回数が減っているのは，ベースとしたクイックソートよりも転送回数が少ないからである。

◆挿入ソート，◆選択ソート

5. 実行時間の比較

評価マシンのスペックは下記の通り

  • Windows10 2022H2
  • Core i7-13700 5.1GHZ，32GB

試験結果を以下に示す。単位は秒である。

表５　実行時間の比較（単位は秒）
コンパイラ 要素数 挿入ソート 選択ソート
Visual C++
32bit版		 8 13.262 12.235
16 12.884 12.557
32 12.638 14.135
64 12.552 17.395
Visual C++
64bit版		 8 12.662 12.809
16 12.249 13.245
32 11.960 14.547
64 11.900 17.745
LLVM clang
32bit版		 8 12.400 12.423
16 12.110 12.569
32 11.936 12.990
64 11.915 13.611
LLVM clang
64bit版		 8 13.019 13.217
16 12.724 13.342
32 12.540 13.876
64 12.475 14.818
intel C++ Compiler
32bit版		 8 12.684 13.115
16 12.274 13.418
32 11.986 14.208
64 11.905 15.380
intel C++ Compiler
64bit版		 8 13.386 13.510
16 13.074 13.666
32 12.795 14.395
64 12.519 15.481

グラフを眺めるといろいろ趣深い。

◆挿入ソート，◆選択ソート

6. 結論

  1. 挿入ソートと選択ソートの比較では，挿入ソートのほうが明らかに優れており，さらにその要素数も 16 から 32，64 くらいまで増やしても性能向上の余地があるように見える。おそらく比較のほうがデータ移動よりもはるかに高コストなのだろう。挿入ソートにおけるデータの挿入操作はメモリの連続アクセスになること，直前に比較を行っているので当然キャッシュに乗っていることもあり，意外と低コストで済んでいる様子である。

  2. 一方，選択ソートは要素数を増やすと実行時間が著しく増えるので，8 個のときが一番よい。4 個とかもっと少ないほうが良いかもしれない。

  3. 選択ソートで要素数を増やしたときの実行時間の伸びについて，Visual C++ は 32bit 版も 64bit 版も著しく増加していくのに対し，LLVM clang および intel C++ Compiler の伸びは穏やかである。コンパイラの性能の差が見えているように思える。

  4. 要素数を減らしていくと小型ソートを持たない素のクイックソートの性能に漸近していくだろうから，挿入ソートと選択ソートの曲線は近づくはずで，実際 Visual C++ 32bit 版以外のすべてのコンパイラはほぼ一致する。唯一，Visual C++ 32bit 版のみ選択ソートのほうが優れているのが謎である。おそらくは，Visual C++ 32bit 版コンパイラの能力的な制約により，選択ソートのほうが最適化し易いのだと思われる。であれば，マイクロソフトが uCRT の qsort に選択ソートを採用しているのも理解できる。

つまり .NET Core の挿入ソートを選択ソートに差し替えても速くはならない。ただ，挿入ソートに切り替えるサイズを 16 個から 64 個くらいまでは増やせば性能は漸増する。

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?