Деструктивне оновлення

У комп'ютерних системах стійка структура даних являє собою структуру даних, яка завжди зберігає попередню версію сама, коли її змінюють. Такі структури даних є фактично незмінними, оскільки їхні операції не оновлюють структуру на місці, але замість цього завжди дають нову оновлену структуру.

Структура даних є частково стійкою , якщо є доступ до всіх версій, але можна змінити лише нову версію. Структура даних є повністю стійкою, якщо кожна версія може бути доступною та модифікованою. Якщо є також операція meld або merge, яка може створити нову версію з двох попередніх версій, структура даних називається confluent persistent. Структури, які не є стійкими, називаються ефемерними.

Ці типи структур даних особливо поширені в логічному і функціональному програмуванні, а в чисто функціональному програмуванні всі дані незмінні, тому всі структури даних автоматично повністю стійкі. Постійні структури даних також можуть бути створені за допомогою внутрішнього оновлення даних, і вони загалом можуть використовувати менший проміжок часу або місця для зберігання, ніж їх суто функціональні аналоги. Чисто функціональна структура даних - це стійкі структури даних, які повністю уникають використання змінного стану, але часто можуть досягти привабливих амортизованих меж ускладненості часу.

У той час як персистенція може бути досягнута шляхом простого копіювання, це неефективно для використання процесора та оперативної пам'яті, оскільки більшість операцій роблять лише невеликі зміни у структурі даних. Кращим методом є використання схожості між новими та старими версіями для спільного використання структури між ними, наприклад, використання того самого піддерева у ряді структури дерева s. Однак, оскільки швидко стає нездійсненним визначити, скільки попередніх версій поділяють ті частини структури, і тому, що часто бажано відкинути старі версії, це вимагає середовища з garbage collection. Проте не "так" нездійсненно, що складний проект, наприклад файлова система ZFS copy-on-write, не може це досягти шляхом прямого відстеження розподілу пам'яті.

Частково стійкі ред.

У моделі часткової наполегливості ми можемо запитати будь-яку попередню версію структури даних, але ми можемо оновити лише останню версію. Це означає лінійний пошук серед версій. Три способи в пошуку в двійковому дереві:

Товстий вузол ред.

Метод жирного вузла полягає в тому, щоб записати всі зміни, внесені в поля вузлів у самих вузлах, не видаляючи старі значення полів. Це вимагає того, щоб ми дозволяли вузлам ставати довільно "жирними". Іншими словами, кожен жировий вузол містить ту ж інформацію та поля вказівника як ефемерний вузол разом із пробілом для довільної кількості додаткових значень поля. Кожне додаткове значення поля має пов'язане ім'я поля та марку версії, яка вказує версію, в якій назване поле було змінено, щоб мати вказане значення. Крім того, кожний жирний вузол має власну марку версії, що вказує версію, в якій був створений вузол. Єдиною метою вузлів з марками версій є переконання, що кожен вузол містить лише одне значення для імені поля для кожної версії. Для переміщення по структурі кожне початкове значення поля у вузлі має маркер версії нуля.

Складність жирового вузла ред.

За допомогою методу жирних вузлів для кожної модифікації потрібен O (1) простір: просто зберігайте нові дані. Кожна модифікація займає O (1) додатковий час для збереження модифікації в кінці історії змін. Це пов'язано з амортизованим часом, припускаючи, що ми зберігаємо історію модифікацій у масивах. Для часу доступу, ми повинні знайти правильну версію на кожному вузлі, коли ми перетинаємо структуру. Якщо ми зробили модифікації m, то кожна операція доступу зумовлює уповільнення O (log m) внаслідок вартості пошуку найближчої модифікації в масиві.

Копіювання шляху ред.

Копія шляху - це зробити копію всіх вузлів на шляху, який містить вузол, який ми збираємось вставити або видалити. Тоді ми повинні каскад змінити назад через структуру даних: всі вузли, які вказали на старий вузол, повинні бути змінені, щоб вказувати на новий вузол. Ці модифікації викликають більше каскадних змін і тощо. Поки ми не дійдемо до кореня. Ми підтримуємо масив коренів, індексованих відміткою часу. Структура даних, вказана корінням часу t, є точною структурою даних часу t.

Складність копіювання шляху ред.

З модифікаціями m, це коштує O (log m) адитивного пошуку та часу. Час і простір модифікації обмежуються розмірами структури, оскільки одна модифікація може призвести до копіювання всієї структури. Тобто O (m) для одного оновлення, і, отже, до часу обробки O (n²).

Комбінація ред.

Daniel Sleator, Robert Tarian та ін. придумав спосіб об'єднати переваги жирних вузлів та копіювання шляху, отримати O (1) прискорення доступу та просторову та часові модифікації O (1).

У кожному вузлі ми зберігаємо одну коробку модифікацій. У цьому вікні можна зберегти одну зміну вузла - або зміну одного з покажчиків, або ключ до вузла, або інший фрагмент специфічних для вузла даних, а також мітку часу, коли ця модифікація була застосована. Спочатку вікно модифікації кожного вузла порожнє.

Кожного разу, коли ми отримуємо доступ до вузла, ми перевіряємо вікно модифікації та порівнюємо його часовий покажчик із часом доступу. (Час доступу визначає версію структури даних, яка нам цікавить.) Якщо вікно модифікації порожнє або час доступу до моменту часу, то ми ігноруємо вікно модифікації і просто займаємося нормальною частиною вузла . З іншого боку, якщо час доступу є після модифікаційного часу, ми використовуємо значення у вікні модифікації, переоцінюючи це значення в вузлі. (Скажіть, що вікно модифікації містить новий ліва вказівник. Тоді ми будемо використовувати його замість звичайного лівого курсора, але ми будемо використовувати звичайний праве покажчик.)

Змінення вузла працює так. (Ми припускаємо, що кожна модифікація торкається одного покажчика або аналогічного поля.) Якщо поле модифікації вузла порожнє, ми заповнимо його модифікацією. В іншому випадку вікно модифікації буде заповнено. Ми робимо копію вузла, але використовуємо лише останні значення (тобто ми перезаписуємо один з полів вузла з значенням, яке було збережено у вікні модифікації). Тоді ми виконуємо модифікацію безпосередньо на новому вузлі, без використовуючи вікно модифікації. (Ми перезаписуємо один з полів нового вузла, а його вікно модифікацій залишається пустим.) Нарешті, ми скопіювали цю зміну до батьківського вузла, як і копіювання шляху. (Це може полягати у заповненні вікна модифікації батьків або рекурсивно копіювання батьків. Якщо вузол не має батьків, це root - ми додаємо новий корінь до сортування коренів.)

За допомогою цього алгоритму, заданого в будь-який час t, у структурі даних існує не більше одного модифікаційного поля з часом t. Таким чином, модифікація в момент часу t розбиває дерево на три частини: одна частина містить дані з до часу t, одна частина містить дані з часу t, і одна частина не вплинула на модифікацію.

Складність комбінації ред.

Час і місце для модифікацій вимагають амортизованого аналізу. Модифікація займає А (1) амортизоване простір, а О (1) амортизується час. Щоб зрозуміти, чому, використовуйте потенційну функцію φ, де φ (T) - це число повних живих вузлів у T. Живі вузли T - це лише вузли, доступні з поточного кореня в поточному часі (тобто після останньої модифікації). Повні живі вузли - це живі вузли, вікна яких є повними.

Кожна модифікація включає в себе декілька копій, скажімо k, а потім 1 зміна вікна модифікації. (Ну, не зовсім, можна додати новий корінь, але це не змінює аргумент.) Розглянемо кожен з копій. Кожен коштує O (1) простір і час, але зменшує потенційну функцію на одиницю. (По-перше, копіюваний вузол повинен бути повним і жити, тому він сприяє потенційній функції.Половуюча функція буде тільки падати, однак, якщо старий вузол недоступний у новому дереві, але ми знаємо, що це не доступний у новому дереві, наступним кроком у алгоритмі буде зміна батьківського вузла на точку на копії.Нарешті, ми знаємо, що вікно модифікації копії порожнє.Тому ми замінили повний живий вузол з порожнім живим вузол і φ знижується на одиницю.) Остання стадія заповнює вікно модифікації, яке коштує O (1) часу і збільшує φ на одиницю.

Встановлюючи все разом, зміна φ становить Δφ = 1- k. Отже, ми сплатили простір O (k + Δφ) = O (1) і O (k + Δφ +1) = O (1) час

Повністю стійкий ред.

У повністю стійкій моделі, обидві версії та запити дозволяються в будь-якій версії структури даних.

Дуже стійка ред.

У конфлуктно стійкій моделі ми використовуємо комбінатори для об'єднання введення більш ніж однієї попередньої версії для випуску нової окремої версії. Замість дерева розгалуження комбінації версій викликають структуру DAG (спрямований ациклічний графік) на графіку версії.

Приклади постійних структур даних ред.

Можливо, найпростішою перманентною структурою даних є список list або cons - список, який складається з простих списків об'єктів, кожна з яких містить посилання до наступної у списку. Це стійка, оскільки ми можемо взяти "хвіст" списку, що означає останні "k" елементи для деяких "k", а також додати нові вузли до його передньої частини. Хвіст не буде дублюватися, замість того, щоб стати поділеним як зі старим, так і з новим списком. Поки вміст хвоста незмінний, це поділ буде невидимим для програми.

Багато поширених стандартних структур даних, таких як червоно-чорне дерево, можна легко пристосувати для створення стійкої версії. Деякі інші потребують трохи більше зусиль, наприклад: черги, і розширення.

Також існують стійкі структури даних, які використовують руйнівні операції ^{[прояснити]}, що робить їх неможливим ефективно реалізовуватись на чисто функціональних мовах (наприклад, Haskell за межами спеціалізованих монад, як штат або IO), але можливо в таких мовах, як C або Java Ці типи структур даних часто можна уникати з іншим дизайном. Одним з основних переваг використання суто стійких структур даних є те, що вони часто поводяться краще в багатопотокових середовищах.

Література ред.

Додаткове читання ред.

Persistent Data Structures and Managed References [Архівовано 10 лютого 2015 у Wayback Machine.] - video presentation by Rich Hickey on Clojure's use of persistent data structures and how they support concurrency
Making Data Structures Persistent [Архівовано 4 грудня 2017 у Wayback Machine.] by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan
Fully persistent arrays for efficient incremental updates and voluminous reads [Архівовано 8 жовтня 2012 у Wayback Machine.]
Real-Time Deques, Multihead Turing Machines, and Purely Functional Programming [Архівовано 8 жовтня 2012 у Wayback Machine.]
Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4.
Purely Functional Data Structures [Архівовано 1 червня 2018 у Wayback Machine.] thesis by Chris Okasaki (PDF format)
Fully Persistent Lists with Catenation [Архівовано 9 серпня 2017 у Wayback Machine.] by James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
Persistent Data Structures [Архівовано 29 серпня 2017 у Wayback Machine.] from MIT open course Advanced Algorithms [Архівовано 28 липня 2017 у Wayback Machine.]

Зовнішнє посилання ред.

Lightweight Java implementation of Persistent Red-Black Trees [Архівовано 12 січня 2019 у Wayback Machine.]
Efficient persistent structures in C# [Архівовано 21 грудня 2017 у Wayback Machine.]