为什么OrderBy返回IOrderedEnumerable <T>比Sort快得多？

Question

这是对C#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"));

争论的方法是:

persons.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
//and
persons.OrderBy(n => n.Name);

首先让我说,我理解没有任何重大的性能差异需要担心.但我很想知道为什么OrderBy表现得比这更好Sort.我正在使用@phoog在原始问题中发布的答案.

private void button1_Click(object sender, EventArgs e)
{
    IEnumerable<Person> people;

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

    BenchMark(persons => people = persons.OrderBy(n => n.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 static void BenchMark(Action<List<Person>> action)
{
    List<Person> persons = new List<Person>();
    for (int i = 0; i < 10000; i++)
    {
        persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
    }
    List<Person> unsortedPersons = new List<Person>(persons);

    Stopwatch watch = new Stopwatch();
    for (int i = 0; i < 100; i++)
    {
        watch.Start();

        action(persons);

        watch.Stop();
        persons.Clear();
        persons.AddRange(unsortedPersons);
    }

    MessageBox.Show(watch.Elapsed.TotalMilliseconds.ToString());
}

结果:

Sort() => 3500 ~ 5000 ms
OrderBy() => 0.2 ~ 1.5 ms

尽管我最初测试的列表较小,但差异很大,但一旦收集的大小上升,它就会变得越来越明显.可能是我遗漏了理解.NET集合的关键,但我的想法是因为Sort对现有的行为List<T>,它应该在处理时具有较小的开销(如果每一个)与OrderBy相同的行为相比List<T>(在我们的例子中persons)但是必须返回另一个集合IOrderedEnumerable<T>.但仍然OrderBy表现得更好.List<T>与IEnumerable<T>类型相比可能有一定的开销,但Sort无论如何都会对现有列表起作用!此外,我很难看到一种Linq比现有.NET方法更快的方法.

在原来的问题所有问题的答案比较,Sort对OrderBy.ToList我相信会有一定的开销,因此执行或多或少同样.

实施差异可能是什么？

---

编辑:好的,我学到了新东西.以下是我对延期执行的确认.

private void button1_Click(object sender, EventArgs e)
{
    BenchMark(persons =>
    {
        persons.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
        foreach (var item in persons)
        {
            break;
        }
    });

    BenchMark(persons =>
    {
        IEnumerable<Person> people = persons.OrderBy(n => n.Name);
        foreach (var item in people)
        {
            break;
        }
    });
}

Sort在OrderBy距离5000毫米以上的地方跑了4000到5000 毫秒.所以我的结论确实是错的.一旦我开始枚举集合,它们都以平等的条件执行.我更喜欢任何一天的语法OrderBy:)

编辑2:我刚刚发现,这是确切的重复这一个.但是这里有一个关于延迟执行的更有趣的问题,尽管不是关于完全排序.

Answer 1

在这种情况下,OrderBy速度要快得多,因为您实际上并没有执行它.

在您枚举结果之前,查询是延迟的,因此它实际上从不进行排序.在您实际枚举结果之前,IOrderedEnumerable<T>不会处理输入并执行任何形式的排序.

尝试将基准更改为:

 BenchMark(persons => people = persons.OrderBy(n => n.Name).Count());

该Count()调用将强制实际发生排序(因为它需要枚举IOrderedEnumerable<T>以生成计数),这应该显着地平衡您的计时.

大多数LINQ扩展方法都以这种方式工作 - 直到你枚举它们(通过Count(),调用ToList()或只是在正常foreach循环中使用它们等),它们的影响可以忽略不计,因为除了构建可枚举之外,它们实际上并没有做任何其他事情.其他基准比较的原因OrderBy(...).ToList()是增加了ToList()力量OrderBy以完全执行并实际排序结果.

Answer 2

OrderBy()和大多数LINQ方法一样,使用延迟执行.

在您枚举其结果之前,它实际上并没有做任何事情.

要正确衡量其性能,您可以致电.OrderBy(...).Count().