Niezmienna (trwała) implementacja struktury danych podobna do tablicy z szybkim indeksowaniem, dołączaniem, dodawaniem, iteracją

Szukam trwałej struktury danych podobnej do tablicy (ale niezmiennej), umożliwiającej szybkie indeksowanie, dołączanie, dodawanie i iterację (dobra lokalizacja).

Clojure zapewnia trwały Vector, ale służy tylko do szybkiego dołączania. Vector Scali ma efektywnie dołączanie i dodawanie w czasie stałym, ale nie mogę zrozumieć, jak jest zaimplementowany, ponieważ jest oparty na tej samej strukturze danych (trie wektorów mapowanych bitowo) co wektor Clojure i, jak rozumiem, trie wektorów mapowanych bitów nie mogę mieć szybkiego przygotowania bez niektórych sztuczek.

Nie jestem zainteresowany gotową implementacją, ale opisem, w jaki sposób samodzielnie wdrożyć taką strukturę danych.

Oczywistym kandydatem jest trwałe zrównoważone drzewo binarne. Wszystkie wymienione operacje można wykonać w czasie lub , używając kopiowania ścieżek . Aby uzyskać więcej informacji na temat tego, jak osiągnąć ten czas działania, zobacz książkę Chrisa Okasakiego wymienioną poniżej lub moją odpowiedź tutaj .O ( lg n $O(1)$$O(\lg n)$

Oczywiście, jako wariant, każdy liść takiego drzewa może sam zawierać niezmienną tablicę (sekwencję kolejnych wartości). To sprawia, że ​​aktualizowanie wartości jest mniej wydajne, ale może działać dobrze w twojej sytuacji, jeśli nigdy nie zamierzasz modyfikować istniejącej wartości, po prostu dołącz i wstaw. W ten sposób twój wektor jest reprezentowany jako sekwencja niezmiennych sekwencji, reprezentowanych jako zrównoważone drzewo binarne z niezmiennymi tablicami w liściach. Pozwala to na szybkie indeksowanie (logarytmiczne w liczbie liści), szybkie dołączanie i dodawanie oraz szybkie iterowanie. Najgorsza asymptotyczna złożoność nie jest lepsza, ale wydajność w praktyce może być znacznie lepsza.

Standardowym odniesieniem jest książka Chrisa Okasaki z 1998 r. „Czysto funkcjonalne struktury danych”.
Zobacz też

• Jakie klasy struktur danych można utrwalić?
• Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki?
• Jakie są nierozstrzygnięte pytania dotyczące czysto funkcjonalnych struktur danych?
• Dziesięć lat czysto funkcjonalnych struktur danych

Opisałem jedną implementację takiej struktury danych w moim artykule na temat przyrostowego dopasowywania wyrażeń regularnych - patrz http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation oraz tekst poniżej i powyżej tej sekcji .

Jest to odmiana drzewa o stałej wysokości (jak B-drzewa lub 2-3 drzewa). Zasadniczo jest to drzewo (2,3), którego liście to tablice (N, 2N-1), aby uniknąć narzutu na element. (Macierz A (N, 2N-1) to macierz, której długości mieszczą się w zakresie N..2N-1.) Większy N daje mniejsze obciążenie, ale liniowo zwiększa złożoność podziału i konkatenacji. Operacje takie jak indeksowanie, dzielenie i konkatenacja są bardzo podobne do sposobu, w jaki działają na 2-3 drzewach, generalizując do (N, 2N-1) na poziomie liścia.