为什么在Debug模式下，List<>.OrderBy LINQ比IComparable+List<>.Sort更快？

Question

我想知道使用LINQ还是实现IComparable接口和List.Sort来对我的类进行排序是否更快。当我尝试使用LINQ时，我很惊讶它比后者更快。

为了进行测试，我创建了一个非常简单的类TestSort，并实现了IComparable接口。

class TestSort: IComparable<TestSort>  {
    private int age;
    private string givenName;

    public int Age {
        get {
            return age;
        }
        set {
            age = value;
        }
    }

    public string GivenName {
        get {
            return givenName;
        }
        set {
            givenName = value;
        }
    }

    public TestSort(int age, string name) {
        this.age = age;
        this.givenName = name;
    }

    public int CompareTo(TestSort other) {
        return this.age.CompareTo(other.age);
    }
}

接下来是一个简单的程序，对它进行多次排序——排序操作比复制列表操作代价更高，所以可以忽略其影响。

class Program {
    static void Main(string[] args) {
        // Create the test data
        string name = "Mr. Bob";

        Random r = new Random();
        var ts2 = new List<TestSort>();

        for (int i = 0; i < 100; i++) {
            ts2.Add(new TestSort(r.Next(), name));
        }

        DateTime start, end;

        // Test List<>.Sort
        start = DateTime.Now;
        for (int i = 0; i < 100000; i++) {
            var l = ts2.ToList();
            l.Sort();
        }
        end = DateTime.Now;

        Console.WriteLine("IComparable<T>: ");
        Console.WriteLine((end - start).TotalMilliseconds);


        // Test Linq OrderBy
        start = DateTime.Now;
        for (int i = 0; i < 100000; i++) {
            var l = ts2.ToList();
            l = l.OrderBy(item => item.Age).ToList();
        }
        end = DateTime.Now;

        Console.WriteLine("\nLINQ: ");
        Console.WriteLine((end - start).TotalMilliseconds);

        Console.WriteLine("Finished.");
        Console.ReadKey();
    }
}

我很惊讶地收到了以下输出:

IComparable<T>:
2965.1696

LINQ:
2181.1248

有时LINQ的速度会降到2000以下，而有时IComparable的速度会达到3000左右。

当我使用普通的List进行测试时，List.Sort的速度是LINQ的1/4，而LINQ的速度保持在约2000左右。

那么为什么对于我的类而言，LINQ只有普通排序速度的66%？我在实现IComparable时有错误吗？

更新： 我刚才尝试在发布模式下运行，结果确实不同：

IComparable<T>:
1593.0911

Linq:
1958.1119

但我仍然非常想知道为什么在调试模式下，IComparable会更慢。

- Vincent McNabb

---

你试过在调试模式下（项目属性）开启优化，看看是否仍然较慢吗？如果没有，那可能就是原因。 - Gishu

代码优化已开启...我正在寻找实际原因而非贡献因素。我并不是在尝试解决问题，两种方法对我的目的来说都足够快，我只是想知道为什么。 - Vincent McNabb

Answer 1

如果你在开始测量之前确保所有东西都被JIT编译，你可能会得到不同的结果。我也强烈推荐使用BenchmarkDotNet进行微基准测试。

var ll = ts2.ToList();
ll.Sort();
ll.OrderBy(item => item.Age).ToList();

根据我的测量（在添加了上述代码之后），IComparable 总是更快的（即使在调试模式下）。

- Eli Arbel

---

你如何确保在测量之前 JIT 编译了代码？ - Vincent McNabb

此外，在我的电脑上进行大约900次测试时，IComparable更快。但是，如果我循环超过1000次，则LINQ变得更快。因此，在最初的LINQ设置中存在一些开销，但重复使用最终会更快。 - Vincent McNabb

在代码片段中，当您调用ll.OrderBy()时，列表已经在前一行上进行了排序，因此在调用OrderBy()时可能需要进行较少的计算。您能否验证在秒表测试中，您没有对已经排序的列表调用OrderBy()？ - devlord

@lorddev 这段代码只是用来JIT方法的，因此实际测量将更准确。然而，现在最好直接使用BenchmarkDotNet。 - Eli Arbel

Answer 2

对我来说，如果这是最常用或唯一的排序方式，我会使用带有IComparable的Linq。在这种情况下，item是TestSort：IComparable<TestSort>

var sorted = ll.OrderBy(item => item); // This automatically used age to compare, as it's defined in CompareTo

ll 可以是任何 IEnumerable：List、Array 等等。

在 CompareTo 中，您可以有多种比较方式...例如，您可以这样做：

  public int CompareTo(TestSort other) {
        return this.age != other.age ? this.age.CompareTo(other.age) : this.dateOfBirth.CompareTo(other.dateOfBirth);
    }

- Jaider

Answer 3

Sort使用未优化的快速排序，在最坏情况下具有n*n的复杂度。我不知道orderby使用什么方法，但我知道它不使用相同的方法，因为它是一种稳定的排序，不像array.sort。

- Stajek

---

Linq对对象的OrderBy使用稳定的快速排序，而不是Array.Sort使用不稳定的快速排序。两种算法的速度成本差别不大。 它们都是O（nlog n）。 - Vincent McNabb

你知道它是否已经优化，还是仍然存在相同的n^2最坏情况吗？ - Stajek

Answer 4

这可能是调用方法CompareTo的开销，在编译并在发布模式下运行时将被替换为内联。

- sgmoore