wizaman's blog (legacy) （2017/09/10 パフォーマンス比較にOrderByを追加。それに伴い、結論をやや修正）
ListとLinkedListの挿入ソートおよびマージソートを実装します。どちらも安定ソートです。
何を考えて実装したのか、長々と別の記事に書いてあるので、興味があればそっちもよろしくです。
マージソートを単純に実装するより、対象となる要素数が少ない時は挿入ソートのほうが速いので、挿入ソートに差し替える対応をします。なので、マージソートの実装がメインで、最適化の副産物で挿入ソートもあるよ、という感じです。
実装
拡張メソッドとして、ListとLinkedListに挿入ソート（insertionSort）とマージソート（mergeSort）を実装します。マージソートは再帰処理をしない方法で実装します。
また、高速化のため、要素数が閾値以下の部分リストに対しては、挿入ソートを適用します。挿入ソートに差し替えたくなければ、閾値を1にします。実装コード中に定義されているデフォルトの閾値は、私の環境で計測した結果を見て、良さそうな値を入れています。なんとなく2のべき乗を選んでいますが、2のべき乗でないと動かないというわけではないです。
ComparisonのIComparer変換のため、下記クラスを使います。今回の性能テストでは使ってませんが。
public class FunctorComparer<T> : IComparer<T>
{
public FunctorComparer(Comparison<T> comparison)
{
_comparison = comparison;
}
public int Compare(T x, T y)
{
return _comparison(x, y);
}
private Comparison<T> _comparison = null;
}List
マージソートは再帰処理をする実装がよく知られていますが、最小部分リストから範囲を倍にしていけばループで書けるので、非再帰処理として実装しました。これで前方部分リストを詰めるためのバッファの確保は一度にまとまります。
public static class ListExtension
{
#region 定数
// マージソートの代わりに挿入ソートを適用する要素数
private const int insertionSortThreshold = 4;
#endregion
#region 要素の取得
public static T first<T>(this List<T> list)
{
return list[0];
}
public static T last<T>(this List<T> list)
{
return list[list.Count - 1];
}
#endregion
#region ソート
#region 挿入ソート
public static void insertionSort<T>(this List<T> list)
{
insertionSort(list, 0, list.Count, null);
}
public static void insertionSort<T>(this List<T> list, Comparison<T> comparison)
{
if(list.Count <= 1) return;
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
insertionSort(list, comparer);
}
public static void insertionSort<T>(this List<T> list, IComparer<T> comparer)
{
insertionSort(list, 0, list.Count, comparer);
}
public static void insertionSort<T>(this List<T> list, int index, int count, IComparer<T> comparer)
{
if(count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
insertionSortUnsafe(list, index, count, comparer);
}
private static void insertionSortUnsafe<T>(this List<T> list, int index, int count, IComparer<T> comparer)
{
var end = index + count;
for(var i = index + 1; i < end; ++i) {
var value = list[i];
if(comparer.Compare(list[i - 1], value) > 0) {
var j = i;
do {
list[j] = list[j - 1];
--j;
} while(j > index && comparer.Compare(list[j - 1], value) > 0);
list[j] = value;
}
}
}
#endregion
#region マージソート
public static void mergeSort<T>(this List<T> list, int minUnit = insertionSortThreshold)
{
mergeSort(list, 0, list.Count, null, minUnit);
}
public static void mergeSort<T>(this List<T> list, Comparison<T> comparison, int minUnit = insertionSortThreshold)
{
if(list.Count <= 1) return;
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
mergeSort(list, comparer, minUnit);
}
public static void mergeSort<T>(this List<T> list, IComparer<T> comparer, int minUnit = insertionSortThreshold)
{
mergeSort(list, 0, list.Count, comparer, minUnit);
}
public static void mergeSort<T>(this List<T> list, int index, int count, IComparer<T> comparer, int minUnit = insertionSortThreshold)
{
if(count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
if(minUnit < 1) {
minUnit = 1;
}
// 全体要素数が少なければ挿入ソート
if(count <= minUnit) {
insertionSortUnsafe(list, index, count, comparer);
return;
}
var end = index + count;
var work = new T[count];
// 少ない要素数の部分リストは挿入ソートを適用
if(minUnit > 1) {
for(var i = index; i < end; i += minUnit) {
var subEnd = i + minUnit;
if(subEnd < end) {
insertionSortUnsafe(list, i, minUnit, comparer);
} else {
// 末尾の部分リストはサイズが中途半端になることがある
var subCount = end - i;
if(subCount > 1) {
insertionSortUnsafe(list, i, subCount, comparer);
}
break;
}
}
}
// nは部分リストの長さ
// 1, 2, 4, ... というように2倍されていく
for(var n = minUnit; n < count; n <<= 1) {
// 長さnの部分リストに分割されている前提で、2組ずつソートしていく
var n_x2 = n << 1;
for(var begin1 = index; begin1 <= end - n; begin1 += n_x2) {
var begin2 = begin1 + n;
// 前方部分リストをバッファに詰める
list.CopyTo(begin1, work, 0, n);
var i = begin1;
// 前方部分リスト（バッファ）の範囲
var i1 = 0;
var end1 = n;
// 後方部分リストの範囲
var i2 = begin2;
var end2 = i2 + n;
if(end2 > end) {
end2 = end;
}
// マージ
while(i1 < end1 && i2 < end2) {
var value1 = work[i1];
var value2 = list[i2];
if(comparer.Compare(value1, value2) > 0) {
list[i] = value2;
++i2;
} else {
list[i] = value1;
++i1;
}
++i;
}
// バッファに残った要素の追加
while(i1 < end1) {
list[i] = work[i1];
++i1;
++i;
}
}
}
}
#endregion
#endregion
}LinkedList
List向けに実装した処理をLinkedList向けに直しました。LinkedListなら挿入が簡単ですが、その結果として先頭ノードが変わることがあるのがややこしいです。ランダムアクセスできないのが弱みなので、なるべく無駄なループは排除するよう配慮しました。
LinkedListNodeはほとんどのメンバがinternalで定義されていて外から直接触れないので、面倒ですがRemove()してからAddBefore()という手順で挿入をしています。すごく無駄な気がしますが仕方ない。
ちなみに、LinkedListに実装した挿入ソートおよびマージソートはアロケーションしません。
挿入ソート、マージソートのほか、arraySortを実装していますが、これは全要素をListに詰めてSort()したものをLinkedListに入れ直す処理です。そのため、In-placeではないし、不安定ソートです。性能比較で使います。
public static class LinkedListExtension
{
#region 定数
// マージソートの代わりに挿入ソートを適用する要素数
private const int insertionSortThreshold = 8;
#endregion
#region 内部クラス
private struct BeginAndEndNodes<T>
{
public LinkedListNode<T> begin;
public LinkedListNode<T> end;
public BeginAndEndNodes(LinkedListNode<T> begin, LinkedListNode<T> end)
{
this.begin = begin;
this.end = end;
}
}
#endregion
#region ソート
#region Listによるソート
public static void arraySort<T>(this LinkedList<T> list)
{
IComparer<T> comparer = null;
arraySort(list, comparer);
}
public static void arraySort<T>(this LinkedList<T> list, Comparison<T> comparison)
{
if(list.Count <= 1) return;
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
arraySort(list, comparer);
}
public static void arraySort<T>(this LinkedList<T> list, IComparer<T> comparer)
{
if(list.Count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
var work = new List<T>(list);
work.Sort(comparer);
list.Clear();
var count = work.Count;
for(var i = 0; i < count; ++i) {
var value = work[i];
list.AddLast(value);
}
}
#endregion
#region 挿入ソート
public static void insertionSort<T>(this LinkedList<T> list)
{
insertionSort(list.First, list.Count, null);
}
public static void insertionSort<T>(this LinkedList<T> list, Comparison<T> comparison)
{
if(list.Count <= 1) return;
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
insertionSort(list, comparer);
}
public static void insertionSort<T>(this LinkedList<T> list, IComparer<T> comparer)
{
insertionSort(list.First, list.Count, comparer);
}
public static void insertionSort<T>(this LinkedList<T> list, int index, int count, IComparer<T> comparer)
{
if(count <= 1) return;
var node = list.First;
for(var i = 1; i < index; ++i) {
node = node.Next;
}
insertionSort(node, count, comparer);
}
private static void insertionSort<T>(this LinkedListNode<T> begin, int count, IComparer<T> comparer)
{
if(count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
insertionSortUnsafe(begin, count, comparer);
}
private static BeginAndEndNodes<T> insertionSortUnsafe<T>(this LinkedListNode<T> begin, int count, IComparer<T> comparer)
{
if(count <= 1) {
return new BeginAndEndNodes<T>(begin, (count == 1) ? begin.Next : begin);
}
var list = begin.List;
var node = begin.Next;
for(var i = 1; i < count; ++i) {
var next = node.Next;
var target = node.Previous;
if(comparer.Compare(target.Value, node.Value) > 0) {
while(target != begin && comparer.Compare(target.Previous.Value, node.Value) > 0) {
target = target.Previous;
}
list.Remove(node);
list.AddBefore(target, node);
if(target == begin) {
begin = node;
}
}
node = next;
}
return new BeginAndEndNodes<T>(begin, node);
}
#endregion
#region マージソート
public static void mergeSort<T>(this LinkedList<T> list, int minUnit = insertionSortThreshold)
{
mergeSort(list, 0, list.Count, null, minUnit);
}
public static void mergeSort<T>(this LinkedList<T> list, Comparison<T> comparison, int minUnit = insertionSortThreshold)
{
if(list.Count <= 1) return;
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
mergeSort(list, comparer, minUnit);
}
public static void mergeSort<T>(this LinkedList<T> list, IComparer<T> comparer, int minUnit = insertionSortThreshold)
{
mergeSort(list, 0, list.Count, comparer, minUnit);
}
public static void mergeSort<T>(this LinkedList<T> list, int index, int count, IComparer<T> comparer, int minUnit = insertionSortThreshold)
{
if(count <= 1) return;
var node = list.First;
for(var i = 1; i < index; ++i) {
node = node.Next;
}
mergeSort(node, count, comparer, minUnit);
}
public static void mergeSort<T>(this LinkedListNode<T> begin, int count, IComparer<T> comparer, int minUnit = insertionSortThreshold)
{
if(count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
if(minUnit < 1) {
minUnit = 1;
}
// 全体要素数が少なければ挿入ソート
if(count <= minUnit) {
insertionSortUnsafe(begin, (int)count, comparer);
return;
}
// 少ない要素数の部分リストは挿入ソートを適用
if(minUnit > 1) {
var node = begin;
for(var i = 0; i < count; i += minUnit) {
var subEnd = i + minUnit;
if(subEnd < count) {
var nodes = insertionSortUnsafe(node, minUnit, comparer);
if(node == begin) {
begin = nodes.begin;
}
node = nodes.end;
} else {
// 末尾の部分リストはサイズが中途半端になることがある
var subCount = count - i;
if(subCount > 1) {
insertionSortUnsafe(node, subCount, comparer);
}
break;
}
}
}
var list = begin.List;
// nは部分リストの長さ
// 1, 2, 4, ... というように2倍されていく
for(var n = minUnit; n < count; n <<= 1) {
// 長さnの部分リストに分割されている前提で、2組ずつソートしていく
var node1 = begin;
for(var begin1 = 0; begin1 <= count - n; begin1 += n << 1) {
var begin2 = begin1 + n;
// 前方部分リストの範囲
var i1 = begin1;
var end1 = i1 + n;
// 後方部分リストの範囲
var i2 = begin2;
var end2 = i2 + n;
if(end2 > count) {
end2 = count;
}
// 後方リストの先頭要素を取得
var node2 = node1.Next;
for(var i = 1; i < n; ++i) {
node2 = node2.Next;
}
// マージ
while(i1 < end1 && i2 < end2) {
if(comparer.Compare(node1.Value, node2.Value) > 0) {
var next = node2.Next;
list.Remove(node2);
list.AddBefore(node1, node2);
if(node1 == begin) {
begin = node2;
}
node2 = next;
++i2;
} else {
node1 = node1.Next;
++i1;
}
}
// 次の部分リストの先頭を取得
while(i2 < end2) {
node2 = node2.Next;
++i2;
}
node1 = node2;
}
}
}
#endregion
#endregion
}パフォーマンス比較
Unity使いなので、Unityの環境での検証になります。ご容赦ください。
テスト環境はUnity 5.6.3p1です。
int型のリストのソートについて、パフォーマンス測定します。
- 要素数100000のソートを20回繰り返した中で、最良の実行時間を選択（イレギュラーな値を排除したかったので中央値でも良かった）。
- 手法名で括弧書きのものは、括弧内に挿入ソートに切り替える要素数を示している。
- 「メモリ確保」は理論上、想定されるアロケートによるメモリ使用量をオーダーで示したもの。
- 「速度比較」は、最速だったList.Sort()を基準に、各手法が何倍時間がかかったかを示したもの。
| コンテナ | 手法 | 安定性 | メモリ確保量 | 速度比較 | 実行時間 |
|---|---|---|---|---|---|
| List | Sort | 不安定 | O(1) | 1.00 | 0.0664 |
| LinkedList | arraySort | 不安定 | O(N) | 1.22 | 0.0808 |
| List | OrderBy | 安定 | O(N) | 1.23 | 0.0817 |
| List | mergeSort(4) | 安定 | O(N) | 1.32 | 0.0877 |
| List | mergeSort(8) | 安定 | O(N) | 1.33 | 0.0881 |
| List | mergeSort(2) | 安定 | O(N) | 1.35 | 0.0900 |
| List | mergeSort(1) | 安定 | O(N) | 1.39 | 0.0923 |
| List | mergeSort(16) | 安定 | O(N) | 1.40 | 0.0932 |
| List | mergeSort(32) | 安定 | O(N) | 1.62 | 0.1075 |
| List | stableSort | 安定 | O(N) | 1.67 | 0.1109 |
| LinkedList | stableSort | 安定 | O(N) | 1.77 | 0.1179 |
| LinkedList | mergeSort(8) | 安定 | O(1) | 2.55 | 0.1697 |
| LinkedList | mergeSort(16) | 安定 | O(1) | 2.58 | 0.1713 |
| LinkedList | mergeSort(1) | 安定 | O(1) | 2.60 | 0.1725 |
| LinkedList | mergeSort(4) | 安定 | O(1) | 2.61 | 0.1735 |
| LinkedList | mergeSort(2) | 安定 | O(1) | 2.65 | 0.1758 |
| LinkedList | mergeSort(32) | 安定 | O(1) | 2.74 | 0.1820 |
（2017/09/10追記）ListのOrderByの計測結果も加えました。Listに対してOrderBy(e => e).ToList()を実行したパフォーマンスです。OrderBy()だけだと遅延評価によりソートが実行されないので、GetEnumerator()の呼び出しをしないと計測になりません。また、Listのソート結果をListで受け取りたかった都合もあり、ToList()までの性能を計測しています。
ListとLinkedListそれぞれにstableSortというのもありますが、これは各要素にインデックスを振ったものを、Listに詰めてからSort()したあとに、元のコンテナに詰め直すという処理です。インデックスによって標準ソートを安定ソートとして利用できるようにしたものです。stableSortの実装は別の記事にまとめました。OrderBy()より速くなることを期待したのですが、全然ダメでしたね。
前回の検討により、UnityのListはcomparerにnullを与えるのが場合によっては最速、という話がありましたが、性能比較がややこしくなるので避けました。なので、上位2位を抑えているSortとarraySortについては、intやdoubleに対してさらに速度を上げることはできます。
余談。クイックソートにも安定ソートの実装が存在しています。swapの代わりに順序保証した挿入を行えばよいので、LinkedListに都合がいいかと思って実装してみましたが、上記の表で一番下にまとまる程度の速度しか出なかったので割愛します。
まとめ
（2017/09/10）Listについて、OrderByを考慮する内容に修正。
Listに関しては内部ソートは諦めましたが、安定ソートとしてはマージソートがかなり速くて良いですね。ただ、OrderBy()がなんだかんだ速くて、速度だけを求めるならこれで良さそうです。マージソートは速度的にOrderBy()とほぼ遜色なく、OrderBy()ほどメモリを使用しないことに価値があります（オーダーは同じでも定数倍違います）。あとは部分ソートができます。
個人的にはUnityではListの安定ソートには、マージソートを使っていきたいです（詳しくは割愛しますが、拡張されたMonoヒープは縮小されずGC時間が長くなってスパイクが発生するので、あまりでかいヒープは使いたくないというゲームプログラムの事情によります）。
一方、LinkeListですが、LinkedList上でのソート実装はどうしてもList.Sort()の2.5倍程度の時間がかかってしまいました。結局、処理速度が重要なときはListにソートさせた方が速いので、arraySortかstableSortを選択することになりそうです。内部ソートであることに価値があるなら今回実装したマージソートは使えます。
少ない要素数のとき挿入ソートに差し替える最適化については、Listのマージソートは多少効いてますが、LinkedListのマージソートに対してはそれほど差が出ていないような気もします。LinkedListNodeの挿入コストが高すぎるのでしょうか。internalでなければなぁ・・・。
Listにしても、LinkedListにしても、stableSortのオーバーヘッドはそこそこあるので、最初からリスト要素にインデックスを持たせる設計にして、そのまま安定ソートを保証できるようにしてList.Sort()やLinkeList.arraySort()を使うのが無難そうではあります。