Jakie są mniej znane struktury danych i algorytmy, o których należy wiedzieć?

Question

Niedawno natrafiłem na strukturę danych SkipList. Naprawdę pomógł mi rozwiązać trudny do rozwiązania problem. Walczyłem, aby rozwiązać to za pomocą zbalansowanego drzewa binarnego, ale stało się to bardzo złożone, ponieważ drzewo musi być zawsze zrównoważone i chciałem poznać istnienie nie tylko określonej wartości, ale wartości w pewnym zakresie. SkipList pomógł mi skutecznie rozwiązać ten problem.

Zastanawiam się, jakie inne struktury danych muszę wiedzieć? Wiem o - Array, List, Stack, Queue, Linked List, hashtable, drzewo i jego różne formy, takie jak B-drzewo, Trie itp. Chciałbyś wiedzieć, czy uważasz, że inna struktura danych/koncepcja jest interesująca, a także przydatna w regularny cykl rozwoju.

Answer 1

Nie wspomniałeś o wykresach, które są bardzo potężne i jeśli o nich nie wiesz, zdecydowanie powinieneś je przeczytać. Wyszukaj algorytm Dijkstry i algorytm wyszukiwania A *, a także ogólne Głębokie pierwsze wyszukiwanie i pierwsze wyszukiwanie.

Pominięto również stosy, które są często używane jako podstawowa struktura kolejki priorytetowej. Sterty binarne są najprostsze, ale można też spojrzeć na sterty min-max-mediany, dwumianowe hałdy (szybkie scalenia) i stosy Fibonacciego (klawisz szybkiego zmniejszania - przydatne w przypadku niektórych algorytmów graficznych).

Inne interesujące struktury danych obejmują próby Patricii, które są próbami efektywnymi pod względem miejsca (wpisane jako podłańcuchy zamiast znaków), drzewa rozrzucone, które są zrównoważone i mogą być zaprogramowane jako trwałe. Również sprawdź filtry Bloom, które są probabilistyczną strukturą danych, która pozwala ci określić, czy element jest członkiem zbioru. Może mieć fałszywe alarmy, ale nie fałszywie negatywy i jest wydajny w czasie/przestrzeni.

Wreszcie można przejść do funkcjonalnej trasy i zajrzeć do niezmiennych i trwałych struktur danych. Wiele z nich to tylko funkcjonalne wersje struktur danych, które już znasz. Jeśli jesteś zainteresowany, to polecam sprawdzenie Okastaki Purely Functional Datastructures.

Answer 2

Masz zarówno "List", jak i "Listę powiązań", i nie jest wcale jasne, jaką różnicę (jeśli jakąkolwiek) zamierzasz między tymi dwoma. W każdym razie jedną oczywistą strukturą, którą pominąłeś, jest kupa (którą możesz zaklasyfikować jako typ drzewa, ale to w najlepszym razie nie jest pewne). Ostatecznie drzewa są podzbiorem wykresów, więc jeśli nie studiowałeś wykresów (ogólnie), prawdopodobnie jest to obszar do zbadania.

Chciałbym zauważyć, że żadna z nich nie jest szczególnie "świeża" - wszystkie znane są od dziesięcioleci. Większość tych naprawdę ogólnych struktur jest znana od dłuższego czasu. Ostatnio odkryte odnoszą się do bardziej konkretnych obszarów tematycznych.