Praktyczne zastosowania różnych struktur danych [zamknięte]

Dużo się mówi o strukturach danych, ale nie mogę znaleźć prostej listy struktur danych i ich praktycznego zastosowania. Próbuję uczyć się do rozmowy kwalifikacyjnej i myślę, że to by mi pomogło, wraz z wieloma innymi. Szukam czegoś takiego:

Struktura danych - przykład / używany do

Hash table - szybkie wyszukiwanie danych ... następnie podaj przykład

Tablica - ...

Drzewo binarne - ...

Jeśli gdzieś jest taki zasób, daj mi znać.

Dzięki!

EDYCJA: Mam na myśli, że wikipedia jest dobra i wszystko, ale na większości stron tak naprawdę nie ma listy praktycznych zastosowań. Szukam czegoś więcej.

Listę znalazłem w podobnym pytaniu, wcześniej w StackOverflow:

Hash Table - służy do szybkiego wyszukiwania danych - tablica symboli dla kompilatorów, indeksowanie baz danych, pamięci podręczne, unikalna reprezentacja danych.

Trie - słownik, taki jak znaleziony w telefonie komórkowym do autouzupełniania i sprawdzania pisowni.

Drzewo sufiksów - szybkie wyszukiwanie pełnotekstowe używane w większości edytorów tekstu.

Stos - operacja cofnij / ponów w procesorach tekstu, ocena wyrażeń i analiza składni, wiele maszyn wirtualnych, takich jak JVM, jest zorientowanych na stos.

Kolejki - badanie transportu i operacji, w którym różne jednostki są przechowywane i przetrzymywane w celu późniejszego przetworzenia, tj. Kolejka pełni funkcję bufora.

Kolejki priorytetowe - planowanie procesów w jądrze

Drzewa - parsery, system plików

Drzewo Radix - tablica routingu IP

Drzewo BSP - grafika komputerowa 3D

Wykresy - powiązania / relacje w serwisach społecznościowych, routing, sieci komunikacji, organizacja danych itp.

Sterta - dynamiczna alokacja pamięci w lisp

To jest odpowiedź pierwotnie opublikowana przez RV Pradeep

Inne, mniej przydatne linki:

Aplikacje są wymienione tylko dla niektórych struktur danych

Nie ukierunkowany na aplikację, przez dobre podsumowanie i odpowiedni

Jestem na tej samej łodzi co ty. Muszę się uczyć do rozmów technicznych, ale zapamiętywanie listy nie jest zbyt pomocne. Jeśli masz 3-4 godziny do stracenia i chcesz zanurkować głębiej, polecam to sprawdzić

mykodeschool Przeglądałem
Coursera i inne zasoby, takie jak blogi i podręczniki, ale uważam, że albo nie są wystarczająco wyczerpujące, albo na drugim końcu spektrum są zbyt obfite w terminologię informatyczną.

Koleś na wideo ma kilka wykładów na temat struktur danych. Nie przejmuj się głupimi rysunkami ani lekkim akcentem. Musisz zrozumieć nie tylko, którą strukturę danych wybrać, ale także kilka innych punktów, które należy wziąć pod uwagę, gdy ludzie myślą o strukturach danych:

• wady i zalety wspólnych struktur danych
• dlaczego istnieje każda struktura danych
• jak to faktycznie działa w pamięci
• konkretne pytania / ćwiczenia i decydowanie, której struktury użyć, aby uzyskać maksymalną efektywność
• jasne wyjaśnienie Big 0

Jeśli jesteś zainteresowany, zamieściłem również notatki na githubie.

W moim rozumieniu struktura danych to wszelkie dane znajdujące się w pamięci dowolnego systemu elektronicznego, którym można efektywnie zarządzać. Często jest to gra pamięciowa lub szybszy dostęp do danych. Jeśli chodzi o pamięć, istnieją kompromisy związane z zarządzaniem danymi w oparciu o koszt dla firmy tego produktu końcowego. Efektywnie zarządzany informuje nas, jak najlepiej można uzyskać dostęp do danych w oparciu o podstawowe wymagania produktu końcowego. To wyjaśnienie na bardzo wysokim poziomie, ale struktury danych to rozległy temat. Większość ankieterów zagłębia się w struktury danych, które mogą pozwolić sobie na omówienie podczas wywiadów w zależności od posiadanego czasu, czyli powiązanych list i powiązanych tematów.

Teraz te typy danych można podzielić na prymitywne, abstrakcyjne, złożone, w oparciu o sposób, w jaki są logicznie konstruowane i dostępne.

• prymitywne struktury danych są podstawowymi elementami składowymi wszystkich struktur danych, mają dla nich ciągłą pamięć: boolean, char, int, float, double, string.
• złożone struktury danych to struktury danych złożone z więcej niż jednego pierwotnego typu danych: klasa, struktura, suma, tablica / rekord.
• abstrakcyjne typy danych to złożone typy danych, które mają sposób na efektywny dostęp do nich, co nazywa się algorytmem. W zależności od sposobu dostępu do danych struktury danych są podzielone na liniowe i nieliniowe typy danych. Połączone listy, stosy, kolejki itp. To liniowe typy danych. sterty, drzewa binarne i tabele skrótów itp. są nieliniowymi typami danych.

Mam nadzieję, że to pomoże ci się zanurzyć.

Doskonała książka „ Podręcznik projektowania algorytmów” autorstwa Skiennej zawiera ogromne repozytorium algorytmów i struktury danych.

W przypadku wielu problemów struktury danych i algorytmy są opisywane, porównywane i omawiane w praktyce. Autor podaje również odniesienia do wdrożeń i oryginalnych artykułów naukowych.

Książka jest świetna, aby mieć ją na swoim biurku, jeśli szukasz najlepszej struktury danych do rozwiązania problemu. Jest również bardzo pomocny w przygotowaniu do rozmowy kwalifikacyjnej.

Innym wspaniałym źródłem jest Słownik struktur danych i algorytmów NIST .

Kilka bardziej praktycznych zastosowań struktur danych

Czerwono-czarne drzewa (używane, gdy występuje częste wstawianie / usuwanie i kilka wyszukiwań) - Grupowanie K-średnich przy użyciu czerwono-czarnego drzewa, baz danych, bazy danych o prostym umyśle, wyszukiwanie słów w słownikach, wyszukiwanie w Internecie

Drzewa AVL (więcej wyszukiwań i mniej wstawiania / usuwania) - analiza danych i eksploracja danych oraz aplikacje wymagające większej liczby wyszukiwań

Sterta minimalna - algorytmy grupowania

Każdy ranking różnych struktur danych będzie przynajmniej częściowo powiązany z kontekstem problemu. Pomogłoby to w nauce analizowania wydajności algorytmów w czasie i przestrzeni. Zwykle stosuje się „notację dużego O”, np. Wyszukiwanie binarne odbywa się w czasie O (log n), co oznacza, że ​​czas wyszukiwania elementu jest logiem (domyślnie o podstawie 2) liczby elementów. Intuicyjnie, ponieważ każdy krok odrzuca połowę pozostałych danych jako nieistotne, podwojenie liczby elementów zwiększy czas o 1 krok. (Wyszukiwanie binarne skaluje się raczej dobrze). Wydajność przestrzeni dotyczy tego, jak rośnie ilość pamięci dla większych zestawów danych. Należy również zauważyć, że notacja duże-O ignoruje stałe czynniki - w przypadku mniejszych zestawów danych algorytm O (n ^ 2) może nadal być szybszy niż algorytm O (n * log n), który ma wyższy współczynnik stały.

Oprócz czasu i przestrzeni inne cechy obejmują to, czy struktura danych jest posortowana (drzewa i listy przeskoków są sortowane, a tabele skrótów nie), trwałość (drzewa binarne mogą ponownie wykorzystywać wskaźniki ze starszych wersji, podczas gdy tabele skrótów są modyfikowane w miejscu) itp.

Chociaż będziesz musiał nauczyć się zachowania kilku struktur danych, aby móc je porównać, jednym ze sposobów zrozumienia, dlaczego różnią się one wydajnością, jest dokładne przestudiowanie kilku. Sugerowałbym porównanie list połączonych pojedynczo, drzew wyszukiwania binarnego i list pomijanych , z których wszystkie są stosunkowo proste, ale mają bardzo różne cechy. Zastanów się, ile pracy potrzeba, aby znaleźć wartość, dodać nową wartość, znaleźć wszystkie wartości w kolejności itp.

Istnieje wiele tekstów na temat analizy wydajności algorytmów / struktury danych, które ludzie zalecają, ale to, co naprawdę miało dla mnie sens, to nauka OCaml. Radzenie sobie ze złożonymi strukturami danych jest mocną stroną ML, a ich zachowanie jest znacznie jaśniejsze, gdy można uniknąć wskaźników i zarządzania pamięcią, jak w C. (Nauka OCaml tylko po to, aby zrozumieć struktury danych, jest jednak prawie na pewno długą drogą. :))