はじめに
筆者の過去記事の続きである。
.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#版
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言語版
#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
下記のプロジェクトファイルをソースコードと同じフォルダに置くこと。
<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)$ で収まっており，途中でヒープソートに切り替わっていることが分かる。
| 要素数 $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$ の対数に比例するので両者の違いが表れている。
