Jakie są mniej znane, ale przydatne struktury danych?

795

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.

f3lix
źródło

Odpowiedzi:

271

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

David Phillips
źródło
12
bardzo często używane przez osoby sprawdzające pisownię
Steven A. Lowe
Tryby serii są również interesującym wariantem, w którym używasz tylko prefiksu ciągów jako węzłów i w inny sposób przechowujesz listy ciągów w węzłach.
Torsten Marek
Silnik wyrażeń regularnych w Perl 5.10 automatycznie tworzy próby.
Brad Gilbert,
Z mojego doświadczenia wynika, że ​​próby są boleśnie kosztowne, biorąc pod uwagę, że wskaźnik jest zwykle dłuższy niż znak, co jest wstydem. Są odpowiednie tylko dla niektórych zestawów danych.
Joe
18
Ponieważ żadne pytanie SO, niezależnie od tematu, nie jest kompletne bez wspominania o jQuery .... John Resig, twórca jQuery, ma interesującą serię struktur danych, w której opisuje
Oskar Austegard
231

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.

albwq
źródło
20
Zapomniałeś wspomnieć o ich użyciu ze słownikami :) Możesz wycisnąć pełny słownik do filtru kwitnienia o wielkości około 512 tys., Jak tablica skrótów bez wartości
Chris S
8
Google przytacza użycie filtrów Bloom w implementacji BigTable.
Brian Gianforcementaro
16
@FreshCode W rzeczywistości pozwala ci tanio przetestować brak elementu w zestawie, ponieważ możesz uzyskać fałszywie dodatnie, ale nigdy fałszywe negatywy
Tom Savage
26
@FreshCode Jak powiedział @Tom Savage, jest to bardziej przydatne podczas sprawdzania negatywów. Na przykład możesz użyć go jako szybkiego i małego (pod względem zużycia pamięci) modułu sprawdzania pisowni. Dodaj do niego wszystkie słowa, a następnie spróbuj wyszukać słowa wpisane przez użytkownika. Jeśli otrzymasz negatyw, oznacza to, że jest źle napisany. Następnie możesz uruchomić droższy czek, aby znaleźć najbliższe dopasowania i zaoferować poprawki.
lacop
5
@ abhin4v: Filtry Bloom są często używane, gdy większość żądań prawdopodobnie zwróci odpowiedź „nie” (jak w tym przypadku), co oznacza, że ​​niewielką liczbę odpowiedzi „tak” można sprawdzić za pomocą wolniejszego testu dokładnego. Nadal powoduje to znaczne zmniejszenie średniego czasu odpowiedzi na zapytanie. Nie wiem, czy Bezpieczne przeglądanie Chrome to robi, ale tak sądzę.
j_random_hacker
140

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

Patrick
źródło
Myślałem o czymś takim na własne potrzeby. Miło wiedzieć, że zostało już zaimplementowane gdzie indziej.
Kibbee
15
W SGI STL (1998) jest implementacja
kwark
2
Nie wiedząc, jak się nazywa, napisałem niedawno coś bardzo podobnego do tego dla Javy - wydajność była doskonała: code.google.com/p/mikeralib/source/browse/trunk/Mikera/src/…
mikera
Lina jest dość rzadka: stackoverflow.com/questions/1863440/…
Czy
6
Link Mikery jest nieaktualny, oto aktualny .
aptwebapps
128

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

Simucal
źródło
+1 Qt używa list pomijania zamiast drzew RB do sortowania map i zestawów. Tak, są fajne (w każdym razie w imperatywnych językach).
Michael Ekstrand,
2
Redis wykorzystuje listy pominięć do zaimplementowania „Sorted Sets”.
antirez
Listy pomijane są prawdopodobnie moją ulubioną strukturą danych, gdy potrzebuję dobrej struktury danych i nie mam żadnych gwarancji co do kolejności danych, i chcę prostszej implementacji niż inne „zrównoważone” struktury danych. Tak dobrze.
earino
Ciekawa uwaga dodatkowa: jeśli dodasz wystarczającą liczbę poziomów do list pominięć, w zasadzie otrzymujesz B-drzewa.
Riyad Kalla,
92

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.

Yuval F.
źródło
6
Wskaźniki przestrzenne są również przydatne do symulacji ciał N z udziałem sił dalekiego zasięgu, takich jak grawitacja.
Justin Peel
87

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!

Don Stewart
źródło
2
przydaje się to tylko w programowaniu funkcjonalnym (w imperatywnych językach wystarczy wskaźnik lub indeks). Poza tym wciąż nie rozumiem, jak naprawdę działają Zamki.
Stefan Monov
4
@Stefan chodzi o to, że nie musisz teraz utrzymywać osobnego indeksu lub wskaźnika.
Don Stewart
69

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

Jonas Kölker
źródło
Drzewo wyszukiwania uporządkowane według stosu nazywa się pułapką. Jednym ze sposobów, które możesz z nimi zrobić, jest zmiana priorytetu węzła, aby przesunąć go na spód drzewa, gdzie łatwiej go usunąć.
paperhorse
1
„Drzewo wyszukiwania uporządkowane według stosu nazywa się pułapką”. - W definicji, którą słyszałem, IIRC, pułapka jest drzewem wyszukiwania uporządkowanym według stosu z losowymi priorytetami. Możesz wybrać inne priorytety, w zależności od aplikacji ...
Jonas Kölker
2
Trie sufiks jest prawie, ale nie do końca taki sam, jak znacznie chłodniejsze drzewo sufiksów , które ma ciągi znaków, a nie pojedyncze litery na krawędziach i można je budować w czasie liniowym (!). Również pomimo tego, że są asymptotycznie wolniejsze, w praktyce tablice sufiksów są często znacznie szybsze niż drzewa sufiksów dla wielu zadań ze względu na ich mniejszy rozmiar i mniejszą liczbę pośrednich wskaźników. Uwielbiam wyszukiwanie płaskiego wykresu O (1) BTW!
j_random_hacker
@j_random_hacker: Tablice sufiksów nie są asymptotycznie wolniejsze. Oto ~ 50 wierszy kodu do budowy liniowej tablicy sufiksów: cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf
Edward KMETT
1
@Edward Kmett: W rzeczywistości przeczytałem ten artykuł, to był przełom w konstrukcji tablicy przyrostków . (Chociaż już wiadomo, że konstruowanie czasu liniowego było możliwe, przechodząc „przez” drzewo sufiksów, był to pierwszy niezaprzeczalnie praktyczny algorytm „bezpośredni”.) Jednak niektóre operacje poza konstrukcją są nadal asymptotycznie wolniejsze na tablicy sufiksów, chyba że LCA stół jest również zbudowany. Można to również zrobić w O (n), ale tracąc przez to zalety rozmiaru i lokalizacji czystej tablicy sufiksów.
j_random_hacker
65

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

zebrabox
źródło
Alternatywne
wersje
Cóż, w większości przypadków zakłócacz robi lepszą pracę.
deadalnix
55

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

Dana
źródło
8
Jest to również nazywane „strukturą danych znajdowania związków”. Byłem pod wrażeniem, kiedy po raz pierwszy dowiedziałem się o tej sprytnej strukturze danych w klasie algorytmów ...
BlueRaja - Danny Pflughoeft
Rozszerzenia union-find-delete pozwalają również na usuwanie w stałym czasie.
Peaker
4
Użyłem Disjoint Set do mojego generatora lochów, aby zapewnić, że wszystkie pokoje są osiągalne przez przejścia :)
goldenratio 24.03.11
52

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.

Adam Rosenfield
źródło
Wysoki stały współczynnik, jak powiedziałeś, i trudny do wdrożenia zgodnie z przyjacielem, który musiał. Na pierwszy rzut oka nie jest tak fajnie, ale może warto wiedzieć.
p4bl0
Ci faceci zmusili ich do konkurowania w porównaniu z innymi rodzajami sterty: cphstl.dk/Presentation/SEA2010/SEA-10.pdf Istnieje powiązana struktura danych o nazwie Pairing Heaps, która jest łatwiejsza do wdrożenia i oferuje całkiem dobrą wydajność praktyczną. Jednak analiza teoretyczna jest częściowo otwarta.
Manuel
Z mojego doświadczenia ze stertami Fibonacciego dowiedziałem się, że kosztowne działanie przydziałów pamięci sprawia, że ​​jest mniej wydajne niż zwykła sterta binarna zabezpieczona tablicą.
jutky
44

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.

spoulson
źródło
... i pokrewne oktety i drzewa kd.
Lloeki,
43

Drzewa Huffmana - używane do kompresji.

Lurker Rzeczywiście
źródło
Chociaż jest interesujące, czy nie jest to rodzaj „wstępu do algorytmów”, jest to przykład typu chciwego algo?
rshepherd
38

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.

huitseeker
źródło
Spójrz na tę duplikat odpowiedzi , warto ją przeczytać!
Francois G
34

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

Cdonner
źródło
4
Ponadto, obrzydliwie, jakoś udało się opatentować (przynajmniej w przypadku wideo). ip.com/patent/USRE36801
David Eison
Po przeczytaniu linku nie sądzę, że sama struktura danych jest opatentowana, ale oparty na niej jakiś wynalazek. Zgadzam się, że jest to zdecydowanie bardzo niewykorzystana struktura danych.
Grawitacja
33

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ęść.

BlueRaja - Danny Pflughoeft
źródło
32

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

Jonas Kölker
źródło
Są ładne z teoretycznego punktu widzenia. W praktyce jednak ciężko jest uzyskać z nich konkurencyjną wydajność. Znany mi artykuł sprawił, że dobrze działały do ​​32-bitowych kluczy ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.7403 ), ale podejście nie będzie skalowane do więcej niż może 34-35 bitów lub i nie ma takiej implementacji.
Manuel
Innym powodem, dla którego są tak fajni, jest to, że są kluczowym elementem składowym szeregu algorytmów ignorowanych przez pamięć podręczną.
Edward KMETT,
29

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.

A. Levy
źródło
5
Sprawdź, czy haszowanie klasy jest szybsze.
chmike
27

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

moinudin
źródło
Trudne do wdrożenia. Nawet najlepsi programiści mogą to zrobić źle.
finnw
26

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.

btilly
źródło
Ciekawa transkrypcja z tego linku: „Kluczem jest układ van Emde Boas, nazwany na cześć struktury danych drzewa van Emde Boas opracowanej w 1977 roku przez Petera van Emde Boasa”
sergiol
23

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.

Lucas
źródło
19

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.

Edward KMETT
źródło
18
  • 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

Jasper Bekkers
źródło
18

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.

anon
źródło
Są one również powszechnie znane jako drzewa „punktów obserwacyjnych” lub drzewa vp. en.wikipedia.org/wiki/Vp-tree
Edward KMETT
17

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

kerkeslager
źródło
1
Zdecydowanie uznałbym to za strukturę danych.
Christopher Barber
Dla wszystkich zainteresowanych jest to dokładnie tak, jak modele Dokumentu (np. PlainDocument), które wspierają komponenty tekstowe Swing, są również implementowane; przed 1.2 uważam, że modele dokumentów były prostymi tablicami, które prowadzą do okropnej wydajności wstawiania dużych dokumentów; gdy tylko przenieśli się do Gap Buffers, wszystko znów było w porządku ze światem.
Riyad Kalla,
16

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.

eordano
źródło
Obawiam się, że to duplikat . Może chcesz dodać do poprzedniej odpowiedzi?
Francois G
Powiązane są również drzewa segmentów, które są przydatne do wykonywania wszelkiego rodzaju zapytań o zakres.
dhruvbird
12

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.

mpen
źródło