Jakie są powody uczenia się różnych algorytmów / struktur danych służących temu samemu celowi?

Zastanawiam się nad tym pytaniem, odkąd byłem studentem. To pytanie ogólne, ale opiszę poniżej przykłady.

Widziałem wiele algorytmów - na przykład dla problemów z maksymalnym przepływem znam około 3 algorytmów, które mogą rozwiązać problem: Ford-Fulkerson, Edmonds-Karp i Dinic, przy czym Dinic ma najlepszą złożoność.

W przypadku struktur danych - na przykład stosów - istnieją stosy binarne, stosy dwumianowe i stosy Fibonacciego, przy czym sterta Fibonacciego ma największą ogólną złożoność.

Mylę mnie: czy są jakieś powody, dla których musimy je wszystkie znać? Dlaczego nie po prostu uczyć się i zapoznawać z najbardziej złożoną?

Wiem, że najlepiej, jeśli znamy je wszystkie, chcę tylko wiedzieć, czy istnieją jakieś „bardziej uzasadnione” powody, takie jak niektóre problemy / algorytmy można rozwiązać tylko przy użyciu A, ale nie B itp.

W pewnym momencie czeka na mnie podręcznik z roboczym tytułem Struktury danych, algorytmy i kompromisy . Prawie każdy algorytm lub struktura danych, której prawdopodobnie nauczysz się na poziomie licencjackim, ma pewną funkcję, która sprawia, że ​​jest lepsza w niektórych aplikacjach niż w innych.

Weźmy na przykład sortowanie, ponieważ wszyscy znają standardowe algorytmy sortowania.

Po pierwsze, złożoność nie jest jedynym problemem. W praktyce ważne są czynniki stałe, dlatego (powiedzmy) szybkie sortowanie jest zwykle używane bardziej niż sortowanie sterty, mimo że szybkie sortowanie ma straszną złożoność najgorszego przypadku.

$O(n \log n)$

W innych przypadkach pomysły z algorytmu lub struktury danych mogą mieć zastosowanie do problemu specjalnego przeznaczenia. Sortowanie bąbelkowe wydaje się być zawsze wolniejsze niż sortowanie wstawiane na prawdziwym sprzęcie, ale pomysł wykonania przejścia bąbelkowego jest czasem dokładnie tym, czego potrzebujesz.

Rozważmy na przykład jakąś wizualizację 3D lub grę wideo na nowoczesnej karcie graficznej, w której chcesz rysować obiekty w kolejności od najbliższego aparatu do najdalszego od aparatu ze względów wydajnościowych, ale jeśli nie otrzymasz dokładnego zamówienia, sprzęt się tym zajmie. Jeśli poruszasz się po środowisku 3D, względna kolejność obiektów nie zmieni się bardzo między klatkami, więc wykonanie jednego przejścia bąbelkowego na każdą klatkę może być rozsądnym kompromisem. (Silnik Source firmy Valve robi to dla efektów cząsteczkowych.)

Istnieje trwałość, współbieżność, lokalizacja pamięci podręcznej, skalowalność w klastrze / chmurze i wiele innych możliwych powodów, dla których jedna struktura danych lub algorytm może być bardziej odpowiednia niż inna, nawet biorąc pod uwagę tę samą złożoność obliczeniową dla operacji, na których Ci zależy.

To powiedziawszy, nie oznacza to, że na wszelki wypadek powinieneś zapamiętać kilka algorytmów i struktur danych. Większość bitew polega na uświadomieniu sobie, że trzeba wykorzystać kompromis, i wiedzieć, gdzie szukać, jeśli uważasz, że może być coś odpowiedniego.

Oprócz tego, że istnieją niezliczone miary kosztów (czas pracy, zużycie pamięci, błędy pamięci podręcznej, nieprzewidywalne oddziały, złożoność implementacji, możliwość weryfikacji ...) na niezliczonych modelach maszyn (TM, RAM, PRAM, ...) , rozważania o średniej w stosunku do najgorszego przypadku, a także kwestie amortyzacji, często występują także różnice funkcjonalne wykraczające poza zakres podstawowej specyfikacji podręcznika.

Kilka przykładów:

• Mergesort jest stabilny tam, gdzie nie ma Quicksort.
• Drzewa wyszukiwania binarnego zapewniają iterację w kolejności, a tabele skrótów nie.
• Bellman-Ford radzi sobie z ujemnymi wagami krawędzi, Dijkstra nie.

Należy również rozważyć kwestie dydaktyczne :

• Jak łatwo jest zrozumieć bardziej zaangażowane rozwiązanie przed prostszymi? (Drzewa AVL (i ich analiza) bez BST; Dinic bez Ford-Fulkerson; ...)
• Czy widzisz te same zasady i wzorce, gdy jesteś narażony na tylko jedno rozwiązanie na problem w porównaniu z narażeniem na wiele rozwiązań?
• Czy ekspozycja tylko jednego rozwiązania na problem zapewnia wystarczające szkolenie (w kierunku opanowania)?
• Czy powinieneś wiedzieć, jakie rozwiązania zostały znalezione (aby zapobiec ponownemu odkrywaniu koła?)?
• Czy narażony na tylko jedno rozwiązanie na problem, zrozumiesz inne rozwiązania, które znajdziesz na wolności (powiedzmy, w prawdziwej bibliotece programistycznej)?

1. To jest coś, co często widzimy od typów programistów, którzy nie mają bogatego zestawu narzędzi CS.

W prawdziwym świecie prawdopodobnie będziesz pracować nad oprogramowaniem napisanym przez zespół innych osób. Część tego oprogramowania zostanie napisana przed twoimi narodzinami!

Aby zrozumieć stosowane algorytmy / struktury danych, bardzo przydatna jest znajomość dużej liczby algorytmów / struktur danych, w tym opcji, które nie są już uważane za „najnowocześniejsze”.

Będziesz także musiał pracować nad algorytmami, które nie są standardowe i są po prostu używane w aplikacji, nad którą pracujesz. Kiedy musisz ulepszyć te algorytmy, przekonasz się, że twój mózg został wypełniony przydatnymi metodami ulepszania algorytmów, ponieważ badałeś, jak inni ludzie ulepszyli algorytmy.

To wyróżnia kogoś, kto studiował informatykę, od kogoś, kto dopiero nauczył się programować. W większości prac, w których pracowałem, był czas, kiedy studiowałem informatykę, mogłem rozwiązać problem, którego nie potrafiłby programista „wyciągnięty z książek”, ale w 95% przypadków stwierdziłem, że studiowanie informatyki nie przyniosło mi żadnej korzyści nad innymi doświadczonymi programistami .

Wiele osób słusznie wspomniało, że często nie ma jednego najlepszego algorytmu - zależy to od sytuacji.

Istnieje również możliwość, że pewnego dnia spotkasz się z nieznaną sytuacją. Im więcej algorytmów znasz, tym większa szansa, że ​​znasz taki, który jest prawie rozwiązaniem, którego możesz użyć jako podstawy.

Wiele świetnych odpowiedzi, po prostu czegoś, czego moim zdaniem brakuje, choć odpowiedź Raphaela wspomina o tym nieco.

Należy również wziąć pod uwagę łatwość wdrożenia.
Zwykle nie jest to problem z algorytmami sortowania, ponieważ większość platform / języków ma już zaimplementowany jeden (i często lepszy niż to, co można zrobić), ale bardziej niezwykłe algorytmy mogą być niedostępne.
W zależności od problemu może nie być potrzebny najlepszy algorytm, jeśli czas wdrożenia wynosi 1 dzień w porównaniu do 2 tygodni.