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

91

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.

shole
źródło
17
Jak zawsze mówię: te (zwykle) nie są „najlepsze”. Gdy jednoznacznie zdefiniujesz, co rozumiesz przez „lepszy”, odpowiedź staje się oczywista.
Raphael
2
To dobre pytanie, ale mówi o tym, co uważałbym za dziurę w twoim wykształceniu, którą możesz rozważyć w celu skorygowania. To praktyczne doświadczenie, jeśli tak naprawdę nie napisałeś tych algorytmów podczas edukacji, możesz rozważyć ich napisanie teraz, podejrzewam, że odpowiedź na to pytanie stałaby się szybko oczywista, gdy próbowałeś znaleźć dla nich zastosowania.
Sam
@Sam Z mojego doświadczenia uważam, że na wykładach lub w niektórych podręcznikach są one pouczające, wprowadzają wiele algorytmów, analiz itp., Ale nie ma wielu praktycznych przypadków ani przykładowych scenariuszy, które A będzie przewyższał B. Mogą obejmować gatunek algorytmów od A do Z i niektóre problemy z zadaniami domowymi, ale dla mnie wszystkie mogą być rozwiązane tylko przez A lub tylko przez Z itp., w związku z tym zadane pytanie.
shole
5
Jeśli upierasz się, aby odłożyć na bok zainteresowanie akademickie, najlepszym praktycznym powodem do nauki algorytmów mniejszych niż optymalne jest rozpoznanie ich takimi, jakie są i zoptymalizowanie ich poprzez refaktoryzację do optymalnych. Nie możesz ulepszyć łuku i strzały do ​​broni, jeśli nie wiesz, do czego służą łuk i strzały.
candied_orange
1
W rzeczywistości zaproponowaliśmy stronę StackExchange, aby pomóc w takich kwestiach edukacyjnych w zakresie CS. Przyjdź, wesprzyj
vk2015

Odpowiedzi:

121

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(nlogn)

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.

Pseudonim
źródło
7
Świetna odpowiedź ze świetnymi przykładami! Nie wiedziałem, że nawet przepustka bąbelkowa ma praktyczne zastosowanie w prawdziwym świecie ...
shole
1
@shole Nie mam dużego doświadczenia w branży gier, ale wszystkie powyższe są w różnym stopniu ważne. (Oczywiście, rodzaje algorytmów, struktur danych i matematyki, których potrzebujesz do gier, prawdopodobnie różnią się od tych wymaganych dla baz danych lub bioinformatyki lub tego, co masz.) Gdybym był tobą, poszedłbym tutaj i zacząłbym oglądać: ręcznie robiony bohater. org Również może być warte przyczajenia się na gamedev.stackexchange.com
pseudonim
1
Wydajność pamięci podręcznej jest dużym czynnikiem, który jest bardzo niedokładnie zbadany (Google „ściana pamięci”).
Raphael
6
Ostrożnie, Quicksort jest średnio znacznie szybszy niż Heapsort, ale Heapsort jest bardziej spójny (wariancja czasu działania jest mniejsza, a najgorszy przypadek jest znacznie lepszy). A Heapsort przeskakuje w szyku w porównaniu z liniowymi skanami Quicksort z lewej i prawej strony, która robi wielką różnicę, gdy w grę wchodzi pamięć podręczna / stronicowanie.
vonbrand,
1
@shole Jakiego rodzaju tworzeniem gier jesteś zainteresowany? Istnieją co najmniej dwa bardzo różne subpola, grafika 3D i rozgrywka (w tym AI). Mam tylko doświadczenie z grafiką, ale mogę powiedzieć, że struktury danych i matematyka są niezwykle ważne w grafice, a także w mniejszym stopniu algorytmów. Jeśli używasz silnika, większość z tych rzeczy zostanie oczywiście załatwiona, ale nadal powinieneś zrozumieć podstawową matematykę geometrii 3D.
ogrodnik
51

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.
Raphael
źródło
4
+1 za uwzględnienie przesłanek dydaktycznych! Powiązane z kilkoma uzasadnieniami (zwłaszcza drugim i trzecim), obserwowanie, jak algorytmy i struktury danych są rozwijane i optymalizowane, uczy technik rozwoju i optymalizacji oraz zrozumienia kompromisów (uczenie się nie tylko „co”, ale także „jak” i „dlaczego” ).
Paul A. Clayton
2
Kolejną kwestią jest to, że analiza różnych alternatyw oferuje przykłady użytecznych narzędzi do analizy nowych algorytmów dla być może nietypowych ustawień.
vonbrand
1
Dobra uwaga, @vonbrand. Zamrożona analiza złożoności została wynaleziona w celu zrozumienia zachowania drzew pnia, ale drzewa pajęcze są rzadko stosowane w praktyce. W każdym razie, nie splay drzewa, jak opublikowano. Jądro systemu Windows NT słynie z drzew splay do implementacji map pamięci wirtualnej, ale nie zmienia kolejności przy każdym wyszukiwaniu.
pseudonim
1
@vonbrand Tak. Zrozumiałbym jednak, że ktoś najbardziej zainteresowany wymiarem przybornika w klasie algorytmów szydziłby z tego powodu.
Raphael
7

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 .

Ian Ringrose
źródło
chyba że 95% rzeczy, które próbujesz rozwiązać, jest związanych z uczeniem maszynowym. Nie rozumiem, w jaki sposób normalny programista może nawet mieć właściwą szansę, aby spróbować rozwiązać dowolny problem z prawdziwymi problemami ML.
Pinokio
3
Cel: znaleźć pracę z lepszą stawką niż 5%.
Raphael
Pamiętaj, że studiowanie CS to świetny sposób na zebranie wiedzy na temat algorytmów i struktur danych. Kodowanie to najlepsze zajęcie - dla programistów.
greybeard
5

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.

Bloke Down The Pub
źródło
5
Ta odpowiedź powtarza tylko punkty ze starszych.
Raphael
1

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.

Leherenn
źródło