Quicksort i nie przejmuj się?

Zwłaszcza gdy piszesz aplikacje „standardowe” (inne niż HPC), czy zastanawiasz się, jaki algorytm sortowania wybrać, czy po prostu decydujesz się na szybkie sortowanie (które większość bibliotek po prostu nazywa sortowaniem)? Do pewnego stopnia może być opłacalne w określonych sytuacjach, ale z drugiej strony odpowiednia optymalizacja wymaga czasu na analizę problemu i wykonanie testów porównawczych.

Ogólnie rzecz biorąc, użycie domyślnych metod, chyba że istnieje szczególna potrzeba zrobienia czegoś bardziej egzotycznego, sprawia, że ​​wszystko jest o wiele bardziej czytelne / zrozumiałe na drodze IMHO.

Jeśli zauważysz (lub w niektórych przypadkach mocno podejrzewasz), że masz problem z wydajnością, to jest czas na zwiększenie złożoności.

Z drugiej strony, jeśli używasz wystarczająco niskiego języka, że ​​nie ma wbudowanego sortowania dla tego rodzaju obiektów, które musisz sortować, spróbuj wybrać jeden lub dwa, które obejmują wszystkie twoje bazy i zaimplementuj je.

Zawsze wywołuj dostarczone procedury biblioteczne, chyba że masz bardzo, bardzo dobry powód, aby tego nie robić (i musisz udokumentować, dlaczego tak jest).

Wynika to z faktu, że algorytmy sortowania są trudne do uzyskania absolutnie poprawne. Wystąpił błąd w szybkim sortowaniu Java z bardzo dużymi zestawami danych, które zostały zidentyfikowane, naprawione i dostarczone klientom przez firmę Sun, więc nie trzeba było tego robić.

Również domyślne sortowanie w Javie 7 zostało zaktualizowane do nowszego, lepszego sortowania. Również za darmo.

Chyba domyślny sortowania jest provably nie wystarczająco dobre dla ciebie, trzymać.

Pewnego razu na konferencji usłyszałem o tym fajną historię.

W firmie Microsoft ktoś pisał aplikację VB (ok. VB 3) i wysłał e-maile do wielu osób z informacją, że ma mnóstwo wartości i chciał, aby pojawiały się w comboboxie, jak powinien to zrobić.

Wszyscy nurkowali po swoje stare podręczniki informatyki, szukając wysoce wydajnych procedur i przenosząc je do Visual Basic i wysyłając je do niego. Jeden facet właśnie odesłał „ile wartości w comboboxie?”.

„Około 50” nadeszła odpowiedź.

„Po prostu ustaw posortowaną właściwość na PRAWDA”.

W 99,9999% przypadków sortowanie najlepiej przeprowadzać przy użyciu biblioteki, kontroli lub wyboru SQL, ponieważ różnica wydajności między procedurą biblioteczną a wszystkim, co piszesz, będzie nieznaczna, a nakład pracy i nakładów związanych z konserwacją znacznie przewyższą konsekwencje.

Czas wyciągnąć klasyczny cytat o przedwczesnej optymalizacji. W większości przypadków to naprawdę nie ma znaczenia. Do diabła, z szybkością procesorów w dzisiejszych czasach, prawdopodobnie możesz sortować bąbelkowo większość zestawów danych i tak naprawdę nie zauważasz zbyt wiele. Ale gdy sortujesz naprawdę duże zestawy danych, a wydajność sortowania staje się problemem, zdecydowanie powinieneś spojrzeć na inne opcje.

Chociaż to oczywiście nie ma znaczenia dla bitów i odcinków czasu. Uważam, że scalanie jest łatwiejsze do napisania i zrozumienia niż szybkie sortowanie. Więc jeśli mam napisać własny algorytm sortowania, użyłbym tego.

Przynajmniej w kompetentnie napisanej bibliotece spodziewałbym się, że wbudowana wersjasort będzie implementowana jako Introsort, a nie tylko Quicksort. Różnica rzadko ma duże znaczenie, ale Introsort eliminuje najgorszą wydajność Quicksort przy minimalnym wpływie na bardziej powszechne przypadki.

Jednak, aby odpowiedzieć na twoje pytanie: tak - od tego zwykle powinieneś zacząć i dopóki / jeśli nie masz wyników profilera wskazujących, że jest to problem, tam powinien pozostać.