はじめに

リストのソートの実装方法は一般的に３つがあると思っています。

格納するアイテムのクラスにIComparable を継承する
IComparerを継承した比較クラスを作成する
Comparisonデリゲートで比較メソッドを作成する

本稿はこれらの実装方法において、実行速度に違いがあるのか検証したものになります。

各実装方法のおさらい

簡単な例として、下記の ID のみを持つDataクラスをIDの昇順にソートする方法を考えてみます。

class Data {
  public int Id { get; set; }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
  }
}

IComparable

DataにIComparableを継承して、CompareTo(T obj)を実装します。比較対象も比較方法も一緒に管理出来るので楽ですが、比較方法が一つしか指定出来ない点（※）、Dataの実装を見ないとソート方法が不明瞭な点がデメリットですかね。

※ IDと名前を持つクラスがあったとして、時にはIDで、時には名前でソートといった使い分けが出来ない。

class Data : IComparable<Data> {
  public int Id { get; set; }
  // インターフェースを実装
  public int CompareTo(DataComparable obj) {
    return Id - obj.Id;
  }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 引数なしのSortを呼び出し
    list.Sort();
  }
}

IComparer

IComparerを継承したクラスを実装します。クラスが必要で手間ですが、比較方法が複数指定出来ますし、ソート使用者側でソート方法を選択出来るので便利です。

// 省略

class Comparer : IComparer<Data> {
  public int Compare(Data x, Data y) {
    return x.Id - y.Id;
  }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 引数にComparerを指定してSortを呼び出し
    list.Sort(new Comparator());
  }
}

Comparison

int Comparison<in T>(T x, T y)デリゲートにあったメソッドを実装します。イメージとしてはクラスが不要となったIComparerでしょうか。コード量が減りますし、変数チックに扱えるので個人的に一番好きです。

// 省略

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 比較メソッドを作成
    Comparison<Data> comparison = (x, y) => x.Id - y.Id;
    // 引数にComparisonデリゲートを指定してSortを呼び出し
    list.Sort(comparison);
  }
}

本題の実行速度の違いは？

結論から述べると検証結果としてはComparisonで実装したソートが20%程実行速度が早かったですが、環境による差なので本当はIComparerが早いんじゃね？です。

以降では結論に至った過程をだらだらと説明していきます。

検証方法

2000万レコードのDataをID降順に並べたListを、ID昇順にソートするのに掛かった時間を計測しました。用意したプログラムの全量は最後に載せておきます。

// タイマーを用意して
var sw = new Stopwatch();
// データを作成して
var list = new List<Data>();
for (var id = 20000000; id > 0; id--) {
  list.Add(new Data { Id = id });
}
// ソートする時間を計測
sw.Start();
list.Sort();
sw.Stop();

検証結果

下記の通り、ComparisonがIComparable、IComparerよりも20%ほど処理速度が早い結果となりました。いやいや、流石にこの差はおかしいだろという事で、List#Sortが内部で何をしているのか確認してみます。

	IComparable	IComparer	Comparison
1回目	10,917	11,616	8,700
2回目	11,749	11,701	8,687
3回目	11,039	11,523	8,707
4回目	10,768	11,917	8,707
5回目	10,946	11,602	8,762
合計	55,419	58,359	43,563
平均	11,083	11,671	8,712

（理解出来る場所まで）内部処理を確認する

まずIComparableとIComparerの処理は下記のとおりです。

IComparable、IComparer

1. List#Sort() を呼び出す

IComparableの場合はcomparerにnullを設定して呼び出します。

public void Sort() {
  Sort(0, Count, comparer);
}

2. List#Sort(int, int, IComparer) を呼び出す

エラーチェックをして、Array#Sortを呼び出します。Listも内部的にはArrayで要素を管理していますからね。

public void Sort(int index, int count, IComparer<T> comparer) {
  if (index < 0) {
    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  }

  if (count < 0) {
    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  }

  if (_size - index < count) { 
    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  }

  Array.Sort(_items, index, count, comparer);
  _version++;
}

3. Array#Sort(T[] array, int index, int length, IComparer comparer) を呼び出す

配列のエラーチェックをして、何やかんやでArraySortHelper#Sortを多分呼び出します。

public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer) {
  if (array == null) {
    throw new ArgumentNullException("array");
  }

  if (index < 0 || length < 0) {
    throw new ArgumentOutOfRangeException((length < 0) ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  }

  if (array.Length - index < length) {
    throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  }

  if (length > 1 && ((comparer != null && comparer != Comparer<T>.Default) || !TrySZSort(array, null, index, index + length - 1))) {
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
  }
}

4. ArraySortHelper#Sort(T[] keys, int index, int length, IComparer comparer) を呼び出す（多分）

要素の比較方法とソートに使うアルゴリズムを選択します。IComparableの場合はcomparerがnullなので、comparerの取得処理を行います。

public void Sort(T[] keys, int index, int length, IComparer<T> comparer) {
  try {
    if (comparer == null) {
      comparer = Comparer<T>.Default;
    }

    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) {
      IntrospectiveSort(keys, index, length, comparer);
    } else {
      DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32);
    }
  } catch (IndexOutOfRangeException) {
    IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
  } catch (Exception innerException) {
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException);
  }
}

5. Comparer.Default で Comparer を取得する（多分）

Runtimeほにゃらら系が何を行っているのかさっぱり理解出来ませんが、単語を拾うにIComparableをComparerに変換しているのだと思います。

private static readonly Comparer<T> defaultComparer = CreateComparer();

public static Comparer<T> Default {
  get {
    return defaultComparer;
  }
}

// ???
private static Comparer<T> CreateComparer() {
  RuntimeType runtimeType = (RuntimeType)typeof(T);
  if (typeof(IComparable<T>).IsAssignableFrom(runtimeType)) {
    return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), runtimeType);
  }

  if (runtimeType.IsGenericType && runtimeType.GetGenericTypeDefinition() == typeof(Nullable<>)) {
    RuntimeType runtimeType2 = (RuntimeType)runtimeType.GetGenericArguments()[0];
    if (typeof(IComparable<>).MakeGenericType(runtimeType2).IsAssignableFrom(runtimeType2)) {
      return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), runtimeType2);
    }
  }
  return new ObjectComparer<T>();
}

7. ArraySortHelper#IntrospectiveSort(T[], int, int, int, IComparer) を呼び出す（多分）

IntrospectiveSortとDepthLimitedQuickSortのどちらを呼び出すのか不明ですが、ひとまずIntrospectiveSortを使用しているとします。ついに配列の各要素を比較している部分が見えてきました。

internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer) {
  if (length >= 2) {
    IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
  }
}

private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer) {
  while (hi > lo) {
    int num = hi - lo + 1;
    if (num <= 16) {
      switch (num) {
        case 1:
          break;
        case 2:
          SwapIfGreater(keys, comparer, lo, hi);
          break;
        case 3:
          SwapIfGreater(keys, comparer, lo, hi - 1);
          SwapIfGreater(keys, comparer, lo, hi);
          SwapIfGreater(keys, comparer, hi - 1, hi);
          break;
        default:
          InsertionSort(keys, lo, hi, comparer);
          break;
      }

      break;
    }

    if (depthLimit == 0) {
      Heapsort(keys, lo, hi, comparer);
      break;
    }

    depthLimit--;
    int num2 = PickPivotAndPartition(keys, lo, hi, comparer);
    IntroSort(keys, num2 + 1, hi, depthLimit, comparer);
    hi = num2 - 1;
  }
}

8. ArraySortHelper#SwapIfGreater(T[], IComparer, int, int) を呼び出す

やっとここでComparerを使って比較を行います・・・長かった・・・。

private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b) {
  if (a != b && comparer.Compare(keys[a], keys[b]) > 0) {
    T val = keys[a];
    keys[a] = keys[b];
    keys[b] = val;
  }
}

Comparison

1. List#Sort(Comparison) を呼び出し

public void Sort(Comparison<T> comparison) {
  if (comparison == null) {
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  }

  if (_size > 0) {
    IComparer<T> comparer = new Array.FunctorComparer<T>(comparison);
    Array.Sort(_items, 0, _size, comparer);
  }
}

2. Array#FunctorComparer を作成

簡潔に述べればComparisonをComparerに変換しているだけです。デザインパターンで言うところのAdapterパターンですね。

internal sealed class FunctorComparer<T> : IComparer<T> {
  private Comparison<T> comparison;
  public FunctorComparer(Comparison<T> comparison) {
    this.comparison = comparison;
  }

  public int Compare(T x, T y) {
    return comparison(x, y);
  }
}

3. 以降の処理は`IComparable`の3以降の処理と同じ！

分かった事

長々と眺めて来ましたが、IComparerableもComparisonも結局はComparerに変換されて使われるという事が判りました。更にComparisonに関しては、Comparer#Compare()からComparisonデリゲートを呼び出しているので、呼び出しのオーバーヘッドで遅くなりそうなイメージです。

困ったときの stack overflow

理解の限界を超えたので、検索してみると案の定同じ疑問を投げかけている方がいました。stack overflow の下記投降です。

Is performance of List.Sort() by Comparison is better than custom IComparer?

こちらの回答によれば、「俺の環境ではIComparerの方がむしろ早かった。インターフェースのメソッドとデリゲートの呼び出しには速度差があり、インターフェースの方が高速なのだろう。」と結論付けていました。

まとめ

内部処理的にはどの実装方法でも速度差はない印象です。そしてここまで調べておいてなんですが、そんなところを気にするよりは、見やすく分かりやすい実装方法を選択するのがベストだと思います・・・。

付録

検証で使ったソースコード

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace ConsoleApp1 {

  internal class Program {

    [MethodImpl(MethodImplOptions.NoInlining)]
    static void Main(string[] args) {
      long total;
      int repeatCount = 20000000;
      var sw = new Stopwatch();

      total = 0;
      Console.WriteLine("<IComparable>");
      for (var i = 0; i < 5; i++) {
        var dataList = new List<DataComparable>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new DataComparable { Id = id });
        }
        sw.Start();
        dataList.Sort();
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

      total = 0;
      Console.WriteLine("<IComparer>");
      for (var i = 0; i < 5; i++) {
        var dataList = new List<Data>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new Data { Id = id });
        }
        sw.Start();
        dataList.Sort(new Compartor());
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

      total = 0;
      Console.WriteLine("<Comparison>");
      Comparison<Data> comparizon = (x, y) => x.Id - y.Id;
      for (var i = 0; i < 5; i++) {
        var dataList = new List<Data>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new Data { Id = id });
        }
        sw.Start();
        dataList.Sort((Comparison<Data>)((x, y) => x.Id - y.Id));
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

dataList.Add(new Data { Id = id });
      Console.ReadLine();
    }

  }

  internal sealed class Data {
    public int Id { get; set; }
  }

  internal sealed class DataComparable : IComparable<DataComparable> {
    public int Id { get; set; }

    public int CompareTo(DataComparable obj) {
      return Id - obj.Id;
    }
  }

  internal sealed class Compartor : IComparer<Data> {
    public int Compare(Data x, Data y) {
      return x.Id - y.Id;
    }
  }

}