Implementacja tabeli trwałej mieszania

Question

W programie, nad którym pracuję, tworzę duże "drzewo wątków" (najwyżej k dzieci na węzeł), gdzie każdy wątek wprowadza pewne modyfikacje do tabeli mieszania odziedziczonej po rodzicu. Czy istnieje sposób na zaimplementowanie tabeli mieszania, która jest nieco "trwała" (w rozumieniu http://en.wikipedia.org/wiki/Persistent_data_structure)?

Czy istnieje sposób na wprowadzenie pary klucz-wartość z wyszukiwaniem, wstawieniem i usunięciem co najmniej O (log n), która jest w pełni trwała, ale jest "efektywna pod względem przestrzeni" (najgorszy przypadek) jak zwykły stolik do mieszania?

Answer 1

"Jako oszczędność miejsca jako zwykły stolik do mieszania" jest dość ogólnikową specyfikacją, ponieważ "zwykła" może oznaczać powiązanie lub sondowanie w zależności od tego, kogo pytasz. Nie sądzę, aby ktokolwiek zaprojektował łatwe do zrozumienia, trwałe tablice skrótów.

Najprostszym sposobem uzyskania trwałej mapy klucz-wartość o złożonej strukturze jest użycie stałego drzewa wyszukiwania binarnego. Lookup jest znanym algorytmem z efemerycznych (nietrwałych) BST. Włóż zmiany jednak i staje się mniej więcej tak (pseudo-Java):

// overwrites the value for k if it's already in the tree 
Node insert(Node node, Key k, Value v) 
{ 
    if (k < node.key) 
     return new Node(node.key, node.val, insert(node.left, k, v), node.right); 
    else if (k > node.key) 
     return new Node(node.key, node.val, node.left, insert(node.right, k, v)); 
    else 
     return new Node(k, v, node.left, node.right); 
} 

Należy pamiętać, że rutynowe wkładka wraca nowe drzewo, które może wydawać się nieskuteczne, ale zmienia tylko te węzły przemierza. Jest to średnio O (lg n), więc przydziela średnio O (lg n). Dotyczy to tak wydajnej przestrzeni, jak to tylko możliwe.

Aby uzyskać najgorszy możliwy scenariusz O (lg n), użyj drzewa czerwono-czarnego. Zobacz także literaturę dotyczącą struktur danych w programowaniu funkcjonalnym, np. dzieła Okasaki.

Answer 2

Firma Clojure wdrożyła cały zestaw trwałych struktur danych, takich jak mapy skrótów. Jest open source, więc może powinieneś rzucić okiem?

http://clojure.org/data_structures

http://code.google.com/p/clojure/source/browse/trunk/src/jvm/clojure/lang/PersistentHashMap.java

Answer 3

Mianowicie, istnieje sposób zaimplementować wartości kluczy parowanie co najmniej O (log n) odnośnika, insercji i delecji, która jest całkowicie trwały, ale jako "efektywny pod względem przestrzeni" (najgorszy przypadek) jako zwykły stolik do mieszania?

Tak. Sekcja 5 Driscoll et al.'s "Making Data Structures Persistent" przedstawia technikę uzyskiwania w pełni stałych czerwono-czarnych drzew o czasie O (lg n) i O (1) złożoności wstawiania, usuwania i wyszukiwania.

Ich struktura danych nie jest spójna i trwała. Aby uzyskać więcej informacji o trwałości, zobacz Kaplan's survey on the topic.

Answer 4

Czy próbowałeś już lub sprawdziłeś źródło jdbm2? http://code.google.com/p/jdbm2/

Answer 5

Czy istnieje sposób, aby wdrożyć klucz-wartość sparowanie z co najmniej O (log n) odnośnika, insercji i delecji, która jest w pełni trwałe, ale jest jako „przestrzeń efektywny” (najgorszy przypadek) jako zwykły stolik do mieszania?

Rzeczywiście istnieje. Wiele sposobów.

E.g.Haskell, prosty Data.Map, a wielkości symetrycznych drzewo binarne (lub drzew równowagi ograniczonej), jak opisano przez:

• Stephen Adams "Wydajne zestawy: balansowaniu", Journal of programowanie funkcji 3 (4): 553-562, październik 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
• J. Nievergelt i EM Reingold "binarne drzewo poszukiwań z ograniczonym równowagi", SIAM Journal informatyki 2 (1), marzec 1973.

udostępnia następujące API, spełniających kryteria:

insert :: Ord k => k -> a -> Map k a -> Map k a -- O(log n) 
lookup :: Ord k => k -> Map k a -> Maybe a  -- O(log n) 
delete :: Ord k => k -> Map k a -> Map k a  -- O(log n) 

będąc w pełni odpornym. Wykorzystanie przestrzeni to O (n).

Dla lepszych stałych czynników, spróbuj np. struktury danych o tej samej ogólnej złożoności.

konstrukcje alternatywne obejmują:

• uporczywych próbach, które lepsze wykorzystanie przestrzeni nad hashtables, jako klucz pamięci jest gęsta.