LoginSignup
5
2

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

はじめに

筆者の過去記事の続きである。

.NET Framework 4.5 以降の Array.Sort はイントロソートを採用しており，平均的なデータに対しては高速とされるクイックソートでソートを開始するが，クイックソートでは時間がかかる場合は途中でヒープソートに切り替わる。

.NET Framework 4.8 の Array.Sort では，単に再帰関数の呼び出し深さが 32 を超えるとヒープソートに切り替えるため，ある程度以上の大規模なデータを与えてやればヒープソートに切り替わる。

しかし，.NET Core 以降では，ヒープソートへ切り替わる再帰関数の呼び出し深さは与えたデータ点数の対数に比例するようになっており，単に大規模な乱数データを与えただけではヒープソートへの切り替えを確認できなかった。

本当にヒープソートに切り替わるのか確認するため，クイックソートでは $O(n^2)$ の時間がかかるようなデータを作成したい。

クイックソートの原理

クイックソートとはピボットと呼ばれる数値を選び，ピボットと配列のデータの大小比較を行って領域を二つのグループに分ける。そして分割したグループ毎に新たにピボットを選んで領域を細分割していくという再帰的なアルゴリズムである。理想としては二つの領域を等分割したいが，無作為に選んだピボットが都合よく領域の中央値になるとは限らないので，一般的には非均等分割になる。しかし，平均的には等分割される場合と大差なく $O(n \log n)$ の計算量で済むことが期待されている。しかし，選んだピボットが運悪く領域の最小値または最大値であり続ける●●●●●と $O(n^2)$ の計算量になってしまう。

このようにピボットが領域の最小値または最大値であり続ける●●●●●最悪なデータを作成するにはどうすれば良いだろうか？

ソースコードが公開されているものについては，そのアルゴリズムに応じて最悪データを作ればよい。たいていの実装ではピボットの値が偏らないように先頭と末尾，そして中間の三点でサンプリングを行うが，uCRT の qsort と .NET の Array.Sort では中間サンプリングの位置が異なる。配列の要素数 $n$ とおくと uCRT の qsort の中間サンプリング位置は $n / 2$ なのに対し，.NET の Array.Sort は $(n - 1) / 2$ なので，$n$ が偶数の場合は一つずれるのだ。

という訳で各実装に応じてデータを作るのは面倒だなと思っていた。

クイックソートキラーの原理

先日，クイックソートキラーの存在を知った。たいていのクイックソート関数は任意の比較関数を指定できるので，その比較関数にピボット位置を探すコードを仕込ませるというアイディアだ12。

クイックソートでは最初期にピボットとなる値を決め，ピボットを基準として全データを舐めるように比較していくので，最初期に呼び出されるのがピボット（候補）であり，ピボットにはできるだけ小さな値を割り当てる。以後，ピボットとの比較を繰り返すが，ピボットと比較される値については具体的な値を決めずに（遅延評価）ピボットが最小値であることから大小関係のみを返してやればいい。

コレ，最初に思いついた人天才だな。

アルゴリズム概要

参考文献のサイトを自分なりに解釈して作り直したものを以下示す。

1. 初期化

配列の要素数 size として，クイックソートに引き渡すダミー配列 dummy[] とピボットの値を割り当てる配列 pivot[] を確保する。ダミー配列 dummy[] は昇順データとし，ピボット配列 pivot[] は未定義値として負の値で初期化する。

初期化
var dummy = new int[size];
var pivot = new int[size];
for(int i = 0; i < size; i++) dummy[i] = i;
for(int i = 0; i < size; i++) pivot[i] = -1;

2. キラー関数

二つの引数がいずれも未定義の場合，両者をピボット（候補）として値を割り当てる。割り当てる値は最初期がもっとも小さく，徐々に大きくしていく。

二つの引数のうち一方がピボットの場合，もう一方の値は具体的に決めず（遅延評価），ピボットのほうが必ず小さいものとして大小関係のみを返す。

ピボット同士を比較する場合のみ割り当てた値同士で比較する。

キラー関数
int     index = 0;
Comparison<int> killer = delegate(int a, int b) {
    if(pivot[a] < 0 && pivot[b] < 0) {
        pivot[a] = index++;
        pivot[b] = index++;
        return -1;
    }
    if(pivot[a] < 0) return  1;
    if(pivot[b] < 0) return -1;
    return pivot[a] - pivot[b];
};
Array.Sort(dummy, killer);

ちなみに，この実行自体 $O(n^2)$ の計算量を要する。

3. 最悪データの作成

上記のアルゴリズムに沿ってソートを行うと，もともと昇順でソートされていたダミー配列 dummy[] は一見デタラメな順にシャッフルされたように見えるが，$O(n^2)$ の計算量を要するようにソートされた結果であり，貴重な情報を内包している。

ソート後のダミー配列 dummy[] をソート前の状態に戻す逆関数を考えると，昇順ソート済みの配列に同じ逆関数を与えたものが最悪データ worst[] となる。こうして作成した最悪データ worst[] を単に昇順ソートさせるだけで $O(n^2)$ の計算量を要するのだ。

最悪データの作成
var worst = new int[size];
for(int i = 0; i < size; i++)
    worst[dummy[i]] = i;

4. 備考

なお，ピボット候補に値を割り当てた pivot[] をそのまま最悪データとして使っても良いように思える。なぜなら，上記の手順で求めた最悪データ worst[] と同様な値を得られるからだ。

ただし，今回たまたま●●●●同じ値を得られたに過ぎない。配列のサイズやクイックソートの実装によっては pivot[] に初期値 -1 がそのまま残ってしまう場合がある。なので，pivot[] を利用したい場合は未定義の初期値には -1 ではなく，配列の大きさ size，あるいはいっそのこと整数最大値である INT_MAX のような大きな値を与えたほうが良いだろう。

なお，筆者の確認したところ，uCRT の qsort および .NET Framework 3.5 の Array.Sort の場合，与えた配列のサイズが偶数の場合は worst[] と同じ値が得られるが，奇数の場合は pivot[] に -1 が現れてしまうようだ。

サンプルコード

サンプルコードを以下に示す。C#版とC言語版の二種類を作成した。

サンプルC#版
ArraySortKiller.cs
using System;
using System.IO;
class ArraySortKiller {
	static	int		Main(string[] args) {
		if(args.Length == 0) {
			Console.Error.WriteLine("Usage: ArraySortKiller(.exe) [size]");
			return -1;
		}
		var	size = int.Parse(args[0]);
		var	dummy = new int[size];
		var	pivot = new int[size];
		for(int i = 0; i < size; i++) dummy[i] = i;
		for(int i = 0; i < size; i++) pivot[i] = -1;
		int		index = 0;
		Comparison<int>	killer = delegate(int a, int b) {
			if(pivot[a] < 0 && pivot[b] < 0) {
				pivot[a] = index++;
				pivot[b] = index++;
				return -1;
			}
			if(pivot[a] < 0) return  1;
			if(pivot[b] < 0) return -1;
			return pivot[a] - pivot[b];
		};
		Array.Sort(dummy, killer);
		var	worst = new int[size];
		for(int i = 0; i < size; i++)
			worst[dummy[i]] = i;
		long	count = 0;
		Comparison<int>	compare = delegate(int a, int b) {
			count++;
			return a - b;
		};
		Array.Sort(worst, compare);
		Console.Out.WriteLine(count);
		return 0;
	}
}
サンプルC言語版
QsortKiller.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
static	int			*dummy = (int*)NULL;
static	int			*pivot = (int*)NULL;
static	int			*table = (int*)NULL;
static	int			index = 0;
static	uint64_t	count = 0;
static	int		killer(const int *p, const 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];
}
static	int		compare(const int *p, const int *q) {
	count++;
	return *p - *q;
}
int	main(int argc, char *argv[]) {
	if(argc < 2) {
		fprintf(stderr, "Usage: QsortKiller(.exe) [size]");
		return -1;
	}
	int	size = atoi(argv[1]);
	if((int*)NULL == (dummy = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	if((int*)NULL == (pivot = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	for(int i = 0; i < size; i++) dummy[i] = i;
	for(int i = 0; i < size; i++) pivot[i] = -1;
	qsort(dummy, size, sizeof(int), killer);
	free(pivot);
	if((int*)NULL == (worst = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	for(int i = 0; i < size; i++)
		worst[dummy[i]] = i;
	free(dummy);
	count = 0;
	qsort(worst, size, sizeof(int), compare);
	fprintf(stdout, "%lld\n", count);
	return 0;
}

ビルド手順

Visual C++ の場合

下記のコマンドを実行する。

cl /O2 /W4 QsortKiller.c

.NET Framework 3.5 の場合

下記のバッチファイルを実行する。

@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v3.5" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET35 mkdir NET35
csc -o -w:4 -out:NET35\ArraySortKiller.exe ArraySortKiller.cs
endlocal
exit /b

.NET Framework 4.8 の場合

下記のバッチファイルを実行する。

@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET48 mkdir NET48
csc -o -w:4 -out:NET48\ArraySortKiller.exe ArraySortKiller.cs
endlocal
exit /b

.NET 8.0 の場合

下記のコマンドを実行する。

dotnet build -c Release

下記のプロジェクトファイルをソースコードと同じフォルダに置くこと。

ArraySortKiller.csproj
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
    <EnableDefaultCompileItems>false</EnableDefaultCompileItems>
  </PropertyGroup>
  <ItemGroup>
    <Compile Include="ArraySortKiller.cs" />
  </ItemGroup>
</Project>

実行結果

実行結果を以下に示す。uCRT の qsort および .NET Framework 3.5 の Array.Sort は見事に $O(n^2) \approx n^2/4 $ の計算量（比較関数の呼び出し回数）となっていることが分かる。一方，.NET Framework 4.8 および .NET8.0 のほうは $O(n \log n)$ で収まっており，途中でヒープソートに切り替わっていることが分かる。

表１　QuickSort Killer を用いたときの比較関数の呼び出し回数
要素数
$n$		 Visual C++
qsort (uCRT)		 .NET
Framework
3.5		 .NET
Framework
4.8		 .NET8.0
10 39 65 65 13
20 124 195 195 64
50 679 885 885 650
100 2,604 3,035 2,769 1,867
200 10,204 11,085 7,137 4,837
500 63,004 65,235 21,266 15,155
1,000 251,004 255,485 46,197 34,960
2,000 1,002,004 1,010,985 97,951 78,647
5,000 6,255,004 6,277,485 261,268 231,444
10,000 25,010,004 25,054,985 544,536 505,168
20,000 100,020,004 100,109,985 1,130,597 1,090,906
50,000 625,050,004 625,274,985 2,960,700 2,960,448
100,000 2,500,100,004 2,500,549,985 6,125,482 6,326,338
200,000 10,000,200,004 10,001,099,985 12,661,996 13,466,784
500,000 62,500,500,004 62,502,749,985 32,968,189 35,977,618
1,000,000 250,001,000,004 250,005,499,985 67,979,733 75,964,727

.NET Framework 4.8 と .NET8.0 で比較関数の呼び出し回数を比較してみると，$n$ が小さいときは .NET 8.0 のほうが少なく，$n$ が大きくなると逆転していることが分かる。このことから，ヒープソートに切り替わる条件が両者で異なっていることが分かる。.NET Framework 4.8 のほうは $n$ に関係なく再帰関数の呼び出し深さで決まっているので，$n$ が小さいときはなかなかヒープソートに切り替わらないが，$n$ が大きくなると早めに切り替わる。一方，.NET8.0 のほうは切り替え点が $n$ の対数に比例するので両者の違いが表れている。

  1. A Killer Adversary for Quicksort ↩

  2. クイックソートを攻略してみた - Zenn ↩

5
2
3

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
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?