Zastanawiam się tylko, dlaczego Java
i .NET Framework
używa domyślnie innego algorytmu sortowania.
W Javie domyślnie Array.Sort()
korzysta z algorytmu scalania sortowania i jak mówi Wikipedia.com :
W Javie metody Arrays.sort () używają sortowania scalonego lub dostrajanego szybkiego sortowania w zależności od typów danych oraz do przełączania wydajności implementacji na sortowanie wstawiania, gdy sortowanych jest mniej niż siedem elementów tablicy
W .NET Framework Array.Sort/List.Sort()
używa szybkiego sortowania jako domyślnego algorytmu sortowania ( MSDN ):
List.Sort () używa Array.Sort, który wykorzystuje algorytm QuickSort. Ta implementacja działa w sposób niestabilny; to znaczy, jeśli dwa elementy są równe, ich kolejność może nie zostać zachowana. Natomiast stabilny sort zachowuje porządek elementów, które są równe.
Patrząc na świetną tabelę „Porównanie algorytmów” , możemy zobaczyć, że oba algorytmy zachowują się zupełnie inaczej niż perspektywy najgorszego przypadku i wykorzystania pamięci:
Zarówno Java
i .NET
są wielkie Ramki dla rozwoju rozwiązań dla przedsiębiorstw, zarówno ma platform wbudowanych rozwoju. Dlaczego więc domyślnie używają innego algorytmu sortowania, jakieś myśli?
Odpowiedzi:
Choć deterministyczne są same komputery, inżynieria komputerowa nie jest nauką ścisłą. Dwie osoby, mając tę samą dziedzinę problemów, przeprowadzą analizę i opracują dwa różne rozwiązania, które spełniają wszystkie ograniczenia problemu. Empiryczne określenie, która z nich jest „lepsza” w ogólnym przypadku, może być trudne lub niemożliwe.
Domyślam się, że .NET QuickSort jest nałożony na coś w MFC lub Windows API i prawdopodobnie jest odziedziczony z dużo starszych wersji Windows, gdzie wielowątkowa przewaga MergeSort nie byłaby brana pod uwagę nawet na komputerach dzień. ( EDYCJA: nie jest, chociaż programiści Microsoft byli fanboyami QuickSort od dawna, o czym świadczy ten wybór implementacji sortowania od MS-DOS).
Java, która nie może korzystać z żadnej implementacji specyficznej dla platformy, ponieważ Java została zaprojektowana od zera, aby była całkowicie niezależna od platformy, poszła inną drogą. Kto wie, dlaczego MergeSort wyszedł na górę; zgaduję, że implementacja wygrała konkurencję wydajnościową z innymi rodzajami, które wymyślili programiści, albo że MergeSort z przestrzenią O (n) wyglądał najlepiej na papierze pod względem wydajności w najlepszym i najgorszym przypadku (MergeSort nie ma pięty Achillesa związanej z wyborem elementów, takim jak QuickSort, a najlepszym jej przykładem jest lista prawie posortowana, chociaż często jest to najgorsza opcja QuickSort). Wątpię, czy początkowo rozważano korzyści z wielowątkowości, ale obecne wdrożenie może być wielowątkowe.
źródło
List<T>.Sort
w .NET używa natywnej metody zaimplementowanej w CLR (jeśli nie używasz niestandardowego modułu porównującego), ale nie ma zależności od bibliotek systemu operacyjnego.Różne zespoły projektowe w dwóch różnych firmach doszły do różnych wniosków dotyczących zwykłego przypadku użycia swoich ram i komponentów i postanowiły je odpowiednio wdrożyć.
Zasadniczo każda firma dokonała analizy, przeanalizowała bazę klientów i podjęła odpowiednie decyzje.
Nie można oczekiwać, że analizy przeprowadzane przez różne firmy i zespoły przy użyciu różnych założeń i surowych danych doprowadzą do tego samego wniosku.
źródło
To pytanie jest nieco nieaktualne, ponieważ Java używa teraz Timsort (od Java 7)
Z wymienionych wymienionych algorytmów:
Quicksort ma niekorzystną wydajność w najgorszym przypadku przy O (n ^ 2), ale jest nieco lżejszy / zajmuje mniej pamięci, więc oferuje lepszą wydajność w typowym przypadku.
Mergesort ma gwarantowaną najgorszą wydajność przy O (n log n), ale przenosi nieco więcej kosztów ogólnych i wymagań dotyczących pamięci. Jest również automatycznie stabilny (tzn. Utrzymuje równe elementy w tej samej kolejności).
Projektanci Java wydają się być nieco bardziej konserwatywni / skoncentrowani na „właściwej rzeczy”, więc nie jest zaskoczeniem, że wybrali Mergesort z dwóch, ponieważ oferuje lepsze gwarancje.
Nie masz pewności, dlaczego Microsoft wybrał Quicksort, a może myśleli, że dzięki temu będą wyglądać lepiej w niektórych mikro-testach?
źródło