Производительность встроенных сортировщиков коллекции .NET

Question

Был задан вопрос о том, как отсортировать список. Было несколько методов, данных из базового List.Sort () в List.OrderBy (). Самым смехотворным был «Выбор по вашему выбору». Я быстро проголосовал за это, но это заставило меня задуматься; не будет ли Linq's OrderBy (), примененный к списку, делать то же самое? myList.OrderBy (x => x.Property) .ToList () создаст итератор, который в основном находит минимальное значение проекции в том, что осталось от коллекции, и yield возвращает его. При просмотре всего списка это сортировка выбора.

Что заставило меня задуматься; какие алгоритмы используют встроенные сортировщики для списков, сортированных списков, перечислимых объектов и т. д., и, как следствие, следует ли избегать их использования для больших коллекций? SortedList, поскольку он остается отсортированным по ключу, вероятно, будет использовать однопроходную InsertionSort для каждого добавления; найдите первый индекс со значением больше нового и вставьте перед ним. Списки и массивы, вероятно, сами по себе MergeSort работают довольно эффективно, но я не знаю фактического алгоритма Sort (). Мы обсудили OrderBy.

То, что я знаю выше, может показаться, что List.Sort () или Array.Sort () являются лучшими вариантами для списка известного размера, и использование Linq для сортировки списка или массива в памяти не рекомендуется. Для потока действительно нет другого способа, кроме OrderBy () перечислимого; потеря производительности снижается благодаря тому, что вы можете хранить данные в виде потока, вместо того чтобы иметь их все перед сортировкой.

EDIT:

Общий консенсус заключается в том, что Sort () быстрее при конкретной реализации List или Array. OrderBy разумно, но медленнее, потому что добавляет O (N) сложность извлечения массива из переданного перечислимого. Инициализация SortedList заканчивается O (N ^ 2) из-за того, что находится под капотом. Мораль истории, используйте List.Sort () вместо List.OrderBy (), когда у вас есть фактический список.

Answer 1

Enumerable.OrderBy () переводит IEnumerable <> в массив и использует быструю сортировку. O (n) требования к хранению. Это делается внутренним классом в System.Core.dll, EnumerableSort<TElement>.QuickSort(). Стоимость хранения делает его неконкурентоспособным, просто сортируя список, если он у вас есть, поскольку List <> сортирует на месте. Linq часто оптимизирует, проверяя истинные возможности IEnumerable с помощью оператора is. Не будет работать здесь, так как List <>. Сортировка разрушительна.

List <>. Sort и Array.Sort используют быструю сортировку на месте.

SortedList <> имеет сложность O (n) для вставки, доминируя над сложностью O (log (n)) поиска точки вставки. Таким образом, размещение N несортированных элементов будет стоить O (n ^ 2). SortedDictionary <> использует красно-черное дерево, придавая сложности вставки O (log (n)). Таким образом, O (nlog (n)) заполнить его так же, как и амортизированная быстрая сортировка.

Answer 2

Один из способов узнать производительность каждого метода - измерить его:

List<int> createUnsortedList()
{
    List<int> list = new List<int>();
    for (int i = 0; i < 1000000; ++i)
        list.Add(random.Next());
    return list;
}

void Method1()
{
    List<int> list = createUnsortedList();
    list.Sort();
}

void Method2()
{
    List<int> list = createUnsortedList();
    list.OrderBy(x => x).ToList();
}

Результат:

• Метод 1: 0,67 секунд (List.Sort)
• Метод2: 3,10 секунды (OrderBy)

Это показывает, что производительность OrderBy является разумной даже для очень больших списков, но это не так быстро, как при использовании встроенного метода сортировки в списке. Вероятно, это связано с тем, что код для OrderBy немного более гибкий - он использует ключевой селектор, который должен оцениваться для каждого элемента.

Answer 3

Да, ваши предположения звучат правильно. Я сделал небольшой тест, чтобы подтвердить это.

На 5000000 целых чисел,

data.Sort();                           //  500 ms
data = data.OrderBy(a => a).ToList();  // 5000 ms

Answer 4

Быстрый анализ отражателя говорит мне, что методы сортировки списка используют быструю сортировку http://en.wikipedia.org/wiki/Quicksort через System.Collections.Generic.GenericArraySortHelper

SortedList использует Array.BinarySearch, чтобы выяснить, куда вставлять вещи в каждое добавление

У счетчиков нет логики сортировки

Быстрая сортировка - хороший выбор сортировки для большинства ситуаций, хотя она может приблизиться к O (n ^ 2), если вам действительно не повезло с входными данными.

Если вы подозреваете, что ваши входные данные представляют собой огромную кучу данных в неудачном (уже отсортированном) порядке для быстрой сортировки, трюк состоит в том, чтобы сначала рандомизировать данные (что всегда дешево), а затем выполнить сортировка по рандомизированным данным. Есть несколько приемов, которые алгоритм быстрой сортировки может реализовать, чтобы смягчить проблему сортировки уже отсортированных (или почти отсортированных) входных данных, я не знаю, делает ли реализация BCL что-либо из этого.