C#Sort和OrderBy比较

Question

我可以使用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);
    }
}

Answer 1

不,它们不是同一种算法.对于初学者来说,LINQ OrderBy被记录为稳定(即如果两个项目相同Name,它们将以原始顺序出现).

它还取决于您是否缓冲查询与多次迭代(LINQ-to-Objects,除非您缓冲结果,将重新排序foreach).

对于OrderBy查询,我也很想使用:

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

(对于{yourchoice}其中之一CurrentCulture,Ordinal或InvariantCulture).

List<T>.Sort

此方法使用Array.Sort,它使用QuickSort算法.此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

Enumerable.OrderBy

该方法执行稳定的排序; 也就是说,如果两个元素的键相等,则保留元素的顺序.相反,不稳定的排序不会保留具有相同键的元素的顺序.分类; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

Answer 2

为什么不测量它:

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表现更好.

UPDATE2:

并使用随机名称:

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更快

Answer 3

Darin Dimitrov的回答表明,这OrderBy比List.Sort面对已经排序的输入要快一些.我修改了他的代码,因此它重复排序未排序的数据,并且OrderBy在大多数情况下稍慢.

此外,OrderBy测试用于ToArray强制Linq枚举器的枚举,但这显然会返回一个Person[]与输入类型(List<Person>)不同的type().因此,我使用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();
    }
}

Answer 4

我认为重要的是要注意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最多调用2 n log(n)次,具体取决于排序算法的成功.

Answer 5

简而言之 :

List/Array Sort():

• 不稳定的排序.
• 就地完成.
• 使用Introsort/Quicksort.
• 通过提供比较器来完成自定义比较.如果比较昂贵,它可能比OrderBy()慢(允许使用键,见下文).

OrderBy/ThenBy():

• 稳定的排序.
• 不到位.
• 使用Quicksort.Quicksort不是一个稳定的类型.这是诀窍:当排序时,如果两个元素具有相同的键,则比较它们的初始顺序(在排序之前已经存储).
• 允许使用键(使用lambdas)对其值上的元素进行排序(例如:) x => x.Id.在排序之前首先提取所有键.这可能会比使用Sort()和自定义比较器产生更好的性能.

来源: MDSN,参考源和dotnet/coreclr存储库(GitHub).

上面列出的一些语句基于当前的.NET框架实现(4.7.2).它可能会在未来发生变化.