C # Sort 和 OrderBy 比较

我可以使用 Sort 或 OrderBy 对列表进行排序。哪一个更快? 两个工作在同一个上面 算法？

List<Person> persons = new List<Person>();
persons.Add(new Person("P005", "Janson"));
persons.Add(new Person("P002", "Aravind"));
persons.Add(new Person("P007", "Kazhal"));

1.

persons.Sort((p1,p2)=>string.Compare(p1.Name,p2.Name,true));

2.

var query = persons.OrderBy(n => n.Name, new NameComparer());


class NameComparer : IComparer<string>
{
public int Compare(string x,string y)
{
return  string.Compare(x, y, true);
}
}
132524 次浏览
小开

不，它们不是同一个算法。对于初学者，LINQOrderBy被记录为 稳定(也就是说，如果两个项目具有相同的 Name，它们将按照原来的顺序出现)。

它还取决于是缓冲查询还是迭代查询(LINQ-to-Objects，除非缓冲结果，否则每个 foreach都会重新排序)。

对于 OrderBy查询，我还想使用:

OrderBy(n => n.Name, StringComparer.{yourchoice}IgnoreCase);

(对于 CurrentCulture、 Ordinal或 InvariantCulture中的 {yourchoice})。

List<T>.Sort

此方法使用 Array.Sort，它 使用快速排序算法 执行情况不稳定 排序; 也就是说，如果两个元素是 它们的顺序可能不相等 相反，是一种稳定的类型 保持元素的顺序 都是平等的。

Enumerable.OrderBy

此方法执行稳定的排序; 也就是说，如果两个元素的键相等，则保留元素的顺序。相反，不稳定的排序不能保持具有相同键的元素的顺序。 排序; 也就是说，如果两个元素是 它们的顺序可能不相等 相反，是一种稳定的类型 保持元素的顺序 都是平等的。

小开
最佳答案

为什么不衡量一下:

class Program
{
class NameComparer : IComparer<string>
{
public int Compare(string x, string y)
{
return string.Compare(x, y, true);
}
}


class Person
{
public Person(string id, string name)
{
Id = id;
Name = name;
}
public string Id { get; set; }
public string Name { get; set; }
}


static void Main()
{
List<Person> persons = new List<Person>();
persons.Add(new Person("P005", "Janson"));
persons.Add(new Person("P002", "Aravind"));
persons.Add(new Person("P007", "Kazhal"));


Sort(persons);
OrderBy(persons);


const int COUNT = 1000000;
Stopwatch watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
Sort(persons);
}
watch.Stop();
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);


watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
OrderBy(persons);
}
watch.Stop();
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);
}


static void Sort(List<Person> list)
{
list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
}


static void OrderBy(List<Person> list)
{
var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
}
}

在我的计算机上，当以发布模式编译时，这个程序会打印:

Sort: 1162ms
OrderBy: 1269ms

更新:

正如@Stefan 所建议的，对一个大列表进行排序的次数减少了:

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
persons.Add(new Person("P" + i.ToString(), "Janson" + i.ToString()));
}


Sort(persons);
OrderBy(persons);


const int COUNT = 30;
Stopwatch watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
Sort(persons);
}
watch.Stop();
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);


watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
OrderBy(persons);
}
watch.Stop();
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

印刷品:

Sort: 8965ms
OrderBy: 8460ms

在这个场景中，OrderBy 的性能似乎更好。

更新2:

用随机的名字:

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
}

地点:

private static Random randomSeed = new Random();
public static string RandomString(int size, bool lowerCase)
{
var sb = new StringBuilder(size);
int start = (lowerCase) ? 97 : 65;
for (int i = 0; i < size; i++)
{
sb.Append((char)(26 * randomSeed.NextDouble() + start));
}
return sb.ToString();
}

收益率:

Sort: 8968ms
OrderBy: 8728ms

还是 OrderBy 更快

小开

我认为有必要指出 Sort和 OrderBy的另一个区别:

假设存在一个 Person.CalculateSalary()方法，它需要很多时间; 甚至可能比对一个大列表排序的操作还要多。

比较一下

// Option 1
persons.Sort((p1, p2) => Compare(p1.CalculateSalary(), p2.CalculateSalary()));
// Option 2
var query = persons.OrderBy(p => p.CalculateSalary());

选项2 可能具有更好的性能，因为它只调用 CalculateSalary方法 N次，而 Sort选项可能调用 CalculateSalary到 < a href = “ http://www.wolframalpha.com/input/? i = 2nlog% 28n% 29”rel = “ noReferrer”> 2N log (N) 次，这取决于排序算法的成功。

小开

DarinDimitrov 的答案表明，当面对已经排序的输入时，OrderBy略快于 List.Sort。我修改了他的代码，使它能够重复对未排序的数据进行排序，而且 OrderBy在大多数情况下稍微慢一些。

此外，OrderBy测试使用 ToArray强制枚举 Linq 枚举器，但这显然返回一个类型(Person[]) ，该类型不同于输入类型(List<Person>)。因此，我用 ToList而不是 ToArray重新运行了测试，得到了一个更大的差异:

Sort: 25175ms
OrderBy: 30259ms
OrderByWithToList: 31458ms

密码:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;


class Program
{
class NameComparer : IComparer<string>
{
public int Compare(string x, string y)
{
return string.Compare(x, y, true);
}
}


class Person
{
public Person(string id, string name)
{
Id = id;
Name = name;
}
public string Id { get; set; }
public string Name { get; set; }
public override string ToString()
{
return Id + ": " + Name;
}
}


private static Random randomSeed = new Random();
public static string RandomString(int size, bool lowerCase)
{
var sb = new StringBuilder(size);
int start = (lowerCase) ? 97 : 65;
for (int i = 0; i < size; i++)
{
sb.Append((char)(26 * randomSeed.NextDouble() + start));
}
return sb.ToString();
}


private class PersonList : List<Person>
{
public PersonList(IEnumerable<Person> persons)
: base(persons)
{
}


public PersonList()
{
}


public override string ToString()
{
var names = Math.Min(Count, 5);
var builder = new StringBuilder();
for (var i = 0; i < names; i++)
builder.Append(this[i]).Append(", ");
return builder.ToString();
}
}


static void Main()
{
var persons = new PersonList();
for (int i = 0; i < 100000; i++)
{
persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
}


var unsortedPersons = new PersonList(persons);


const int COUNT = 30;
Stopwatch watch = new Stopwatch();
for (int i = 0; i < COUNT; i++)
{
watch.Start();
Sort(persons);
watch.Stop();
persons.Clear();
persons.AddRange(unsortedPersons);
}
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);


watch = new Stopwatch();
for (int i = 0; i < COUNT; i++)
{
watch.Start();
OrderBy(persons);
watch.Stop();
persons.Clear();
persons.AddRange(unsortedPersons);
}
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);


watch = new Stopwatch();
for (int i = 0; i < COUNT; i++)
{
watch.Start();
OrderByWithToList(persons);
watch.Stop();
persons.Clear();
persons.AddRange(unsortedPersons);
}
Console.WriteLine("OrderByWithToList: {0}ms", watch.ElapsedMilliseconds);
}


static void Sort(List<Person> list)
{
list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
}


static void OrderBy(List<Person> list)
{
var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
}


static void OrderByWithToList(List<Person> list)
{
var result = list.OrderBy(n => n.Name, new NameComparer()).ToList();
}
}
小开

我只是想补充一下 orderby 更有用。

为什么，因为我能做到:

Dim thisAccountBalances = account.DictOfBalances.Values.ToList
thisAccountBalances.ForEach(Sub(x) x.computeBalanceOtherFactors())
thisAccountBalances=thisAccountBalances.OrderBy(Function(x) x.TotalBalance).tolist
listOfBalances.AddRange(thisAccountBalances)

为什么要使用复杂的比较器? 只是基于一个字段进行排序。这里我是基于总量平衡进行排序的。

很简单。

我不能那样做，我想知道为什么。

至于速度，永远是 O (n)。

小开

简而言之:

列表/数组排序() :

  • 情绪不稳定。
  • 就地解决。
  • 使用内向排序/快速排序。
  • 自定义比较是通过提供比较器来完成的。如果比较代价很高，那么它可能比 OrderBy ()慢(后者允许使用键，见下文)。

OrderBy/ThenBy () :

  • 很稳定。
  • 位置不对。
  • 使用快速排序。Quicksort 不是一个稳定的国家。这里有一个技巧: 在排序时，如果两个元素有相同的键，它会比较它们的初始顺序(在排序之前已经存储)。
  • 允许使用键(使用 lambdas)对元素的值进行排序(例如: x => x.Id)。在排序之前，首先提取所有键。这可能比使用 Sort ()和自定义比较器带来更好的性能。

资料来源: MDSN 、 参考资料来源和 Dotnet/coreclr存储库(GitHub)。

上面列出的一些语句基于当前的.NET 框架实现(4.7.2)。


提交答案