C排序和排序比较

为什么不测量它:

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

不,它们不是同一个算法。首先,Linq OrderBy 记录如下: 稳定的 (即如果两个项目相同 Name ,它们将按原始顺序显示)。

它还取决于是否对查询进行缓冲,而不是重复多次(除非对结果进行缓冲,否则linq-to-objects将根据 foreach )

对于 排序 查询,我也会尝试使用:

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

(用于 {yourchoice} 什么之中的一个 CurrentCulture , Ordinal 或 InvariantCulture )

List<T>.Sort

此方法使用array.sort,其中 使用快速排序算法。这个 实现执行不稳定 排序;也就是说,如果两个元素 相等,它们的顺序可能不是 保存。相反,一种稳定的 保留元素的顺序 一律平等。

Enumerable.OrderBy

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

达林·迪米特洛夫的回答表明 OrderBy 比 List.Sort 当面对已经排序的输入时。我修改了他的代码,使它对未排序的数据重复排序,并且 排序 在大多数情况下稍微慢一点。

而且, 排序 测试用途 ToArray 强制枚举Linq枚举器,但显然返回一个类型( Person[] )与输入类型不同( List<Person> )。因此,我用 ToList 而不是 托托 还有一个更大的区别:

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();
    }
}

我认为需要注意的是 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 时代,而 排序 选项可能调用 计算器 高达 2 n log( n ) 时间,取决于排序算法的成功。

简而言之:

列表/数组排序():

• 不稳定排序。
• 就地完成。
• 使用IntroSort/QuickSort。
• 自定义比较是通过提供比较器来完成的。如果比较昂贵,它可能比orderby()慢(后者允许使用键,请参见下文)。

orderby/thenby():

• 稳定排序。
• 不到位。
• 使用快速排序。快速排序不是一种稳定的排序。诀窍是:排序时,如果两个元素的键相等,则比较它们的初始顺序(排序前已存储)。
• 允许使用键(使用lambda)对元素的值(例如: x => x.Id )。排序前先提取所有键。这可能会导致比使用sort()和自定义比较器更好的性能。

资料来源: MDSN , reference source 和 dotnet/coreclr 存储库(Github)。

上面列出的一些语句基于当前的.NET框架实现(4.7.2)。将来可能会改变。

您应该计算orderby和sort方法使用的算法的复杂性。 我记得QuickSort的复杂性为n(log n),其中n是数组的长度。

我也在搜索orderby的,但我甚至在msdn库中也找不到任何信息。 如果您没有任何相同的值,并且只与一个属性相关的排序,我宁愿使用 sort()方法;如果不使用orderby。

我只想添加那个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)