Lina (struktura danych) - Rope (data structure)
W programowaniu komputerowym , a liny lub sznura , to struktura danych składa się z mniejszych strun , która służy do efektywnego przechowywania i manipulować bardzo długi łańcuch. Na przykład program do edycji tekstu może używać liny do reprezentowania edytowanego tekstu, dzięki czemu operacje takie jak wstawianie, usuwanie i dostęp losowy mogą być wykonywane wydajnie.
Opis
Lina jest drzewem binarnym, w którym każdy liść (węzeł końcowy) zawiera sznur i długość (zwaną również „ciężarem”), a każdy węzeł wyżej drzewa zawiera sumę długości wszystkich liści w lewym poddrzewie . Węzeł z dwojgiem dzieci dzieli więc cały ciąg na dwie części: lewe poddrzewo przechowuje pierwszą część ciągu, prawe poddrzewo przechowuje drugą część ciągu, a waga węzła to długość pierwszej części.
W przypadku operacji linowych zakłada się, że ciągi przechowywane w węzłach są stałymi, niezmiennymi obiektami w typowym nieniszczącym przypadku, umożliwiając pewne zachowanie przy kopiowaniu przy zapisie . Węzły liściowe są zazwyczaj realizowane jako podstawowych ciągów stałej długości z liczbą odniesienia dołączonym do dealokacji gdy nie są już potrzebne, chociaż inne zbiórki śmieci metody mogą być również stosowane.
Operacje
W poniższych definicjach N to długość liny.
Wstawić
-
Definicja::
Insert(i, S’)
wstaw ciąg S ' zaczynający się na pozycji i w ciągu s , aby utworzyć nowy ciąg C 1 ,…, C i , S' , C i + 1 ,…, C m . - Złożoność czasowa: .
Tę operację można wykonać za pomocą a Split()
i dwóch Concat()
operacji. Koszt to suma trzech.
Indeks
-
Definicja::
Index(i)
zwraca znak z pozycji i - Złożoność czasowa:
Aby pobrać i -ty znak, rozpoczynamy przeszukiwanie rekurencyjne od węzła głównego:
function index(RopeNode node, integer i)
if node.weight <= i and exists(node.right) then
return index(node.right, i - node.weight)
end
if exists(node.left) then
return index(node.left, i)
end
return node.string[i]
end
Na przykład, aby znaleźć znak na i=10
rysunku 2.1 pokazanym po prawej stronie, zacznij od węzła głównego (A), znajdź 22 jest większe niż 10 i jest lewe dziecko, więc przejdź do lewego dziecka (B). 9 to mniej niż 10, więc odejmij 9 od 10 (pozostawiając i=1
) i przejdź do prawego dziecka (D). Następnie, ponieważ 6 jest większe niż 1 i jest lewe dziecko, przejdź do lewego dziecka (G). 2 jest większe niż 1 i jest lewe dziecko, więc ponownie idź do lewego dziecka (J). Wreszcie 2 jest większe niż 1, ale nie ma lewego dziecka, więc odpowiedzią jest znak pod indeksem 1 krótkiego ciągu „na” (tj. „A”).
Concat
-
Definicja::
Concat(S1, S2)
połącz dwie liny, S 1 i S 2 , w jedną linę. - Złożoność czasowa: (lub czas na obliczenie wagi pierwiastka)
Konkatenację można przeprowadzić po prostu przez utworzenie nowego węzła głównego z lewym = S1 i prawym = S2 , co jest stałym czasem. Waga węzła macierzystego jest ustawiona na długość lewego dziecka S 1 , co zajmie trochę czasu, jeśli drzewo jest zrównoważone.
Ponieważ większość operacji linowych wymaga zrównoważonych drzew, po połączeniu drzewo może wymagać ponownego wyważenia.
Rozdzielać
-
Definicja::
Split (i, S)
podziel strunę S na dwie nowe struny S 1 i S 2 , S 1 = C 1 ,…, C i i S 2 = C i + 1 ,…, C m . - Złożoność czasowa:
Istnieją dwie sprawy, którymi należy się zająć:
- Punkt podziału znajduje się na końcu łańcucha (tj. Po ostatnim znaku węzła liścia)
- Punkt podziału znajduje się w środku struny.
Drugi przypadek sprowadza się do pierwszego, dzieląc ciąg w punkcie podziału, aby utworzyć dwa nowe węzły liści, a następnie tworząc nowy węzeł, który jest rodzicem dwóch ciągów składowych.
Na przykład, aby podzielić 22-znakową linę pokazaną na rysunku 2.3 na dwie równe składowe liny o długości 11, zapytaj dwunasty znak, aby zlokalizować węzeł K na dolnym poziomie. Usuń powiązanie między K i G . Przejdź do nadrzędnego G i odjąć wagę K od ciężaru D . Podjedź w górę drzewa i usuń wszelkie prawe linki do poddrzew obejmujących znaki poza pozycją 11, odejmując wagę K od ich węzłów nadrzędnych ( w tym przypadku tylko węzły D i A ). Wreszcie, budować nowo osieroconych węzłów K i H przez łączenie ich ze sobą i tworząc nowy nadrzędny P o masie równej długości lewego węzeł K .
Ponieważ większość operacji linowych wymaga zrównoważonych drzew, może być konieczne ponowne wyważenie drzewa po rozłupaniu.
Usunąć
-
Definicja::
Delete(i, j)
usuń podciąg C i ,…, C i + j - 1 , z s, aby utworzyć nowy ciąg C 1 ,…, C i - 1 , C i + j ,…, C m . - Złożoność czasowa: .
Ta operacja może być wykonana przez dwie Split()
i jedną Concat()
operację. Najpierw podziel linę na trzy, podzielone odpowiednio przez i -ty i i + j -ty znak, co spowoduje wyodrębnienie łańcucha do usunięcia w oddzielnym węźle. Następnie połącz pozostałe dwa węzły.
Raport
-
Definicja::
Report(i, j)
wypisz łańcuch C i ,…, C i + j - 1 . - Złożoność czasowa:
Aby zgłosić ciąg C i ,…, C i + j - 1 , znajdź węzeł u zawierający C i i weight(u) >= j
, a następnie przejdź przez T, zaczynając od węzła u . Wyjście C i , ..., C i + j - 1 , wykonując takie przechodzenie na zamówienie z T zaczynając od węzła u .
Porównanie z tablicami monolitycznymi
Operacja | Lina | Strunowy |
---|---|---|
Indeks | O (log n) | O (1) |
Rozdzielać | O (log n) | O (1) |
Concatenate (destrukcyjne) | O (log n) bez ponownego równoważenia / O (n) najgorszy przypadek | Na) |
Concatenate (nieniszczące) | Na) | Na) |
Powtarzaj po każdym znaku | Na) | Na) |
Wstawić | O (log n) bez ponownego równoważenia / O (n) najgorszy przypadek | Na) |
Dodać | O (log n) bez ponownego równoważenia / O (n) najgorszy przypadek | O (1) amortyzowane, O (n) najgorszy przypadek |
Usunąć | O (log n) | Na) |
Raport | O (j + log n) | O (j) |
Budować | Na) | Na) |
Zalety:
- Liny umożliwiają znacznie szybsze wstawianie i usuwanie tekstu niż monolityczne tablice ciągów, na których operacje mają złożoność czasową O (n).
- Liny nie wymagają O (n) dodatkowej pamięci, gdy są obsługiwane (tablice potrzebują tego do operacji kopiowania).
- Liny nie wymagają dużych, ciągłych przestrzeni pamięci.
- Jeśli używane są tylko nieniszczące wersje operacji, lina jest trwałą strukturą danych . W przypadku przykładu programu do edycji tekstu prowadzi to do łatwej obsługi wielu poziomów cofania .
Niedogodności:
- Większe całkowite wykorzystanie przestrzeni, gdy nie jest używany, głównie do przechowywania węzłów nadrzędnych. Istnieje kompromis między tym, jaka część całkowitej pamięci stanowi taki narzut, a tym, jak długo fragmenty danych są przetwarzane jako ciągi. Ciągi znaków na przykładowych rysunkach powyżej są nierealistycznie krótkie dla nowoczesnych architektur. Narzut jest zawsze O (n), ale stała może być dowolnie mała.
- Wydłużenie czasu potrzebnego na zarządzanie dodatkową przestrzenią dyskową
- Zwiększona złożoność kodu źródłowego; większe ryzyko błędów
Ta tabela porównuje cechy algorytmiczne implementacji sznurka i liny, a nie ich surową prędkość . Ciągi oparte na tablicach mają mniejszy narzut, więc (na przykład) operacje łączenia i dzielenia są szybsze w przypadku małych zestawów danych. Jednak gdy ciągi oparte na tablicach są używane dla dłuższych ciągów, złożoność czasowa i użycie pamięci do wstawiania i usuwania znaków stają się niedopuszczalnie duże. W przeciwieństwie do tego struktura danych liny ma stabilną wydajność niezależnie od rozmiaru danych. Ponadto złożoność przestrzeni dla lin i tablic wynosi O (n). Podsumowując, liny są preferowane, gdy dane są obszerne i często modyfikowane.
Zobacz też
- Środowisko programistyczne Cedar , które wykorzystywało liny „prawie od samego początku”
- Model T amfilada , podobną strukturę danych z początku 1970 roku.
- Bufor luk , struktura danych powszechnie używana w edytorach tekstu, która umożliwia wydajne operacje wstawiania i usuwania skupione w pobliżu tej samej lokalizacji
- Tabela elementów , kolejna struktura danych powszechnie używana w edytorach tekstu
Bibliografia
Linki zewnętrzne
- Wdrożenie linek „Cords” w bibliotece Boehm Garbage Collector
- Specyfikacja SGI C ++ dla lin (obsługiwana przez STLPort i libstdc ++ )
- Liny dla C #
- liny do Common Lisp
- Liny dla Javy
- Linki do JavaScript
- Liny do Limbo
- liny dla Nim
- Liny do OCaml
- piropy dla Pythona
- Liny do Smalltalk
- SwiftRope dla Swift
- „Ropey” dla Rusta