Java i .NET: Dlaczego domyślnie stosowane są różne algorytmy sortowania?

19

Zastanawiam się tylko, dlaczego Javai .NET Frameworkuż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:

wprowadź opis zdjęcia tutaj

Zarówno Javai .NETsą 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?

sll
źródło
1
Aby uzyskać dalszą dyskusję na temat porównania między tymi dwoma rodzajami, zobacz stackoverflow.com/q/680541/866022
yoozer8

Odpowiedzi:

10

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.

KeithS
źródło
1
List<T>.Sortw .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.
Joey
1
@Keith - .NET nie jest warstwowy i został zaprojektowany tak, aby był niezależny od platformy. Możesz zobaczyć implementację tutaj: github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/…
Robert MacLean
@RobertMacLean - „.NET nie jest nakładany na nic” nie jest prawdziwym stwierdzeniem, chociaż wykazałeś, że omawiana funkcja sortowania jest całkowicie „zarządzanym” kodem. Duże części platformy .NET, w tym obsługa kryptografii, biblioteki graficznego interfejsu użytkownika systemu Windows, interakcja interfejsu API systemu Windows (w tym kontrola procesów i wątków) są oparte na wcześniej istniejącym niezarządzanym kodzie, w tym MFC. Po prostu muszą być; Sam Windows ma tylko bardzo niewielki składnik .NET swojej bazy
kodowej
Pozostaje, że deweloperzy Microsoft są sprawdzonymi fanami QuickSorta nad innymi implementacjami, ponieważ QuickSort jest algorytmem z wyboru od MS-DOS, a to wpłynęłoby na ich decyzję o wdrożeniu sortowania .NET za pomocą tego algorytmu.
KeithS
Ta odpowiedź jest tak błędna, że ​​jestem szczerze zszokowana.
user9993
17

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.

Oded
źródło
5
Lub nawet te same założenia i surowe dane. . .
Wyatt Barnett,
Tak było chyba tylko siłą przyzwyczajenia - Microsoft został użyty do korzystania z (niestabilna) quicksort, Java chciał iść z rodzaju stabilnej ... i scalania sortowania był najszybszy znany stabilny ...
rogerdpack
12

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?

mikera
źródło