16

結果

1000万のランダムintのリストを使用する（毎回同じシード、平均10回の繰り返し）：

listCopy.Sort(Comparer<int>.Default)314msかかります。

使用する

sealed class IntComparer : IComparer<int>
{
  public int Compare(int x, int y)
  {
    return x < y ? -1 : (x == y ? 0 : 1);
  }
}

listCopy.Sort(new IntComparer())716msかかります。

いくつかのバリエーション：

  • struct IntComparer代わりに使用sealed class：771ms
  • 使用public int Compare(int x, int y) { return x.CompareTo(y); }：809ms

コメントコメント

Comparer<int>.Defaultを返しますGenericComparer<int>。dotPeekによると、次のようになります。

internal class GenericComparer<T> : Comparer<T> where T : IComparable<T>
{
  public override int Compare(T x, T y)
  {
    if ((object) x != null)
    {
      if ((object) y != null)
        return x.CompareTo(y);
      else
        return 1;
    }
    else
      return (object) y != null ? -1 : 0;
  }

...
}

IntComparer明らかに、これはを使用する私のバリアントよりも速くないはずCompareToです。

ArraySortHelper<T>のコアであると思われるに関連するものは見つかりませんでしList<T>.Sortた。

JITがここでいくつかの魔法の特別なケーシングを行っていると推測することしかできません（呼び出しをComparer<int>.Default行わない特別な並べ替えの実装などで使用する並べ替えを置き換えます）？IComparer<T>.Compare

編集：上記のタイミングは5.9214729782462845（StopwatchそしてTimeSpan「ダニ」の異なる定義を持っている）の係数で低すぎます。ただし、ポイントには影響しません。

4

3 に答える 3

24

その理由は、参照ソースの system/array.cs ソース コード ファイルですぐにわかります。

   [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
   public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) {
       // Argument checking code omitted
       //...

       if (length > 1) {
           // <STRIP>
           // TrySZSort is still faster than the generic implementation.
           // The reason is Int32.CompareTo is still expensive than just using "<" or ">".
           // </STRIP>
           if ( comparer == null || comparer == Comparer<T>.Default ) {
               if(TrySZSort(array, null, index, index + length - 1)) {
                   return;
               }
           }

           ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
       }
   }

でマークされたコメントは、<STRIP>英語が壊れているにもかかわらず、それを説明しています :) デフォルトの比較子のコード パスは、CLR で実装され、C++ で記述された関数である TrySZSort() を経由します。ソース コードは SSCLI20 から取得できます。clr /src/vm/comarrayhelpers.cpp に実装されています。という名前のテンプレート クラス メソッドを使用しArrayHelpers<T>::QuickSort()ます。

<Int32.CompareTo() で必要な 10 の代わりに、単一の cpu 命令である演算子を使用できるため、速度の利点が得られます。つまり、IComparable<>.CompareTo は、単純な並べ替えに対して過剰に指定されています。

これはマイクロ最適化であり、.NET Framework には非常に多くの機能があります。依存関係チェーンの最下部に位置するコードの運命は避けられないため、Microsoft は、自社のコードが顧客のアプリでスピード クリティカルにならないとは決して想定できません。

于 2012-07-11T20:24:39.367 に答える
4

ILSpy は次のように逆コンパイルします。

    public override int Compare(T x, T y)
    {
        if (x != null)
        {
            if (y != null)
            {
                return x.CompareTo(y);
            }
            return 1;
        }
        else
        {
            if (y != null)
            {
                return -1;
            }
            return 0;
        }
    }

null チェックは常にtrue値の型として評価されるため、最適化されて取り除かれます。最終結果は

public override int Compare(T x, T y)
{
    return x.CompareTo(y);
}
于 2012-07-11T19:57:13.780 に答える
1

Int32 の既定の比較子は CompareTo(int,int) メソッドです。デフォルトの比較子の仮定は正しくありません。

IComparable インターフェイスは、ジェネリック コレクション オブジェクトのメンバーを順序付けするための厳密に型指定された比較メソッドを提供します。このため、通常、開発者コードから直接呼び出されることはありません。代わりに、List.Sort() や Add などのメソッドによって自動的に呼び出されます。

http://msdn.microsoft.com/en-us/library/4d7sx9hd.aspx . 上記の IComparable インターフェイスは、CompareTo メソッドを定義します。

したがって、比較者はほぼ同じ速度であると想定する必要があります。では、なぜ遅くなるのでしょう？.Net の Sort メソッドを掘り下げると、最終的に次の行にたどり着きます。

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

比較子がその型のデフォルトの比較子と等しい場合、配列ソートは内部で最適化されたソート方法を使用しようとします。あなたの比較子はデフォルトの比較子ではないため、最適化された並べ替えをスキップします。

于 2012-07-11T20:19:21.280 に答える