Wydajność wbudowanych sorterów kolekcji .NET

Question

Pojawiło się pytanie, jak posortować listę. Podano kilka metod od podstawowego List.Sort() do List.OrderBy(). Najśmieszniejszy był roll-your-own-SelectionSort. Szybko przegłosowałem to, ale to mnie zastanowiło; czy nie zamawiałbyś Linby na OrderBy(), czy zrobił to samo? myList.OrderBy (x => x.Property) .ToList() tworzyłby iterator, który w zasadzie znajduje minimalną wartość projekcji w tym, co pozostało z kolekcji, a plon ją zwraca. Przechodząc przez całą listę, jest to sortowanie według wyboru.

Który zmusił mnie do myślenia; jakie algorytmy używają wbudowane sortowniki dla list, sortowanych, pełnych itp. i czy należy ich unikać w przypadku dużych kolekcji? SortedList, ponieważ pozostaje posortowany według klucza, prawdopodobnie używałby jednoprzebiegowego InsertionSort przy każdym dodaniu; znajdź pierwszy indeks o wartości większej niż nowa i wstaw przed nim. Listy i tablice prawdopodobnie sprawiają, że MergeSort się dość sprawnie, ale nie znam rzeczywistego algorytmu za Sort(). Omówiliśmy OrderBy.

Co wiem powyżej, wydaje się wskazywać, że List.Sort() lub Array.Sort() są najlepszymi opcjami dla listy znanych rozmiarów, a używanie Linq do sortowania listy lub tablicy w pamięci powinno być zniechęcane . W przypadku strumienia, tak naprawdę nie ma innego sposobu niż OrderBy() przeliczalny; Utrata wydajności jest łagodzona przez fakt, że można przechowywać dane w postaci strumienia zamiast konieczności posiadania wszystkiego przed sortowaniem.

EDIT:

Ogólny konsensus jest, że Sort() jest szybsza podano konkretną implementację listy lub macierzy. OrderBy jest rozsądny, ale wolniejszy, ponieważ dodaje O (N) złożoność wyodrębniania tablicy z przejętego przelicznika. Inicjalizacja SortedList kończy się jako O (N^2) z powodu tego, co znajduje się pod maską. Morał z tej historii, użyj List.Sort() zamiast List.OrderBy(), gdy masz prawdziwą listę.

Answer 1

Enumerable.OrderBy() slurps IEnumerable <> do tablicy i używa szybkiego sortowania. O (n) Wymagania dotyczące pamięci. Jest to wykonywane przez klasę wewnętrzną w System.Core.dll, EnumerableSort<TElement>.QuickSort(). Koszt przechowywania czyni go niekonkurencyjnym z prostym sortowaniem listy, jeśli ją masz, ponieważ lista <> sortuje w miejscu. Linq często optymalizuje się, sprawdzając prawdziwe możliwości IEnumerable za pomocą operatora is. Nie działa tutaj, ponieważ lista <> .Sort jest destrukcyjna.

Lista <> .Sort i Array. Użyj szybkiego sortowania w miejscu.

SortedList <> ma złożoność O (n) dla wstawienia, dominującą złożoność O (log (n)) znalezienia punktu wstawienia. Zatem umieszczenie N nieposortowanych przedmiotów będzie kosztować O (n^2). SortedDictionary <> używa drzewa czerwono-czarnego, co daje wstawkę złożoności O (log (n)). Zatem O (nlog (n)) do wypełnienia go, tak samo jak amortyzowany szybki sort.

Answer 2

Szybkie gąsior przez reflektor mówi mi, że metody sortowania listy wykorzystują quicksort http://en.wikipedia.org/wiki/Quicksort przez System.Collections.Generic.GenericArraySortHelper

SortedList wykorzystuje Array.BinarySearch aby dowiedzieć się, gdzie wstawić rzeczy na każdy Dodaj

rachmistrzów nie ma logiki sortowania

Quicksort jest dobrym wyborem do sortowania w większości sytuacji, ale może zbliżyć się do O (n^2), jeśli masz naprawdę pecha z danymi wejściowymi.

Jeśli podejrzewasz, że dane wejściowe być ogromny stos danych w pechowym (już posortowane) Aby quicksort trik ma losowe dane pierwsza (co zawsze jest tanie), a następnie wykonaj sortowanie na dane zrandomizowane. Jest kilka sztuczek, które algorytm quicksort może zaimplementować, aby złagodzić problem sortowania już posortowanych (lub prawie posortowanych) danych wejściowych, nie wiem, czy implementacja BCL wykonuje którąkolwiek z tych operacji.

Answer 3

Jednym ze sposobów, aby dowiedzieć się, wydajność każdej metody jest go zmierzyć:

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

Wynik:

• Method1: 0.67 sekund (List.Sort)
• Method2: 3.10 sekund (OrderBy)

Pokazuje to, że działanie OrderBy jest uzasadnione nawet dla bardzo dużych list, ale nie jest tak szybkie, jak użycie wbudowanej metody Sortowania na liście. Jest tak prawdopodobnie dlatego, że kod dla OrderBy jest nieco bardziej elastyczny - wymaga selektora kluczy, który musi zostać oceniony dla każdego elementu.

Answer 4

Tak, twoje założenia brzmią dobrze. Zrobiłem mały test, aby to potwierdzić.

On 5000000 liczb całkowitych,

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