Jakie algorytmy / struktury danych powinienem „rozpoznać” i znać po imieniu? [Zamknięte]

69

Chciałbym uważać się za dość doświadczonego programistę. Programuję od ponad 5 lat. Moim słabym punktem jest jednak terminologia. Jestem samoukiem, więc chociaż umiem programować, nie znam bardziej formalnych aspektów informatyki. Jakie więc praktyczne algorytmy / struktury danych mogę rozpoznać i poznać po imieniu?

Uwaga: nie proszę o rekomendację książkową dotyczącą implementacji algorytmów. Nie dbam o ich wdrożenie, chcę tylko móc rozpoznać, kiedy algorytm / struktura danych byłaby dobrym rozwiązaniem problemu. Proszę o więcej algorytmów / struktur danych, które powinienem „rozpoznać”. Na przykład znam rozwiązanie takiego problemu:

Zarządzasz zestawem szafek oznaczonych 0-999. Ludzie przychodzą do ciebie, aby wynająć szafkę, a następnie wracają, aby zwrócić klucz do szafki. Jak zbudowałbyś oprogramowanie do zarządzania wiedząc, które szafki są bezpłatne, a które używane?

Rozwiązaniem może być kolejka lub stos.

To, czego szukam, to: „w jakiej sytuacji należy użyć B-drzewa - jaki algorytm wyszukiwania powinien zostać tutaj użyty” itp. I może szybkie wprowadzenie w jaki sposób bardziej złożone (ale często używane) struktury danych / algorytmy działają.

Próbowałem spojrzeć na listę struktur danych i algorytmów Wikipedii, ale myślę, że to trochę przesada. Więc szukam bardziej podstawowych rzeczy, które powinienem rozpoznać?

Earlz
źródło
10
Głosowanie na zakończenie jako „nie konstruktywne”. Każda odpowiedź będzie całkowicie subiektywna - nie ma zgody co do tego, co „należy” wiedzieć.
Oded
2
Jaka część tego problemu z szafką wymaga porządkowania wejścia / wyjścia? [wskazówka!]
Telastyn
5
@Otwarta jest absolutnie lista, która, jak sądzę, większość ludzi zgodzi się na to, jakie struktury danych i algorytmy powinien znać dobrze zorientowany programista.
David Cowden,
6
@Oded Brak konsensusu? Co z programem szkolenia wprowadzającego na temat algorytmów i struktur danych w informatyce? Całkiem dobrze znormalizowany i recenzowany . Dobry punkt wyjścia.
MarkJ
3
Alternatywne rozwiązanie; zakładamy, że ładujesz w ciągu dnia i masz maksymalną opłatę. Przymocuj papierową etykietkę do klucza, gdy wpuszczasz szafkę i napisz na niej numer dnia Juliana. Po zwróceniu klucza spójrz na tag, aby obliczyć należny czynsz. Brakujące lub uszkodzone tagi przyciągają maksymalną opłatę. Nieużywane klucze są przechowywane w torbie (ponieważ nie trzeba wybierać żadnego konkretnego klucza z wolnych kluczy przy wynajmie szafki). Całkowity rozmiar struktury danych: zero bitów. Wszystkie części algorytmu są O (1).
James Youngman

Odpowiedzi:

78

Obiektywna odpowiedź:

Podczas gdy moja początkowa odpowiedź na to pytanie opierała się na moich doświadczeniach empirycznych jako wkrótce studenta CS oraz na mojej przewidywanej opinii o typach ludzi, z którymi chciałem pracować w dziedzinie CS. W rzeczywistości istnieje obiektywna odpowiedź (w odniesieniu do subiektywnych opinii stowarzyszeń obliczeniowych ACM SIGCSE i IEEE). Co 10 lat ACM i organy IEEE współpracują w ramach wspólnej publikacji, która szczegółowo przedstawia sugestie dotyczące programu studiów licencjackich z zakresu informatyki w oparciu o profesjonalną wiedzę o stanie branży komputerowej. Więcej informacji można znaleźć na stronie cs2013.org . Komitet publikuje raport końcowy zawierający listę rekomendacji programowych .

Mimo to nadal uważam, że moja lista jest całkiem dobra.

Oryginalna odpowiedź poniżej.


Co powinienem wiedzieć?

Minimum

Uważam, że biegły programista powinien posiadać wiedzę z zakresu informatyki na poziomie co najmniej licencjackim. Pewnie, możesz być skuteczny w wielu zawodach, mając tylko niewielki podzbiór informatyki, ze względu na solidną społeczność, na której opiera się CS, i zawężone ukierunkowanie większości profesjonalnych stanowisk. Ponadto wiele osób będzie dalej specjalizować się po studiach licencjackich. Nie uważam jednak, aby były pretekstem, aby nie być wtajemniczonym w podstawową wiedzę na temat CS.

Aby odpowiedzieć na pytanie tytułowe, oto, co powinien wiedzieć student studiów licencjackich (podstawa programisty) po ukończeniu studiów:

Struktury danych

  • Reprezentacja danych maszynowych
    • Jedynki, dopełnienie dwóch i powiązana arytmetyka
    • Słowa, wskaźniki, zmiennoprzecinkowe
    • Dostęp do bitów, przesuwanie i manipulowanie
  • Połączone listy
  • Tabele skrótów (mapy lub słowniki)
  • Tablice
  • Drzewa
  • Półki na książki
  • Kolejki
  • Wykresy
  • Bazy danych

Algorytmy

  • Sortowanie:
    • Sortowanie bąbelkowe (aby dowiedzieć się, dlaczego jest źle)
    • Sortowanie przez wstawianie
    • Scal sortowanie
    • Szybkie sortowanie
    • Sortowanie według stylu Radix, sortowanie zliczające i sortowanie kubełkowe
    • Sortuj sterty
    • Sortowanie Bogo i kwantowe (=
  • Badawczy:
    • Wyszukiwanie liniowe
    • Wyszukiwanie binarne
    • Głębokie pierwsze wyszukiwanie
    • Szerokość Pierwsze wyszukiwanie
  • Manipulacja ciągiem
  • Iteracja
  • Tree Traversal
  • Lista Traversal
  • Funkcje mieszania
  • Konkretna implementacja tabeli mieszania, drzewa, listy, stosu, kolejki, tablicy i zestawu lub kolekcji
  • Algorytmy planowania
  • Przejście i manipulacja systemem plików (na poziomie i- węzła lub równoważnego).

Wzorce projektowe

  • Modularyzacja
  • Fabryka
  • Budowniczy
  • Singel
  • Adapter
  • Dekorator
  • Flyweight
  • Obserwator
  • Iterator
  • Stan [maszyna]
  • Kontroler widoku modelu
  • Gwintowanie i równoległe wzorce programowania

Paradygmaty

  • Tryb rozkazujący
  • Obiektowy
  • Funkcjonalny
  • Deklaracyjny
  • Programowanie statyczne i dynamiczne
  • Znaczniki danych

Teoria złożoności

  • Przestrzenie złożoności
  • Obliczalność
  • Regularne, bezkontekstowe i uniwersalne maszyny Turinga kompletne języki
  • Wyrażenia regularne
  • Liczenie i podstawowa kombinatoryka

Poza

Aby przejść do pytania, o które pytasz w dalszej części pytania, jeśli znasz powyższe, powinieneś być w stanie łatwo zidentyfikować odpowiedni wzorzec, algorytm i strukturę danych dla danego scenariusza. Należy jednak pamiętać, że często nie ma najlepszego rozwiązania. Czasami może być konieczne wybranie mniejszego zła lub nawet wybranie jednego z dwóch równie realnych rozwiązań. Z tego powodu potrzebujesz ogólnej wiedzy, aby móc bronić swojego wyboru przed rówieśnikami.

Oto kilka wskazówek dotyczących algorytmów i struktur danych:

  • Wyszukiwania binarnego można (i należy) używać tylko do posortowanych danych.
  • Rodzaje stylów Radix są niesamowite, ale tylko wtedy, gdy masz sortowane skończone klasy rzeczy.
  • Drzewa nadają się do prawie wszystkiego, podobnie jak Stoły Hash. Funkcjonalność tabeli skrótów można ekstrapolować i wykorzystać do rozwiązania wielu problemów kosztem wydajności.
  • Tablice mogą być używane do tworzenia kopii zapasowych większości struktur danych wyższego poziomu. Czasami „struktura danych” to po prostu sprytna matematyka do uzyskiwania dostępu do lokalizacji w tablicy.
  • Wybór języka może być różnicą między wyciąganiem włosów lub przejeżdżaniem przez problem.
  • Tabela ASCII i tablica zawierająca 128 elementów tworzą domyślną tablicę skrótów (=
  • Wyrażenia regularne mogą rozwiązać wiele problemów, ale nie można ich używać do analizowania HTML .
  • Czasami struktura danych jest równie ważna jak algorytm.

Niektóre z powyższych mogą wydawać się bezmyślne, a niektóre mogą wydawać się niejasne. Jeśli chcesz, żebym zagłębił się bardziej szczegółowo, mogę. Ale mam nadzieję, że gdy napotkamy bardziej konkretne pytanie, takie jak: „Zaprojektuj funkcję, która liczy liczbę wystąpień każdego znaku w ciągu znaków”, możesz spojrzeć na wskazówkę dotyczącą tabeli ASCII i 128 elementów tworzących czysty ukryty skrót tabele odpowiedzi.

Opierając się na tych pomysłach, zaproponuję odpowiedź na problem z szafką opisany w twoim pytaniu.


Odpowiedz na problem związany z pytaniem.

To może nie być najlepsza odpowiedź na twoje pytanie, ale myślę, że jest to interesujące, które nie wymaga niczego zbyt złożonego. I z pewnością pokona złożoność czasową korzystania z kolejki lub stosu, które wymagają liniowego czasu, aby ustalić, czy szafka jest wolna, czy nie.

Masz 0-999 szafek. Teraz, ponieważ masz stałą liczbę szafek, możesz łatwo wyobrazić sobie funkcję haszującą bez kolizji w zakresie 0-999. Ta funkcja to po prostu h (x) = x mod 1000. Teraz [koncepcyjnie] zbuduj tablicę skrótów z kluczami całkowitymi i zawartością tablicy elementów 1000 jako wartości. Jeśli klient chce zarezerwować szafkę 78 do użytku, po prostu wstaw 78 do funkcji skrótu (zwracając 78), a następnie dodaj tę liczbę do podstawowego wskaźnika tablicy - przechowując prawdziwą wartość w miejscu wskazanym przez wartość przesunięcia . Podobnie, jeśli chcesz sprawdzić, czy 78 jest w użyciu, po prostu przeczytaj wartość przechowywaną w tej lokalizacji i sprawdź wartość true.

To rozwiązanie działa w trybie ciągłym dla wyszukiwania i przechowywania, w przeciwieństwie do przechowywania i wyszukiwania dziennika (n) w przypadku kolejki priorytetowej wspieranej przez drzewo binarne. Opis jest celowo obszerny, dzięki czemu można zobaczyć, że wyższe pojęcia sprowadzane są do wydajnego algorytmu.

Teraz możesz zapytać: co, jeśli muszę znać wszystkie dostępne szafki, czy kolejka priorytetowa nie byłaby lepsza? Jeśli w kolejce priorytetowej znajduje się k dostępnych szafek, iteracja nad wszystkimi z nich zajmie k kroków. Ponadto, w zależności od implementacji kolejki priorytetowej, może być konieczne przebudowanie kolejki priorytetowej, gdy spojrzysz na to wszystko ... co wymagałoby kroków k * log (k): (k <1000). W rozwiązaniu macierzowym musisz tylko iterować tablicę 1000 elementów i sprawdzić, które są otwarte. Możesz również dodać dostępną lub używaną listę do implementacji, aby sprawdzić tylko w czasie k.

David Cowden
źródło
1
Świetna odpowiedź! Chciałbym również dodać, że naprawdę powinieneś być pewny korzystania z predefiniowanych funkcji / struktur danych używanego języka, na przykład algorytmów i struktur danych stl w C ++ lub Java API dla Java.
marktani
1
Doskonały! Zwłaszcza „Wyrażenia regularne mogą rozwiązać wiele problemów, ale nie można ich używać do analizowania HTML”.
FrustratedWithFormsDesigner
2
Odpowiedź była dobra, dopóki nie pojawił się „problem”. W ogóle nie ma powodu, aby używać kolejki priorytetowej lub tabeli skrótów. Wystarczy prosty stos. Dodaj iterację, aby uzyskać pełną listę bezpłatnych szafek, jeśli chcesz.
Matthieu M.,
1
czy powinniśmy dodać relacyjną bazę danych + SQL, znajomość drzewa B +, teorię kompilatora, wiedzę na temat organizacji sprzętu, znajomość teorii systemu operacyjnego, znajomość sieci TCP / IP?
dan_l
1
Jestem sceptycznie nastawiony do Wzorów Projektowych. Wiele z nich jest przydatnych w niektórych rodzajach języków, podczas gdy w innych są bezużyteczne i / lub niepotrzebne. Możesz także dodać heurystykę w ramach algorytmów oraz struktury danych trie i Skip-List. Tradycyjne algorytmy / struktury danych osiągają limit synchronicznego dostępu, ale można je pokonać innymi nietradycyjnymi podejściami wykorzystującymi wiele wątków i współbieżność. Heurystyka może radykalnie zmniejszyć liczbę potrzebnych wyszukiwań, a struktury takie jak lista pominięć pozwolą na zapisanie struktury danych bez globalnej blokady.
Evan Plaice
6

Podręcznik projektowania algorytmów autorstwa Stevena S. Skieny wydaje się być źródłem, którego szukasz. Druga część to niejawna lista problemów z przeglądem powiązanych algorytmów. Istnieje wersja internetowa .

AProgrammer
źródło
3
świetna książka, ale nie czuję, że trzeba ją opanować, aby naprawdę zostać programistą. Właśnie go kupiłem i od 1979 r. Otrzymuję wynagrodzenie za program. (I tak, kupiłem go, wierząc, że mogę się z niego czegoś nauczyć.)
Kate Gregory
@KateGregory Kupiłem książkę i naprawdę nie mogłem jej zrozumieć, ponieważ znam tylko języki wysokiego poziomu, takie jak Ruby i JavaScript (bez drzew binarnych, list powiązanych itp.) ... W końcu przestałem ją czytać.
bigpotato
4

Nie ma „powinien”. A. Zapoznaj się z podstawowymi klasami złożoności (liniowa, logarytmiczna itp.) B. Zdaj sobie sprawę, że możesz zrobić wszystko z prostą tablicą, jak możesz z fantazyjną strukturą danych, taką jak B-drzewo. Sztuczka przy wyborze odpowiedniej struktury / algorytmu polega na równoważeniu wydajności, oczekiwanego rozmiaru danych wejściowych i złożoności implementacji.

Są też abstrakcyjne, ale niezwykle użyteczne rzeczy (chociaż użyteczność nie jest od razu oczywista): maszyny stanów, teoria grafów, teoria wypukłości (programowanie liniowe itp.).

zvrba
źródło
1
Nie należy lekceważyć znaczenia, kiedy trzeba wiedzieć, czego użyć. Ponieważ problemy, które rozwiązałeś za pomocą prostej tablicy, wrócą i ugryzą cię, gdy będziesz miał ochotę na tego dużego klienta i dowiesz się, że aplikacja, która działała dobrze przez lata, spowalnia do indeksowania tylko dlatego, że użyłeś opcji bąbelkowej zamiast Quicksort.
Pieter B
3

MIT publikuje bezpłatne notatki z wykładów, filmy, zadania i materiały egzaminacyjne do wprowadzenia do algorytmów . Te tytuły wykład listy algorytmów / struktur danych objętych.

Jest to recenzowany konsensus co do tego, co powinieneś wiedzieć. To prawdopodobnie także świetne źródło wiedzy.

MarkJ
źródło