はじめに

前回の記事で C# プログラムを作り直した。

当初，一桁くらいの大幅な高速化が期待されたところ，残念ながら 1.5 倍程度しか高速化できなかったのだが，どうやら .NET Framework の Array.Sort が怪しいというところまでは特定できた。ということで今回 .NET Framework の Array.Sort の謎に挑みたいと思う。

.NET Framework の Array.Sort の仕様

マイクロソフトの公式情報¹によると Array.Sort メソッドの仕様は下記の通り。

このメソッドでは、次のようにイントロスペクティブソート(イントロソート)アルゴリズムを使用します。

パーティションサイズが 16 個以下の要素の場合は、挿入並べ替えアルゴリズムが使用されます。

パーティションの数が 2 * LogNを超える場合(N は入力配列の範囲)、Heapsort アルゴリズムを使用します。

それ以外の場合は、Quicksort アルゴリズムを使用します。
この実装では、不安定な並べ替えを実行します。つまり、2 つの要素が等しい場合、順序が保持されない可能性があります。これに対し、安定した並べ替えでは、等しい要素の順序が保持されます。

うん。微妙に分からん。とくにヒープソートが適用される場合の条件がよく分からない。ちなみに英語の原文を読んでも分からなかった。Array.Sort のソースコード²³を読んでみたところ，おそらく以下のようになっている。ここで $n$ はソート対象の配列の要素数，$d$ は再帰関数の呼び出しの深さである。

表１　Array.Sort の実装方法の違い
.NET Framework 4.0 以前	.NET Framework 4.5 以降	.NET Core 以降
クイックソート	クイックソート $d \le 32$	挿入ソート $n \le 16$

		クイックソート $n > 16$ かつ $d \le 2 \log{n}$

	ヒープソート $d > 32$	ヒープソート $d > 2 \log_2{n}$

Visual Studio 2022 uCRT qsort の仕様

次に比較のためC言語，Visual Studio 2022 における uCRT の qsort の仕様⁴を調べてみる。当たり前だがクイックソートを使っていると明言されている。

qsort 関数は、それぞれが width バイトの number 要素から成る配列を並べ替えるためのクイックソートアルゴリズムを実装します。

テストプログラム（C 言語版）のソースコード

比較のため，まずC言語でテストプログラムを作成した。なお，テスト用データ配列の要素数は 17 個とした。これは後出する .NET の Array.Sort では要素数が 16 個以下だと別アルゴリズムが適用されると書いてあったからだ。

なお，テストプログラムではソート関数が呼び出された回数をカウントし，比較対象となる二つの数（およびそれらの差分）を表示するようにした。

qsort.c

#include <stdio.h>
#include <stdlib.h>
//------------------------------------------------------------------------------
// qsort の比較関数
//------------------------------------------------------------------------------
typedef	int (*SORTFUNC)(const void *, const void *);
//------------------------------------------------------------------------------
// テスト用データ配列
//------------------------------------------------------------------------------
static	int	table[] = {
	9, 15, 16, 14, 11, 12, 7, 13, 10, 0, 8, 5, 6, 1, 4, 3, 2
};
#define	countof(a)	(sizeof(a)/sizeof(a[0]))
//------------------------------------------------------------------------------
// ソート関数を呼び出した回数
//------------------------------------------------------------------------------
static	int	count = 0;
//------------------------------------------------------------------------------
// ソート関数
//------------------------------------------------------------------------------
static	int	sortfunc(int *p, int *q) {
	count++;
	fprintf(stdout, "%d\t%d\t%d\n", *p, *q, *p - *q);
	return *p - *q;
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
int	main() {
	//--------------------------------------------------------------------------
	// 配列 table をソートする
	//--------------------------------------------------------------------------
	qsort(table, countof(table), sizeof(table[0]), (SORTFUNC)sortfunc);
	//--------------------------------------------------------------------------
	// ソート関数を呼び出した回数
	//--------------------------------------------------------------------------
	fprintf(stdout, "%d\n", count);
	return 0;
}

テストプログラム（C 言語版）の実行結果

テストプログラムの実行結果を以下に示す。まず，最初の３つに着目する。クイックソートの基本アルゴリズムは文献⁵あたりを参照して欲しいが，境界値（ピボットという）の値が非常に重要とされる。クイックソートの時間計算量は平均的に $O(N\log{N})$ とされているが，ピボットの値が最小値または最大値の場合 $O(N^2)$ となってしまうからだ。これを避けるための対策として，

配列の一部の要素を選び、それらの中央値を選ぶ（典型的には、配列の先頭・中間・末尾の3要素の中央値）

という案が挙げられている。実際，下記の最初の３回の比較要素を見てみると，見事に先頭 table[0] = 9，中間 table[8] = 10，末尾 table[16] = 2 の値を比較していることが分かる。

ソート関数を合計 78 回呼び出した。簡単のため途中を省略したが，同じ要素を比較することは一度もなかったことを断っておく。

テストプログラム（C# 版）のソースコード

先ほどのテストプログラムの C# 版である。

arraysort.cs

using System;
using System.IO;
class ArraySort {
	static	int	Main() {
		//----------------------------------------------------------------------
		// テスト用データ配列
		//----------------------------------------------------------------------
		var	table = new int[] {
			9, 15, 16, 14, 11, 12, 7, 13, 10, 0, 8, 5, 6, 1, 4, 3, 2
		};
		//----------------------------------------------------------------------
		// ソート関数を呼び出した回数
		//----------------------------------------------------------------------
		int	count = 0;
		//----------------------------------------------------------------------
		// ソート関数
		//----------------------------------------------------------------------
		Comparison<int>	sortfunc = delegate(int p, int q) {
			count++;
			Console.Out.WriteLine("{0}\t{1}\t{2}", p, q, p - q);
			return p - q;
		};
		//----------------------------------------------------------------------
		// 配列 table をソートする
		//----------------------------------------------------------------------
		Array.Sort(table, sortfunc);
		//----------------------------------------------------------------------
		// ソート関数を呼び出した回数
		//----------------------------------------------------------------------
		Console.Out.WriteLine(count);
		return 0;
	}
}

テストプログラム（C# 版）の実行結果

テストプログラムの実行結果を以下に示す。驚いたことに最初の３つはC言語版と全く同じである。

ところが，４つ目以降の比較要素は全く異なる。ソート関数の呼び出し回数が 78 → 106 回に増えており，一見無駄だと思われる同一要素を比較しているケースが目につく。

上記は .NET Framework 4.8 の結果である。

結論

.NET Framework の Array.Sort では，差がゼロとなることが分かり切っているにも関わらず，全くの同一要素の比較を行う場合があるのだ。

これが .NET Framework の欠陥なのか，あるいはこのほうが効率良いからなのかは分からない。ただ，このような特質が分かれば対策はできる。上記 Rev.3 のプログラムの下記関数に一行を追加するだけでいい。

ソート関数の修正版

 Comparison<int> compareIndex = delegate(int a, int b) {
+    if(a == b) return 0;
     var lret = filesize[a] - filesize[b];
     /**/ if(lret > 0) return  1;
     else if(lret < 0) return -1;
     var iret = compareHash(a, b);
     /**/ if(iret != 0)
         return iret;
     else if(classicCompare)
         return string.Compare(filename[a], filename[b], StringComparison.OrdinalIgnoreCase);
     else
         return LogicalStringComparer.Compare(filename[a], filename[b]);
 };

Rev.4 のコード全体を以下に示す。

詳しくはコチラ

UniqFile.CS Rev.4

using System;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Runtime.InteropServices;
using VbFileIO = Microsoft.VisualBasic.FileIO;
//------------------------------------------------------------------------------
// VisualBasic ライブラリクラス
//------------------------------------------------------------------------------
class VbLib {
	//--------------------------------------------------------------------------
	// ファイルをゴミ箱へ移動する
	//--------------------------------------------------------------------------
	public	static	void	RemoveFile(string path) {
		VbFileIO.FileSystem.DeleteFile(path,
			VbFileIO.UIOption.OnlyErrorDialogs,
			VbFileIO.RecycleOption.SendToRecycleBin);
	}
}
//------------------------------------------------------------------------------
// Explorer 互換ソートクラス
//------------------------------------------------------------------------------
class LogicalStringComparer {
	[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
	extern	static	int	StrCmpLogicalW(string s1, string s2);
	public	static	int	Compare(string s1, string s2) {
		return StrCmpLogicalW(s1, s2);
	}
}
//------------------------------------------------------------------------------
// 大文字・小文字を区別しない比較クラス
//------------------------------------------------------------------------------
class IgnoreCaseComparer : IEqualityComparer<string> {
	public	bool	Equals(string s1, string s2) {
		return string.Equals(s1, s2, StringComparison.OrdinalIgnoreCase);
	}
	public	int	GetHashCode(string s) {
		return s.ToUpper().GetHashCode();
	}
}
//------------------------------------------------------------------------------
// エントリポイントを持つクラス
//------------------------------------------------------------------------------
class UNIQFILE {
	//--------------------------------------------------------------------------
	// 関数内関数を実現する delegate
	//--------------------------------------------------------------------------
	delegate	byte[]	ComputeHash(int n);			// ハッシュ値を計算する
	delegate	int		CompareHash(int a, int b);	// ハッシュ値を比較する
	//--------------------------------------------------------------------------
	// メイン関数
	//--------------------------------------------------------------------------
	static	int	Main(string[] args) {
		//----------------------------------------------------------------------
		// ヘルプメッセージ
		//----------------------------------------------------------------------
		if(args.Length < 1) {
			Console.Error.WriteLine("重複するファイルを削除します。");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("UNIQFILE(.EXE) (オプション) [ファイル名] ...");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("＜オプション＞");
			Console.Error.WriteLine("/C　ファイル名のソートを従来方式（単純な文字列比較）で行います。");
			Console.Error.WriteLine("　　デフォルトは Explorer 互換アルゴリズムで比較します。");
			Console.Error.WriteLine("/S　ファイルを再帰的に検索します。");
			Console.Error.WriteLine("/T　ファイルをゴミ箱に移動します。");
			Console.Error.WriteLine("/V　ファイルを削除しません。");
			Console.Error.WriteLine("");
			Console.Error.WriteLine("＜注意事項＞");
			Console.Error.WriteLine("・ファイルの内容が重複する場合，ファイル名を昇順にソートして");
			Console.Error.WriteLine("　先頭のファイルのみ残し，残りのファイルは削除します。");
			Console.Error.WriteLine("・複数のファイル名を指定できます。");
			Console.Error.WriteLine("・ファイル名の指定にはワイルドカードを使用できます。");
			return -1;
		}
		//----------------------------------------------------------------------
		// ファイル一覧を作成する
		//----------------------------------------------------------------------
		bool	classicCompare  = false;	// ファイル名のソートを単純な文字列比較で行います。
		bool	recursiveSearch = false;	// ファイルを再帰的に検索します。
		bool	trashBoxMode    = false;	// ファイルをゴミ箱に移動します。
		bool	viewOnlyMode    = false;	// ファイルを削除しません。
		var		list = new List<string>();	// ファイル名（ワイルドカード可）
		for(int i = 0; i < args.Length; i++) {
			string	s = args[i];
			if(s[0] == '/' || s[0] == '-') {
				switch(s[1]) {
				  case 'C': case 'c':	classicCompare  = true;	break;
				  case 'S': case 's':	recursiveSearch = true;	break;
				  case 'T': case 't':	trashBoxMode    = true;	break;
				  case 'V': case 'v':	viewOnlyMode    = true;	break;
				  default:
					Console.Error.WriteLine("不正なオプション {0} を指定しました!!", s);
					return -1;
				}
			} else {
				list.Add(s);
			}
		}
		if(list.Count == 0) {
			Console.Error.WriteLine("ファイル名を指定して下さい!!");;
			return -1;
		}
		//----------------------------------------------------------------------
		// ファイル一覧の作成
		//----------------------------------------------------------------------
		var	filename = new List<string>();
		var	opt = recursiveSearch
				? SearchOption.AllDirectories
				: SearchOption.TopDirectoryOnly;
		for(int i = 0; i < list.Count; i++) {
			var	s = list[i];
			var	path = Path.GetDirectoryName(s);
			var	file = Path.GetFileName(s);
			if(path == "") {
				path = ".";
			} else if(!Directory.Exists(path)) {
				Console.Error.WriteLine("ディレクトリ {0} は存在しません!!", path);
				return -1;
			}
			path = Path.GetFullPath(path);
			filename.AddRange(Directory.GetFiles(path, file, opt));
		}
		filename = filename.Distinct(new IgnoreCaseComparer()).ToList();
		if(filename.Count == 0) {
			Console.Error.WriteLine("ファイルが見つかりません!!");
			return -1;
		} else if( filename.Count == 1) {
			Console.Error.WriteLine("ファイル数が不足しています!!");
			return -1;
		}
		//----------------------------------------------------------------------
		// ファイルサイズを取得する
		//----------------------------------------------------------------------
		var	filesize = new long[filename.Count];
		for(int i = 0; i < filename.Count; i++) {
			if(!File.Exists(filename[i])) {
				Console.Error.WriteLine("ファイル {0} が存在しません!!", filename[i]);
				return -1;
			}
			var	info = new FileInfo(filename[i]);
			filesize[i] = info.Length;
		}
		//----------------------------------------------------------------------
		// MD5によるハッシュ値を生成する
		//----------------------------------------------------------------------
		var	md5 = MD5.Create();
		var	hash = new byte[filename.Count][];
		for(int i = 0; i < filename.Count; i++)
			hash[i] = null;
		//----------------------------------------------------------------------
		// ハッシュ値を計算するローカル関数
		//----------------------------------------------------------------------
		ComputeHash	computeHash = delegate(int n) {
			byte[]	bytes = File.ReadAllBytes(filename[n]);
			return md5.ComputeHash(bytes);
		};
		//----------------------------------------------------------------------
		// ハッシュ値を比較するローカル関数
		//----------------------------------------------------------------------
		CompareHash	compareHash = delegate(int a, int b) {
			if(hash[a] == null) hash[a] = computeHash(a);
			if(hash[b] == null) hash[b] = computeHash(b);
			for(int i = 0; i < hash[a].Length; i++) {
				int	ret = hash[a][i] - hash[b][i];
				if(ret != 0) return ret;
			}
			return 0;
		};
		//----------------------------------------------------------------------
		// ソート関数の定義
		//----------------------------------------------------------------------
		Comparison<int>	compareIndex = delegate(int a, int b) {
			if(a == b) return 0;
			var	lret = filesize[a] - filesize[b];
			/**/ if(lret > 0) return  1;
			else if(lret < 0) return -1;
			var	iret = compareHash(a, b);
			/**/ if(iret != 0)
				return iret;
			else if(classicCompare)
				return string.Compare(filename[a], filename[b], StringComparison.OrdinalIgnoreCase);
			else
				return LogicalStringComparer.Compare(filename[a], filename[b]);
		};
		//----------------------------------------------------------------------
		// インデクスをソートする
		//----------------------------------------------------------------------
		var	index = new int[filename.Count];
		for(int i = 0; i < index.Length; i++)
			index[i] = i;
		Array.Sort(index, compareIndex);
		//----------------------------------------------------------------------
		// ファイルサイズおよびハッシュ値の重複するファイルを削除する
		//----------------------------------------------------------------------
		int	count = 0, prev = -1;
 		for(int i = 0; i < index.Length; i++) {
			int	n = index[i];
			Console.Out.Write("{0, 12:#,##0} {1} {2}",
				filesize[n],
				hash[n] == null ? new string('-', 32)
								: BitConverter.ToString(hash[n]).Replace("-", ""),
				Path.GetFileName(filename[n]));
			string	s = "";
			if(prev >= 0 && filesize[n] == filesize[prev] && compareHash(n, prev) == 0) {
				/*--*/ if(viewOnlyMode) {
					s = " ... (*)";		/* 何もしない */
				} else if(trashBoxMode) {
					s = " ... (TRASH)";	VbLib.RemoveFile(filename[n]);
				} else {
					s = " ... DELETED";	File.Delete(filename[n]);
				}
				count++;
			}
			Console.Out.WriteLine(s);
			prev = n;
		}
		//----------------------------------------------------------------------
		// メッセージ出力
		//----------------------------------------------------------------------
		string	format = count == 0   ? "全ファイル {0} 個のうち，重複ファイルはありません。"
					   : viewOnlyMode ? "全ファイル {0} 個のうち，重複ファイル {1} 個を削除できます。"
					   : trashBoxMode ? "全ファイル {0} 個のうち，重複ファイル {1} 個をゴミ箱に送りました。"
					   :                "全ファイル {0} 個のうち，重複ファイル {1} 個を削除しました。";
		Console.Out.WriteLine(format, index.Length, count);
		return 0;
	}
}

Rev.4 の結果を示す。優先してファイルサイズで比較し，ファイルサイズが一致する場合のみハッシュ値を計算していることが分かる。

処理時間は Rev.2 の約 5 倍，Rev.3 の約 3 倍速くなった。ちなみに大半は画面出力が占めており，標準出力をファイルにリダイレクトすれば 100[ms] もかからない。

UNIQFILE Rev.4 の実行結果

～中略～
     825,718 -------------------------------- 148-149.JPG
     826,434 -------------------------------- 056-057.JPG
     826,608 7F04A672DCF68DF97A94F0CF7DF695BA 092-093.JPG
     826,608 A96CB6C51A9942DB0F44D28FCAE2682A 046-047.JPG
     828,328 -------------------------------- 040-041.JPG
     828,469 -------------------------------- 126-127.JPG
～中略～
   2,352,127 -------------------------------- 072-073.JPG
   2,372,063 -------------------------------- 088-089.JPG
   2,404,810 -------------------------------- 144-145.JPG
   2,431,600 -------------------------------- 088-089.JPG
   2,461,879 -------------------------------- 146-147.JPG
   2,486,408 -------------------------------- 162-163.JPG
   2,557,145 -------------------------------- 080-081.JPG
   2,568,829 -------------------------------- 120-121.JPG
   2,599,109 -------------------------------- 142-143.JPG
   2,645,270 -------------------------------- 058-059.JPG
全ファイル 1845 個のうち，重複ファイルはありません。
実行時間：1,100[ms]／00:00:01.100[s]

なお，.NET Framework の Array.Sort のアルゴリズムの詳細については引き続き調査中である。進展があり次第，後日，続報記事を書きたいと思う。