Скорость linq orderby () против list.sort ()

Вот список случайных целых чисел:

var r = new Random();
var e = Enumerable.Repeat(1, 10_000_000).Select( _ => r.Next());

Как вы думаете, какая версия быстрее:

var result = e.OrderBy(x => x).Last(); //materialize the IEnumerable

или

var l = e.ToList();
l.Sort();
var result = l.Last();

Я надеялся, что .OrderBy(x => x).Last() в первом примере будет оптимизирован для сортировки только небольшого подмножества списка или просто для обхода списка за O (n).

Спойлер: Это не.

Но тогда производительность двух версий должна быть как минимум сопоставимой, не так ли? Я имею в виду:

В первом OrderBy() выделяет временный массив и сортирует его на месте. Во втором я явно выделяю список и Sort() его на месте.

Фактические результаты показывают, что пример OrderBy() в 4-5 раз медленнее! (5-6 сек против 1,2-1,3 сек)

Кто-нибудь может объяснить, почему?

В случае .OrderBy(x => x) используется лямбда идентификации x => x для каждого элемента. Разница между:

var result2 = e.Last();

и

var result2 = e.Select(x=>x).Last();

измеримо, но мало: во втором случае на 30-50 мс больше. Так что это не объясняет огромного разрыва.

Вот почему я хотел бы, чтобы были версии Min() и Max(), которые возвращали объект вместо значения. Это позволило бы избежать необходимости сортировать весь набор элементов, чтобы получить объект с наибольшим или наименьшим значением.

itsme86 10.08.2018 16:32

@ itsme86 Что ты имеешь в виду? Всегда можно сделать IEnumerable<MyThing> thingsList = ...; MyThing pubBum = thingsList.Max( thing => thing.BeersBeforeCollapsing )

Cristian Diaconescu 10.08.2018 16:36

Это возвращает int при условии, что BeersBeforeCollapsing - это int. Думаю, это также может быть поплавок.

itsme86 10.08.2018 16:37

Нет, возвращает MyThing

Cristian Diaconescu 10.08.2018 16:38

Не на моем компьютере ... MyObj[] foo = { new MyObj { Blee = 7 } }; var bar = foo.Max(o => o.Blee);bar - это 7, а не объект MyObj. Если бы вы могли это сделать, вам бы не пришлось делать свой .OrderBy().Last(), вы могли бы просто .Max().

itsme86 10.08.2018 16:42

Ого, ты прав! Извините, я бы поставил на это (и потерял деньги!)

Cristian Diaconescu 10.08.2018 16:44

Причина, по которой я использовал .Last(), заключалась в том, чтобы принудительно запустить цепочку Linq. Сначала я хотел добавить .ToList() в конце, но это было бы другое распределение.

Cristian Diaconescu 10.08.2018 16:47

Имеет смысл. Не хотел сорвать ваш вопрос.

itsme86 10.08.2018 16:48

LINQ to Object не выполняет каких-либо умных оптимизаций слияния. OrderBy().Last() - это OrderBy(), за которым следует Last(), а не то, что быстрее, чем отдельные операции. Вы в основном спрашиваете, почему операция сортировки на месте List.Sort (которая использует интросорт) быстрее, чем Enumerable.OrderBy (которая использует быструю сортировку, затрудненная требованием сравнения, проходящего через лямбда-выражение ключевого селектора). Если вы хотите разобраться в этом, benchmark.net, вероятно, вам подскажет.

Jeroen Mostert 10.08.2018 16:54

Связанный: C# Сортировка и упорядочение по сравнению. А вот с объектами результат кажется другим?

41686d6564 10.08.2018 17:09

@ itsme86 Вот почему у меня написаны расширения Aggregate и MaxBy на основе MinBy.

NetMage 10.08.2018 20:21

Я бы использовал First вместо Last, что позволяет избежать ненужного обхода результата, поскольку в этом случае вы просто пытаетесь принудительно выполнить OrderBy.

NetMage 10.08.2018 20:24

Список в массив можно быстро преобразовать. Тогда вы можете просто использовать метод Max (). См. Этот пример: dotnetperls.com/max.

Dan Randolph 10.08.2018 21:36
4
13
3 544
1

Ответы 1

Похоже, что у List есть специальная оптимизированная версия сортировки C++, который он использует, когда сравнивает типы с Comparer.Default, или не IComparer для типа. OrderBy всегда выполняет общую сортировку, подходящую для любого типа, и IComparer.

Если вы замените результат Select объектами типа MyInt следующим образом:

public class MyInt : IComparable {
    public int value;
    public MyInt(int newv) => value = newv;

    public int CompareTo(object obj) {
        if (obj is MyInt m2) {
            return value.CompareTo(m2.value);
        }
        else if (obj is int i2) {
            return value.CompareTo(i2);
        }
        else {
            throw new Exception($"can't compare MyInt to {obj.GetType()}");
        }
    }
}

var e = Enumerable.Repeat(1, 10_000_000).Select(_ => new MyInt(r.Next()));

Тогда OrderBy будет в 2 раза быстрее, чем метод List.Sort.

Обратите внимание: если вы используете Comparer<>.Create для создания Comparer для MyInt, List.Sort примерно соответствует OrderBy:

l.Sort(Comparer<MyInt>.Create((m1,m2) => m1.value.CompareTo(m2.value)));

Другие вопросы по теме