Ładowanie struktury palca

Po dłuższej pracy z 2-3 palcami jestem pod wrażeniem ich szybkości w większości operacji. Jednak jedynym problemem, na jaki natknąłem się, jest duży koszt związany z początkowym utworzeniem dużego drzewa palców. Ponieważ budowanie jest definiowane jako sekwencja operacji konkatenacji, kończy się budowanie dużej liczby niepotrzebnych struktur drzewa palcowego.

Ze względu na złożoną naturę 2-3 palców nie widzę intuicyjnej metody ich ładowania, a wszystkie moje wyszukiwania są puste. Pytanie brzmi: jak możesz zacząć ładować drzewo 2-3 palców przy minimalnym obciążeniu?

Mówiąc wprost: biorąc pod uwagę sekwencję o znanej długości wygeneruj reprezentację drzewa palca przy minimalnej liczbie operacji.$S$$n$$S$

Naiwnym sposobem na osiągnięcie tego jest kolejne wywołanie operacji przeciw (w literaturze operator „ ”). Jednak stworzy to odrębnych struktur drzewek palca reprezentujących wszystkie wycinki dla .$\triangleleft$$n$$S$$[1..i]$

GHC użytkownika Data.Sequencejest replicatefunkcja buduje fingertree w czas i przestrzeń, ale możliwe jest to dzięki znajomości elementów, które go na prawej stronie kręgosłupa drzewa palec z get-go. Ta biblioteka została napisana przez autorów oryginalnego artykułu na 2-3 palcach.$O(\lg n)$

Jeśli chcesz zbudować drzewo palców poprzez wielokrotne łączenie, możesz być w stanie zmniejszyć przejściowe użycie przestrzeni podczas budowania, zmieniając reprezentację grzbietów. Kolce na 2-3 palcach są sprytnie przechowywane jako zsynchronizowane pojedynczo połączone listy. Jeśli zamiast tego przechowujesz kolce jako deques, może być możliwe zaoszczędzenie miejsca podczas łączenia drzew. Chodzi o to, że łączenie dwóch drzew tej samej wysokości zajmuje przestrzeń poprzez ponowne użycie kolców drzew. Podczas łączenia 2-3 drzew palcowych, jak pierwotnie opisano, kolce wewnętrzne nowego drzewa nie mogą być używane jako takie.$O(1)$

„Czysto funkcjonalne reprezentacje sortowanych list Catenable” Kaplana i Tarjana opisują bardziej skomplikowaną strukturę palca. Ten artykuł (w rozdziale 4) omawia również konstrukcję podobną do sugestii deque, którą przedstawiłem powyżej. Wierzę, że struktura, którą opisują, może łączyć dwa drzewa o równej wysokości w czasie i przestrzeni . Czy w przypadku budowania palców jest to dla ciebie wystarczająco dużo miejsca?$O(1)$

Uwaga: użycie słowa „bootstrapping” oznacza coś innego niż użycie powyższego. Oznacza to przechowywanie części struktury danych przy użyciu prostszej wersji tej samej struktury.

Riffując doskonałą odpowiedź jbapple na temat replicate, ale zamiast tego używając replicateA(który replicatejest wbudowany), wymyśliłem:

--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) <- get
            put ys
            return y

myFromList(w nieco bardziej wydajnej wersji) jest już zdefiniowany i stosowany wewnętrznie w Data.Sequencekonstruowania drzewa palców, które są wyniki rodzaju.

Ogólnie intuicja dotycząca replicateAjest prosta. replicateAjest zbudowany na funkcji aplikacji drzewko aplikacyjne . applicativeTreebierze kawałek drzewa wielkości mi tworzy dobrze zrównoważone drzewo zawierające jego nkopie. Obudowy dla nmaksymalnie 8 (jednego Deeppalca) są na stałe zakodowane. Wszystko powyżej tego, a rekursywnie się przywołuje. Element „aplikacyjny” polega po prostu na tym, że przeplata on konstrukcję drzewa z efektami gwintowania, takimi jak w przypadku powyższego kodu, stan.

goFunkcji, które są replikowane, jest po prostu działaniem, które dostaje aktualny stan, element pojawia się na górze, a zastępuje resztę. Przy każdym wywołaniu przesuwa się ona w dół listy podanej jako dane wejściowe.

Kilka bardziej konkretnych notatek

main = print (length (show (Seq.fromList [1..10000000::Int])))

W niektórych prostych testach przyniosło to interesujący kompromis w zakresie wydajności. Główna funkcja powyżej działała prawie o 1/3 niżej z myFromList niż z fromList. Z drugiej strony myFromListużywano stałej sterty 2 MB, podczas gdy standard fromListzużywał do 926 MB. To 926 MB wynika z konieczności jednoczesnego przechowywania całej listy w pamięci. Tymczasem rozwiązanie myFromListjest w stanie leniwie korzystać ze struktury. Problem prędkości wynika z faktu, że myFromListmusi wykonać około dwa razy więcej przydziałów (w wyniku budowy pary / zniszczenia monady państwowej) niżfromList. Możemy wyeliminować te przydziały, przechodząc do monady stanu przekształconej przez CPS, ale skutkuje to utrzymaniem o wiele większej pamięci w danym momencie, ponieważ utrata lenistwa wymaga przemierzania listy w sposób nieprzesyłający.

Z drugiej strony, zamiast wymuszać całą sekwencję pokazu, przechodzę do wyodrębnienia głowy lub ostatniego elementu, myFromListnatychmiast przynosi większą wygraną - wyodrębnienie elementu głowy jest niemal natychmiastowe, a wyodrębnienie ostatniego elementu wynosi 0,8 s . Tymczasem przy standardzie fromListwyjęcie głowy lub ostatniego elementu kosztuje ~ 2,3 sekundy.

To są wszystkie szczegóły i są konsekwencją czystości i lenistwa. W sytuacji mutacji i losowego dostępu wyobrażam sobie, że replicaterozwiązanie jest zdecydowanie lepsze.

Rodzi to jednak pytanie, czy istnieje sposób na przepisanie applicativeTree, który myFromListjest zdecydowanie bardziej wydajny. Wydaje mi się, że problem polega na tym, że działania aplikacyjne są wykonywane w innej kolejności niż drzewo jest naturalnie przechodzone, ale nie w pełni pracowałem nad tym, jak to działa lub czy istnieje sposób, aby to rozwiązać.

Kiedy skończysz z dużą liczbą pośrednich struktur palców, dzielą one ze sobą zdecydowaną większość swoich struktur. Ostatecznie przydzielasz maksymalnie dwa razy więcej pamięci niż w przypadku idealizowanym, a resztę zwalnia pierwsza kolekcja. Asymptotyki tego są tak dobre, jak tylko mogą, ponieważ na końcu potrzebujesz palca wypełnionego wartościami n.

Możesz zbudować zestaw palców za pomocą Data.FingerTree.replicatei za pomocą, FingerTree.fmapWithPosaby wyszukać twoje wartości w tablicy, która odgrywa rolę twojej skończonej sekwencji, lub używając, traverseWithPosaby oderwać je z listy lub innego pojemnika o znanej wielkości.

$O(\log n)$$O(n)$$O(\log n)$

$O(\log n)$replicateAmapAccumL

TL; DR Gdybym musiał to zrobić, prawdopodobnie użyłbym:

rep :: (Int -> a) -> Int -> Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 

oraz indeksu do ustalonej wielkości tablicy chcę tylko dostarczyć (arr !)do fgóry.