16

结果

使用 1000 万个随机ints 的列表（每次相同的种子，平均 10 次重复）：

listCopy.Sort(Comparer<int>.Default)需要314 毫秒。

使用

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

listCopy.Sort(new IntComparer())需要716 毫秒。

一些变化：

  • 使用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

原因在Reference Source、 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>解释了它，尽管它的英文很烂:) 默认比较器的代码路径通过 TrySZSort()，这是一个在 CLR 中实现并用 C++ 编写的函数。您可以从SSCLI20获取它的源代码，它在 clr/src/vm/comarrayhelpers.cpp 中实现。它使用一个名为ArrayHelpers<T>::QuickSort().

它从能够使用<运算符中获得速度优势，单个 cpu 指令而不是 Int32.CompareTo() 所需的 10 条指令。或者换句话说， IComparable<>.CompareTo 被过度指定用于简单排序。

这是一个微优化，.NET Framework 有很多很多。位于依赖链最底部的代码不可避免的命运，微软永远不能假设他们的代码在客户的应用程序中不会对速度至关重要。

于 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 回答