Jak algorytmy sortowania mają się do programowania?

0

Dobrze znam kilka algorytmów: Kopcowanie, Dijkstra, Prim, Kruskal, DFS, BFS - miałem ostatnio z tego kolosa, więc musiałem ogarnąć. Zastanawiam się, jak to ma się do programowania w jakimś języku? Powiedzmy, że muszę posortować liczby, skąd mam wiedzieć jakiego algorytmu użyć, skoro różne robią to samo?

9

W aplikacjach biznesowych znajomość algorytmów niespecjalnie ma znaczenie, bo i tak używasz funkcji wbudowanych (jak np ogólne metody sort do sortowania). Z drugiej strony znajomość algorytmów pozwoli wyrobić sobie intuicje na temat złożoności operacji na gotowych strukturach danych czy algorytmach. Może się to przydać, bo np tworzenie kolejki priorytetowej z nieposortowanej kolekcji zajmuje czas O(n), a dorzucanie element po elemencie do kolejki priorytetowej daje sumaryczną złożoność O(n lg n) - taka różnica jest już czasami odczuwalna. Sortowanie kolekcji po odflitrowaniu elementów daje często znacznie szybszy ogólny kod niż gdy sortujemy przed odfiltrowaniem, itd Niektórzy też popełniają błędy tworząc wielokrotnie zagnieżdżone pętle i wpadając w wysoką złożoność obliczeniową podczas gdy przerobienie logiki może poskutkować zmniejszeniem złożoności.

1
Mały Szewc napisał(a):

Dobrze znam kilka algorytmów: Kopcowanie, Dijkstra, Prim, Kruskal, DFS, BFS - miałem ostatnio z tego kolosa, więc musiałem ogarnąć. Zastanawiam się, jak to ma się do programowania w jakimś języku? Powiedzmy, że muszę posortować liczby, skąd mam wiedzieć jakiego algorytmu użyć, skoro różne robią to samo?

Z opisu odnoszę wrażenie, ze wiesz CO robią algorytmy, ale nie do końca JAK to robią i gdzie jest różnica. Kluczowe przy wyborze jest zrozumienie:

  • złożoności czasowej i pamięciowej
  • danych wejściowych

Dla problemu sortowania, również powinieneś wiedzieć czym jest "stabilność" (tj. zachowanie kolejności elementów wejściowych, które mają tę samą wartość).

Z perspektywy programisty sortowanie jest często zaimplementowane w bibliotece standardowej, więc nie wymyślasz koła od nowa tylko stosujesz bibliotekę. W aplikacjach biznesowych rzadko (moje doświadczenia, więc u innych może być "często") zdarza się, że masz dane wejściowe, które pozwalają na optymalizację sortowania przez zliczanie i jeszcze rzadziej, że sortowanie jest krytycznym punktem przetwarzania (pomijam sub-optymalne zapytania bazodanowe z "ORDER BY").

2

Efekt jest niby ten sam, ale nie zawsze. Nie każdy algorytm działa tak samo i tak samo dobrze na danym zestawie danych. Wiele zależy od nich samych - jakiego są typu, czy są wstępnie posortowane, ich rozmiar. Środowisko też jest ważne - może akurat działasz na sprzęcie, gdzie pamięć jest malutka i raczej trzeba wybierać algorytm o małym zapotrzebowaniu na dodatkową pamięć?

Może akurat operacja insertowania dla twojego data setu jest bardzo kosztowana i raczej trzeba wybrać algorytm, który mało używa tej operacji?

Może operujemy na danych, które akurat są w formie worst-case dla wybranego algorytmu, więc lepiej użyć innego?

A może algorytm musi być stable? Nie każdy jest.

Ta wiedza, mimo, że wydaje się być obskórna i nieprzydatna, to jest ważna, zwłaszcza jeśli robisz, albo chcesz robić cokolwiek więcej niż klepać do końca życia templaty w htmlu czy elementarne crudowe api restowe wystawiające operacje dla bloga.

I o ile raczej pewne jest, że sam nie będziesz musiał implementować od nowa algorytmów, bo po co wymyślać koło ponownie, to i tak wiedza o tym JAK działa dany algorytm, umożliwi ci wybór tego, który będzie najlepszy dla danej aplikacji.Poza tym to też pokazuje na rozmowie rekrutacyjnej, że cokolwiek się orientujesz w temacie.

Złożonośc obliczeniowa mimo wszystko pozostaje bardzo ważnym zagadanieniem.

0
Mały Szewc napisał(a):

Dobrze znam kilka algorytmów: Kopcowanie, Dijkstra, Prim, Kruskal, DFS, BFS - miałem ostatnio z tego kolosa, więc musiałem ogarnąć.

A co tu znać? W Tarnowie licealiści też je znają.

Zastanawiam się, jak to ma się do programowania w jakimś języku? Powiedzmy, że muszę posortować liczby, skąd mam wiedzieć jakiego algorytmu użyć, skoro różne robią to samo?

Nie bój się, fakt, że zadajesz takie pytanie będąc studentem informatyki praktycznie wyklucza szansę, że będziesz wykorzystywać tą wiedzę w praktyce.

0

Znajomość tych algorytmów pozwala ominąć problem "ponownego wymyślania koła".
I nie mam na myśli tyko faktu o którym wspomniał Wibowit, że są biblioteki, które realizują dany algorytm (np Sort), ale łatwiej napisać taki algorytm w przyzwoity sposób.
Poza tym jeśli się koduje coś co używa jednego z tych algorytmów, to jego nazwanie pozwala czytelnikowi szybciej zrozumieć kod (mówisz wtedy specjalistycznym językiem, zrozumiałym dla większości).
I na koniec uczenie się tych algorytmów jest dobrym ćwiczeniem intelektualnym, gdy przyjdzie w myśleć coś swojego będzie łatwiej.

A algorytmów jest dużo i nigdy nie poznasz wszystkich. Warto je poznawać, żeby zobaczyć jak bardzo przebiegłe rozwiązania znajdują inni
Mój ulubiony przykład to "Heavy Hitter", bo pokazuje jak z prostego problemu wycisnąć bardzo cwane rozwiązanie (tu celem jest stała złożoność pamięciowa).

1 użytkowników online, w tym zalogowanych: 0, gości: 1