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


11

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.

Odpowiedzi:


13

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(lgn)

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ż


Dziękuję Ci. Wygląda na to, że drzewa RRB są dobrym kandydatem i mają już (nie pełną) implementację Clojure.
Tvaroh

Chyba Okasaki mówi nam, jak osiągnąć te środowiska wykonawcze w niezmienności i wytrwałości?
Raphael

1
@Raphael, tak. Dodałem odniesienia, aby wyjaśnić, w jaki sposób osiągasz środowisko uruchomieniowe (na początku mojej odpowiedzi).
DW

4

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.


Zerwane linki; proszę podać odpowiednie, solidne odniesienie (które pozwala ludziom znaleźć twój artykuł bez linku).
Raphael

Nie opublikowałem tego artykułu w żadnym czasopiśmie, tylko na mojej osobistej stronie internetowej. Powinien to jednak umieścić na Arxivie, dobry pomysł.
jkff

Głównie myślałem o autorach, tytule i roku - dzięki temu Googling jest łatwiejszy, jeśli zajdzie taka potrzeba. Umieszczenie go w arXiv byłoby jeszcze lepsze, prawda!
Raphael
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.