Jakie są mniej znane, ale przydatne struktury danych?

Istnieje kilka struktur danych, które są naprawdę przydatne, ale są nieznane większości programistów. Które to są?

Wszyscy wiedzą o połączonych listach, drzewach binarnych i skrótach, ale co na przykład o listach pomijania i filtrach Bloom . Chciałbym poznać więcej struktur danych, które nie są tak powszechne, ale warto je poznać, ponieważ polegają na świetnych pomysłach i wzbogacają zestaw narzędzi programisty.

PS: Interesują mnie również takie techniki, jak Taniec linków, które sprytnie wykorzystują właściwości wspólnej struktury danych.

EDYCJA : Spróbuj dołączyć bardziej szczegółowo linki do stron opisujących struktury danych. Spróbuj także dodać kilka słów o tym, dlaczego struktura danych jest fajna (jak już wskazał Jonas Kölker ). Spróbuj także podać jedną strukturę danych na odpowiedź . Pozwoli to, aby lepsze struktury danych przesunęły się na samą górę na podstawie samych głosów.

Próbki , znane również jako drzewa prefiksowe lub drzewa krytyczne , istnieją od ponad 40 lat, ale nadal są stosunkowo nieznane. Bardzo fajne użycie prób opisano w „ TRASH - Dynamiczna struktura danych LC-trie i hash ”, która łączy trie z funkcją haszującą.

Filtr Bloom : tablica bitów m bitów, początkowo wszystkie ustawione na 0.

Aby dodać element, uruchom go przez k funkcji skrótu, które dadzą ci k wskaźników w tablicy, którą następnie ustawisz na 1.

Aby sprawdzić, czy element znajduje się w zestawie, oblicz k wskaźników i sprawdź, czy wszystkie są ustawione na 1.

Oczywiście daje to pewne prawdopodobieństwo fałszywych trafień (według wikipedii jest to około 0,61 ^ (m / n), gdzie n jest liczbą wstawionych elementów). Fałszywe negatywy nie są możliwe.

Usunięcie elementu jest niemożliwe, ale możesz zaimplementować filtr liczenia kwitnienia , reprezentowany przez tablicę liczb całkowitych i przyrost / spadek.

Lina : Jest to sznurek, który pozwala na tanie przedpole, podciągi, środkowe wstawki i uzupełnienia. Naprawdę miałem z tego tylko jeden raz, ale żadna inna struktura nie wystarczyłaby. Zwykłe ciągi znaków i tablice były po prostu zbyt drogie dla tego, co musieliśmy zrobić, a odwracanie wszystkiego nie wchodziło w rachubę.

Listy pomijania są dość schludne.

Wikipedia
Lista pominięć to probabilistyczna struktura danych, oparta na wielu równoległych, posortowanych połączonych listach, o wydajności porównywalnej do drzewa wyszukiwania binarnego (dziennik zamówień n średni czas dla większości operacji).

Można je stosować jako alternatywę dla zrównoważonych drzew (stosując raczej równoważenie probalistyczne niż ścisłe wymuszanie równoważenia). Są łatwe do wdrożenia i szybsze niż powiedzmy, czerwono-czarne drzewo. Myślę, że powinny one znaleźć się w każdym dobrym zestawie narzędzi dla programistów.

Jeśli chcesz uzyskać szczegółowe wprowadzenie do list pominięć tutaj, jest link do filmu z wykładem MIT z Wprowadzenie do algorytmów na ich temat.

Ponadto tutaj jest aplet Java pokazujący wizualnie Listy Pomiń.

Indeksy przestrzennej , w szczególności R drzew i KD-drzew , przechowywania danych przestrzennych sprawnie. Są dobre do danych współrzędnych geograficznych mapy oraz algorytmów VLSI do lokalizacji i tras, a czasem do wyszukiwania najbliższych sąsiadów.

Tablice bitów przechowują pojedyncze bity w sposób kompaktowy i umożliwiają szybkie operacje bitowe.

Zamki błyskawiczne - pochodne struktur danych, które modyfikują strukturę, aby mieć naturalne pojęcie „kursor” - bieżąca lokalizacja. Są one naprawdę przydatne, ponieważ gwarantują, że wskazania nie mogą być poza zasięgiem - używane, np. W menedżerze okien xmonad do śledzenia, które okno się skupiło.

O dziwo, można je uzyskać, stosując techniki od rachunku różniczkowego do rodzaju oryginalnej struktury danych!

Tu jest kilka:

• Przyrostek próbuje. Przydatny do prawie wszystkich rodzajów wyszukiwania ciągów (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Zobacz także tablice sufiksów; nie są tak szybkie jak drzewa z przyrostkami, ale są o wiele mniejsze.

• Splay drzewa (jak wspomniano powyżej). Powód, dla którego są fajni, jest trojaki:

  • Są małe: potrzebujesz tylko lewego i prawego wskaźnika, tak jak w każdym drzewie binarnym (nie trzeba przechowywać informacji o kolorze lub rozmiarze węzła)
  • Są (względnie) bardzo łatwe do wdrożenia
  • Oferują one optymalną zamortyzowaną złożoność dla całego szeregu „kryteriów pomiarowych” (czas logowania jest tym, który wszyscy znają). Widziećhttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Drzewa wyszukiwania uporządkowane według stosu: przechowujesz w drzewie kilka par kluczy (klucz, prio), dzięki czemu jest to drzewo wyszukiwania w odniesieniu do kluczy i uporządkowane według stosu w odniesieniu do priorytetów. Można pokazać, że takie drzewo ma unikalny kształt (i nie zawsze jest w pełni zapakowane do lewej). Losowe priorytety dają oczekiwany czas wyszukiwania O (log n), IIRC.

• Niszą są listy przyległości dla niekierowanych grafów płaskich z zapytaniami sąsiada O (1). Jest to nie tyle struktura danych, co konkretny sposób organizacji istniejącej struktury danych. Oto jak to zrobić: każdy wykres płaski ma węzeł o stopniu co najwyżej 6. Wybierz taki węzeł, umieść jego sąsiadów na liście sąsiadów, usuń go z wykresu i powtarzaj, aż wykres będzie pusty. Gdy otrzymasz parę (u, v), poszukaj u na liście sąsiadów v i v na liście sąsiadów u. Oba mają rozmiar co najwyżej 6, więc jest to O (1).

Zgodnie z powyższym algorytmem, jeśli u i v są sąsiadami, nie będziesz mieć zarówno u na liście v, jak i v na liście u. Jeśli potrzebujesz tego, po prostu dodaj brakujących sąsiadów każdego węzła do listy sąsiadów tego węzła, ale zapisz, ile części listy sąsiadów należy przejrzeć, aby szybko wyszukać.

Myślę, że alternatywy bez blokowania do standardowych struktur danych, tj. Kolejka bez blokad, stos i lista, są znacznie pomijane.
Są one coraz bardziej istotne, ponieważ współbieżność staje się wyższym priorytetem i są znacznie bardziej godnym podziwu celem niż używanie Mutexów lub blokad do obsługi jednoczesnych odczytów / zapisów.

Oto kilka linków
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Linki do pliku PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Blog Mike'a Actona (często prowokujący) zawiera doskonałe artykuły na temat projektowania i podejść bez blokady

Myślę, że Disjoint Set jest całkiem sprytny w przypadkach, gdy trzeba podzielić kilka elementów na odrębne zestawy i przydzielić członkostwo. Dobra implementacja operacji Union i Find powoduje zamortyzowane koszty, które są faktycznie stałe (odwrotne do funkcji Ackermnana, jeśli prawidłowo przywołam klasę struktur danych).

Kupy Fibonacciego

Są one używane w niektórych z najszybszych znanych algorytmów (asymptotycznie) do wielu problemów związanych z grafem, takich jak problem najkrótszej ścieżki. Algorytm Dijkstry działa w czasie O (E log V) ze standardowymi stosami binarnymi; użycie stosów Fibonacciego poprawia to do O (E + V log V), co jest ogromnym przyspieszeniem dla gęstych wykresów. Niestety mają one jednak wysoki stały współczynnik, co często czyni je niepraktycznymi w praktyce.

Każdy, kto ma doświadczenie w renderowaniu 3D, powinien znać drzewa BSP . Zasadniczo jest to metoda polegająca na konstruowaniu sceny 3D w taki sposób, aby można ją było renderować, znając współrzędne kamery i położenie.

Podział przestrzeni binarnej (BSP) to metoda rekurencyjnego dzielenia przestrzeni na zbiory wypukłe przez hiperpłaszczyzny. Podział ten powoduje przedstawienie sceny za pomocą struktury danych drzewa zwanej drzewem BSP.

Innymi słowy, jest to metoda rozbicia misternie ukształtowanych wielokątów na wypukłe zestawy lub mniejsze wielokąty składające się całkowicie z kątów nierefleksyjnych (kąty mniejsze niż 180 °). Aby uzyskać bardziej ogólny opis partycjonowania przestrzeni, zobacz Partycjonowanie przestrzeni.

Początkowo takie podejście zaproponowano w grafice komputerowej 3D w celu zwiększenia wydajności renderowania. Niektóre inne aplikacje obejmują wykonywanie operacji geometrycznych z kształtami (konstrukcyjna geometria bryłowa) w CAD, wykrywanie kolizji w robotyce i grach komputerowych 3D oraz inne aplikacje komputerowe, które wymagają obsługi złożonych scen przestrzennych.

Drzewa Huffmana - używane do kompresji.

Spójrz na Finger Trees , szczególnie jeśli jesteś fanem wspomnianych wcześniej czysto funkcjonalnych struktur danych. Stanowią one funkcjonalną reprezentację trwałych sekwencji wspierających dostęp do końców w zamortyzowanym stałym czasie oraz konkatenację i podział logarytmiczny czasowy wielkości mniejszego kawałka.

Zgodnie z oryginalnym artykułem :

Nasze funkcjonalne drzewa 2-3 palców są przykładem ogólnej techniki projektowania wprowadzonej przez Okasaki (1998), zwanej ukrytym spowolnieniem rekurencyjnym . Zauważyliśmy już, że drzewa te są przedłużeniem jego ukrytej struktury deque, zastępując pary 2-3 węzłami, aby zapewnić elastyczność wymaganą do skutecznego łączenia i dzielenia.

Drzewo palców można sparametryzować za pomocą monoidu , a użycie różnych monoidów spowoduje różne zachowania drzewa. Pozwala to Finger Tree symulować inne struktury danych.

Bufor okrągły lub pierścieniowy - wykorzystywany między innymi do przesyłania strumieniowego.

Dziwi mnie, że nikt nie wspomniał o drzewkach Merkle (tj. Drzewach haszyszowych ).

Używany w wielu przypadkach (programy P2P, podpisy cyfrowe), gdy chcesz zweryfikować skrót całego pliku, gdy masz do dyspozycji tylko jego część.

<zvrba> Drzewa Van Emde-Boas

Myślę, że warto wiedzieć, dlaczego są fajni. Zasadniczo najważniejsze jest pytanie „dlaczego”;)

Moja odpowiedź jest taka, że ​​dają ci słowniki O (log n) z kluczami {1..n}, niezależnie od liczby używanych kluczy. Podobnie jak wielokrotne dzielenie na pół daje O (log n), powtarzane sqrting daje O (log log n), co dzieje się w drzewie vEB.

Co powiesz na drzewa splay ?

Przychodzą mi na myśl czysto funkcjonalne struktury danych Chrisa Okasakiego .

Interesujący wariant tabeli haszującej nazywa się Hashing z kukułką . Używa wielu funkcji skrótu zamiast tylko 1, aby poradzić sobie z kolizjami skrótu. Kolizje są rozwiązywane przez usunięcie starego obiektu z lokalizacji określonej przez podstawową wartość skrótu i ​​przeniesienie jej do lokalizacji określonej przez alternatywną funkcję skrótu. Mieszanie kukułki pozwala na bardziej efektywne wykorzystanie przestrzeni pamięci, ponieważ można zwiększyć współczynnik obciążenia nawet do 91% za pomocą tylko 3 funkcji skrótu i ​​nadal mieć dobry czas dostępu.

Min-maks sterty jest odmianą sterty , który implementuje dwukrotnie zakończony kolejka priorytetowa. Osiąga to poprzez prostą zmianę właściwości sterty: Drzewo jest uporządkowane w kolejności min-max, jeśli każdy element na parzystych (nieparzystych) poziomach jest mniejszy (większy) niż wszystkie dzieci i wnuki. Poziomy są ponumerowane od 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Lubię Cache Oblivious danych struktur . Podstawową ideą jest ułożenie drzewa w rekurencyjnie mniejszych blokach, aby skrzynki o różnych rozmiarach korzystały z bloków, które wygodnie do nich pasują. Prowadzi to do efektywnego wykorzystania buforowania we wszystkim, od pamięci podręcznej L1 w pamięci RAM do dużych fragmentów danych odczytywanych z dysku, bez konieczności poznawania specyfiki rozmiarów dowolnej z tych warstw buforowania.

Lewe, pochylone czerwono-czarne drzewa . Znacznie uproszczone wdrożenie czerwono-czarnych drzew przez Roberta Sedgewicka opublikowane w 2008 r. (~ Połowa wierszy kodu do wdrożenia). Jeśli kiedykolwiek miałeś problemy z owinięciem głowy wokół implementacji drzewa czerwono-czarnego, przeczytaj o tym wariancie.

Bardzo podobny (jeśli nie identyczny) do drzew Anderssona.

Kolejka kradzieży pracy

Bezblokowa struktura danych do podziału pracy na wiele wątków Implementacja kolejki kradzieży pracy w C / C ++?

Kupy ze skośno-dwumianowymi stertami : Gerth Stølting Brodal i Chris Okasaki:

Pomimo swojej długiej nazwy zapewniają asymptotycznie optymalne operacje sterty, nawet w ustawieniach funkcji.

• O(1)rozmiar, połączenie , wkładka, minimum
• O(log n) deleteMin

Zauważ, że zjednoczenie trwa O(1)raczej niż O(log n)czas, w przeciwieństwie do bardziej znanych stosów, które są często omawiane w podręcznikach struktury danych, takich jak stosy lewicowe . I w przeciwieństwie do hałd Fibonacciego , te asymptotyki są najgorszym przypadkiem, a nie amortyzowane, nawet jeśli są używane wytrwale!

W Haskell istnieje wiele implementacji .

Zostały one wspólnie wyprowadzone przez Brodala i Okasaki, po tym, jak Brodal wymyślił imperatywną stertę z tymi samymi asymptotykami.

• Kd-Drzewa , struktura danych przestrzennych wykorzystywana (między innymi) w ray tracingu w czasie rzeczywistym, ma tę wadę, że trójkąty, które przecinają się, przecinają różne przestrzenie. Ogólnie BVH są szybsze, ponieważ są bardziej lekkie.
• MX-CIF Quadtrees , przechowuj obwiednie zamiast dowolnych zestawów punktów, łącząc zwykły poczwórny z dwójkowym drzewem na krawędziach czworokątów.
• HAMT , hierarchiczna mapa skrótów z czasami dostępu, które generalnie przekraczają O-1 mapy skrótów ze względu na zaangażowane stałe.
• Odwrócony indeks , dość dobrze znany w kręgach wyszukiwarek, ponieważ służy do szybkiego wyszukiwania dokumentów związanych z różnymi wyszukiwanymi hasłami.

Większość z nich, jeśli nie wszystkie, jest udokumentowana w Słowniku algorytmów i struktur danych NIST

Kulki Drzew. Tylko dlatego, że ludzie chichoczą.

Drzewo kulkowe to struktura danych, która indeksuje punkty w przestrzeni metrycznej. Oto artykuł na temat ich budowania. Często służą do znajdowania najbliższych sąsiadów do punktu lub przyspieszania k-średnich.

Niezupełnie struktura danych; jest to raczej sposób na optymalizację dynamicznie przydzielanych tablic, ale bufory przerw używane w Emacsie są dość fajne.

Drzewo Fenwick. Jest to struktura danych służąca do zliczania sumy wszystkich elementów w wektorze, między dwoma podindeksami i i j. Trywialne rozwiązanie, wstępne obliczanie sumy od początku nie pozwala na aktualizację przedmiotu (musisz wykonać pracę O (n), aby nadążyć).

Drzewa Fenwicka pozwalają na aktualizację i zapytania w O (log n), a sposób działania jest naprawdę fajny i prosty. Jest to naprawdę dobrze wyjaśnione w oryginalnym artykule Fenwicka, dostępnym bezpłatnie tutaj:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Jego ojciec, drzewo RQM jest również bardzo fajny: pozwala zachować informacje o minimalnym elemencie między dwoma indeksami wektora, a także działa w aktualizacji O (log n) i zapytaniu. Lubię uczyć najpierw RQM, a potem Fenwick Tree.

Drzewa Van Emde-Boas . Mam nawet jego implementację w C ++ , dla maksymalnie 2 ^ 20 liczb całkowitych.

Zestawy zagnieżdżone są przydatne do reprezentowania drzew w relacyjnych bazach danych i uruchamiania na nich zapytań. Na przykład ActiveRecord (domyślna ORM Ruby on Rails) zawiera bardzo prostą wtyczkę z zestawem zagnieżdżonym , co sprawia, że ​​praca z drzewami jest trywialna.

Jest dość specyficzny dla domeny, ale struktura danych o pół krawędzi jest dość schludna. Umożliwia iterację po siatkach wielokątów (ścianach i krawędziach), co jest bardzo przydatne w grafice komputerowej i geometrii obliczeniowej.