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.
data-structures
Joel
źródło
źródło
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:
Jeśli jesteś zainteresowany, zamieściłem również notatki na githubie.
źródło
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.
Mam nadzieję, że to pomoże ci się zanurzyć.
źródło
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 .
źródło
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
źródło
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ą. :))
źródło