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ć?

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.

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 .

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.).

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.