为什么是List <>。OrderBy LINQ比IComparable + List <>更快。

我感兴趣的是，使用LINQ对我的类进行排序，还是通过实现IComparable接口和List.Sort，会更快。当LINQ代码更快时，我感到非常惊讶。为什么是List <>。OrderBy LINQ比IComparable + List <>更快。

为了做这个测试，我做了一个非常简单的类，使用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<Int>List.Sort是LINQ的1/4的速度，它保持在2000左右。

那么LINQ为什么只有ab我的班级正常排序的速度是66％吗？我是否在执行IComparable时出错？

更新： 我只是想尝试在释放模式做，是的，结果是不同的：

IComparable<T>: 
1593.0911 

Linq: 
1958.1119

但我还是很有兴趣知道为什么了IComparable处于调试模式慢。

来源

2010-07-26 Vincent McNabb

你有没有尝试在调试模式（项目属性）设置优化，看看它是否仍然较慢？如果没有，那可能会解释它。 – Gishu 2010-07-26 10:58:51

开启优化代码...我正在寻找一个真正的原因，而不是一个促成因素。我并没有试图解决这个问题，两种方法对我而言都足够快，我只想知道为什么。 – 2010-07-26 11:09:42

如果你把每件事情都JIT编译的启动措施之前，你可能会得到不同的结果（我也推荐使用Stopwatch类测量时间）：

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

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

来源

2010-07-26 12:50:42

在测量之前，您如何确保事物已被打乱？ – 2010-07-26 22:08:26

另外。在我的电脑上进行高达约900次的测试，IComparable速度更快。但是，如果我循环超过1000，那么LINQ变得更快。所以在最初的LINQ设置上有一些开销，但重复使用最终会变得更快。 – 2010-07-26 23:29:53

在代码片段中，当您调用'll.OrderBy（）'时，列表已经在前一行进行了排序，所以调用OrderBy（）时可能发生的计算量较少。你能否在你的秒表测试中验证你是否在已经排序的列表上调用了'OrderBy（）'？ – devlord 2017-02-08 20:29:24

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

来源

2010-07-26 13:06:58 sgmoore

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

来源

2011-12-06 12:59:26 Stajek

Linq到对象OrderBy使用稳定的快排，而Array.Sort使用不稳定的快排。算法的速度成本应该没有太大的差别。它们都是O（n log n）。 – 2011-12-08 00:40:31

您是否知道它是否经过优化或者仍然存在相同的n^2最坏情况？ – Stajek 2012-03-30 16:25:37

对我来说，我将使用Linq与IComparable（当这是最简单或唯一的排序方式）。在这种情况下，项目是TestSort: IComparable<TestSort>

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

ll可以是任何的IEnumerable：列表，阵列等

此外，在CompareTo你可以有多个方法来比较...例如，你可以做这样的事情：

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

来源

2012-05-11 14:01:26 Jaider

为什么是List <>。OrderBy LINQ比IComparable + List <>更快。

回答

相关问题