Sens nauki bardziej skomplikowanych algorytmów

Witam.
Od pewnego czasu przerabiam książkę "Algorytmy bez tajemnic" Thomasa H. Cormena (czytam oraz samodzielnie implementuje te algorytmy). Po przerobieniu około połowy mam wrażenie, że nie ma sensu uczyć się tych bardziej zaawansowanych algorytmów na przyszłość (oczywiście nie uczę się na pamięć). Oprócz tego, że nie zapamiętam większości tych algorytmów na dłuższy czas, to jest to bardzo nudne oraz mam wrażenie, że mógłbym ten czas poświęcić na naukę ciekawszych rzeczy. Czy według was jest sens takiej nauki, kiedy poznałem już podstawowe algorytmy? Jakie algorytmy i struktury danych powinno się znać jako programista? Możecie polecić jakieś źródła warte uwagi?
Z góry dziękuję za pomoc.

To jest cienka książeczka, dokończyć ją to chyba nie problem, a w ogóle to nawet nie jest wstęp do algorytmów :)

Najważniejszą kwestią (w pracy typowego programisty) z punktu widzenia algorytmiki jest znajomość złożoności obliczeniowej (i pamięciowej też). Ostatnio w firmie zamieniłem algorytm z O(n*n) na O(n) i serwis przestał zarzynać cyklicznie CPU na kilka minut za każdym razem. W zasadzie nie był to wielki problem (bo zarzynał tylko jeden rdzeń, a lag nadal nie był problemem z punktu widzenia biznesowego), ale utrudniał analizę spadku wydajności systemu.

Żeby wyrobić sobie intuicję na temat złożoności obliczeniowej pasuje dobrych kilka algorytmów i struktur danych poznać i zrozumieć w jakim stopniu i dlaczego złożoności poszczególnych operacji w różnych algorytmach i strukturach danych się różnią.

Komentując to co napisał @Wibowit
Notację O warto znać i rozumieć konsekwencje, ale nie warto się przejmować na codzień.
Widziałem tony godzin zmarnowane na absurdy typu szukanie binarne w tablicach o długości 6 elementów.

Właczamy yellow alert jak wiemy, że pracujemy listami o długości w okolicach co najmniej 1000. (no chyba, że coś jest np O(n!), ale to raczej w korpo pracy się nie wydarza) - A zanim zajrzymy w big O warto najpierw umieć odpalić i zrozumieć profiler.

Inna sprawa, że wiele podstawowych optymalizacji (typu sortowania i takie binary searche) są w zasadzie w nowoczesnych językach (bibliotekach) robione z automatu.
Czytając opis jakiegoś sorta warto wiedzieć co to znaczy stable.

Ogólnie - to smutna sprawa, ale w pracy korpo klepacza nie za bardzo się większość zawartości przydaje.
W jednej firmie świętowaliśmy, bo kolega dostał do napisania algorytm, taki nietrywialny, z opisem matematycznym.
Pełna zazdrość, ale i duma, bo 10 latach pracy w korpo - w naszym pokoju, w naszym zespole - coś takiego!

Najwięcej z algorytmami miałem do czynienia robiąc przy bieda game devie - wtedy można było się wyżyć (ale to był krótki czas).

Algorytmów nie uczy sie na pamięć, tak samo jak matematyki nie uczy się na pamięć. Kluczowe jest rozumienie pewnych wzorców postępowania i metod rozwiązywania problemów. Wiele algorytmów o których czytasz opiera sie o ten sam schemat np. dziel i zwyciężaj czy algorytmy zachłanne. To są rzeczy które, wbrew pozorom, wcale nie tak rzadko sie w życiu pojawiają. Oczywiscie nie w taki sposób że klepiesz merge sorta czy wydawanie reszty, ale trafiasz na problem który można rozwiązać analogicznymi metodami.
Oprócz tego warto rozumieć jak coś działa i kiedy tego uzywać, tutaj koniecznie w przypadku struktur danych. Trzba rozumieć czym się różni HashSet od Listy.

jarekr000000 napisał(a):

Komentując to co napisał @Wibowit
Notację O warto znać i rozumieć konsekwencje, ale nie warto się przejmować na codzień.
Widziałem tony godzin zmarnowane na absurdy typu szukanie binarne w tablicach o długości 6 elementów.

Właczamy yellow alert jak wiemy, że pracujemy listami o długości w okolicach co najmniej 1000. (no chyba, że coś jest np O(n!), ale to raczej w korpo pracy się nie wydarza) - A zanim zajrzymy w big O warto najpierw umieć odpalić i zrozumieć profiler.

Akurat ta zmiana z O(n*n) do O(n) poskutkowała mniejszą ilością kodu niż była wcześniej. Zmiana polegała na zastąpieniu Set.exists(predicate) (musi lecieć po elementach po kolei i odpalać predykat) na Set.contains(element) (tutaj HashSet może policzyć hasha i wyszukać element w O(1)). W innym przypadku optymalizacja polegała np na wyniesieniu tworzenia mapy poza wewnętrzną pętle - przez to, że O(n) razy była tworzona identyczna mapa złożoność całego algorytmu mocno rosła.

Często na początku, podczas tworzenia serwisu są dane o małym rozmiarze, ale z czasem rosną. Co się dzieje jak takie kulawe algorytmy niedomagają? Zamiast sprofilować i zoptymalizować algorytm (oj, to musi być zbyt skomplikowane!) pierwszym odruchem jest: "zróbmy więcej instancji serwisu, niech działają równolegle". Średniawe rozwiązanie. Zbicie złożoności z O(n*n) do O(n) niespecjalnie da się zastąpić dorzucaniem kolejnych instancji.

Inna sprawa, że wiele podstawowych optymalizacji (typu sortowania i takie binary searche) są w zasadzie w nowoczesnych językach (bibliotekach) robione z automatu.

Właśnie obecność gotowców w bibliotekach (nie)standardowych sprawia, że dbanie o złożoność obliczeniową da się zrobić elegancko, zwięźle i czytelnie. Dalej można używać tych gotowców, ale odpowiednio je dobierając, tak by wykorzystać ich mocne strony.

1. Jeśli algorytmy z Coremana nazywasz zaawansowanymi, to niewiele w życiu widziałeś algorytmiki. I prawdopodobnie nie zobaczysz jeśli w połowie książki zadajesz tego typu pytania na forum.

2. Nie zaufałbym człowiekowi, który nie umie zaimplementować listy jedno/dwu kierunkowej, tablicy haszującej, bufora cyklicznego i przynajmniej sortowania bąbelkowego i nie wie co to stos i jak się na nim operuje bez zaglądania do książki. Dlaczego? Bo to są dość "straightforward" rzeczy do implementacji. Jak dorzucisz do tego grafy (przeszukiwanie ich oraz minimalne drzewa rozpinające oraz najkrótsze ścieżki między węzłami to będziesz na przyzwoitym poziomie. Taki mądry jak mniej więcej student 1go/2go roku informatyki być powinien w tej działce. To najbardziej podstawowe podstawy podstaw bez których w bardziej zaawansowane zagadnienia nie polecisz a i w życiu codziennym będzie dużo ciężej niż być powinno. Jak się jeszcze minmaxa dołączysz to nawet prymitywne AI do gry strategicznej będziesz w stanie zaklepać.

Wibowit napisał(a):

Często na początku, podczas tworzenia serwisu są dane o małym rozmiarze, ale z czasem rosną. Co się dzieje jak takie kulawe algorytmy niedomagają? Zamiast sprofilować i zoptymalizować algorytm (oj, to musi być zbyt skomplikowane!) pierwszym odruchem jest: "zróbmy więcej instancji serwisu, niech działają równolegle". Średniawe rozwiązanie. Zbicie złożoności z O(n*n) do O(n) niespecjalnie da się zastąpić dorzucaniem kolejnych instancji.

Mam inne obserwacje.
Dorzucanie instancji nie zawsze jest takie proste. Sensowne profilowanie bywa trudne, zwłaszcza jak nie mamy narzędzi i doświadczenia.
Skutki:
Wiele razy widziałem zespoły walczące dniami (rekord to kilka miesięcy i to akurat było w mojej firmie - ważna nauka) z objawami typu strona wolno się ładuje poprzez zgadywanie na podstawie kodu: o tu w sqlu są 3 joiny więc pewnie dlatego wolne .
Mistrzowie mieli podłączone dynatrace i naprawdę ładne metryki z produkcji, a i tak woleli przez 3-4 tygodnie zgadywać :/

Z moich obserwacji to dla takiego typowego klepacza jak pewnie 85% tego forum (w tym i rowniez mnie) algorytmy sie przydaja tylko do przejscia etapu rozmowy jak rzucaja codility. Co projekt, co prace pytaja o algorytmy, jakies zasady SOLID i ich zrozumienie, a po odpaleniu gita klasy po 600-800 loc i ogolny bajzel. Nie studiowalem informatyki, domyslam sie ze tam mecza algosami, bo sam dla kolegi pisalem pare razy jakis algorytm, lata mijaja i pozniej męczeni staja sie męczącymi, tylko o co tutaj chodzi?

tylko o co tutaj chodzi?

Pewnie jak tak to Odbierasz, to w zły sposób, ale starają się nauczyć przyszłych inżyinerów rozwiązywania problemów.

Zgadzam się z przedmówcami. Samo wprowadzenie do algorytmów ma 1000 stron. Sztuka programowania Knuta to 5 grubych tomów. I tam dopiero masz zaawansowane algorytmy gdy autor poświęca 200 stron na poszukiwanie dobrego algorytmu generowania liczb losowych. To co jest w "Algorytmy bez tajemnic" określił bym jako podstawy.

U mnie w pracy często pojawia się problem złożoności obliczeniowej, bo przy przetwarzaniu dużej ilości danych zaczyna miec znaczenie że algo jest O(N^2). Nie jest to wiedza bezużyteczna. Miałem też kilka przypadków że implementowaliśmy jakieś algorytmy na podstawie artykułów naukowych i sprawdzaliśmy który nam lepiej będzie działać w praktyce.

Z drugiej strony rekrutacja algorytmiczna jest w modzie, więc chociażby z tego też względu warto znać. IMHO Dobry programista powinien być w stanie napisać QuickSorta mając w głowie jedynie idee jak to ma działać. Analiza złożoności tego algorytmu to już zupełnie inna kwestia (jeżeli chcemy to zrobić porządnie całkując)

Warto też wiedzieć że są takie problem że "nie ma chu** we wsi", i żaden komputer nie będzie ich w stanie szybko rozwiązać (lub w ogóle rozwiązać). Przydaje się gdy kumpel będzie namawiał Ciebie do dołączenie do startup który alokuje np. sale wykładowe do zajęć i dostępności profesorów automatycznie.

Na koniec dodam że praktyczne implemntacje algorytmów często różnią się od tych książkowych, bo starają się też w rozsądny sposób obsłużyć przypadki brzegowe. W praktyce czystego QSorta nie spotkach a raczej hybrydowe połączenie QSort + HeapSort. Albo dziwactwa w stylu TimSort.