Руссін О. С. ПЕРСИСТЕНТНІ СТРУКТУРИ ДАНИХ

УДК: 004.053

 

ПЕРСИСТЕНТНІ СТРУКТУРИ ДАНИХ

Руссін О. С.

Національний технічний університет України «Київський політехнічний інститут», Україна, Київ

 

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

Ключові слова: Персистентність, структура даних, персистентний стек, персистентне дерево, оптимізація персистентності, персистентна черга.

 

Руссин А. С. Персистентные структуры данных / Национальный технический университет Украины «Киевский политехнический институт», Украина, Киев

Персистентные структуры - такие структуры, при всякой их изменении сохраняют доступ ко всем предыдущих версий этой структуры, способность состояния существовать дольше, чем процесс, который создал его. Одним из возможных решений является полное копирование всей структуры при каждой смене. Это чрезвычайно ресурсоемким процедура как по памяти, так и по времени работы. Этот способ можно применять на стадии тестирования более сложной организации структуры, но для работы в готовом проекте он непригоден. Важно более поиск и разработка более производительных решений, оптимальных реализаций для различных структур.

Ключевые слова: Персистентность, структура данных, персистентный стек, персистентный дерево, оптимизация персистентности, персистентная очередь.

 

Russin A. S. Persistent data structures / National Technical University of Ukraine "Kyiv Polytechnic Institute", Ukraine, Kyiv

Persistent patterns - such structures at every change they retain access to all previous versions of this structure, the ability of the state to exist longer than the process that created it. One possible solution is a complete copy of the entire structure at each change. This is a very intensive procedure both in memory and on time work. This method can be used at the stage of testing a complex organization structure, but to work in the finished project, it is not suitable. More important is the search and development of more productive solutions, optimal implementations for different structures.

Key words: Persistence, data structure, persistent stack, persistent tree optimization persistent, persistent queue.

 

Вступ. Структури даних можна розділити на дві групи: ефемерні і персистентні. Ефемерними називаються структури даних, що зберігають тільки останню свою версію. Персистентні структури, тобто ті, які зберігають всі свої попередні версії, в свою чергу можна розділити ще на дві підгрупи: якщо структура даних, дозволяє змінювати тільки останню версію, вона називається частково персистентной (partially persistent), якщо ж дозволяється змінювати будь-яку версію, така структура вважається повністю персистентной (fully persistent).

Постановка задачі

Реалізовувати ми будемо, так звану повну персистентність - це означає, що проміжні версії доступні не тільки в режимі read-only, а і є можливість в будь-який момент часу додавати і витягувати з них елементи. Крім того, нам, звичайно, хотілося б мати таку ж асимптотику часу роботи і додаткової пам'яті, як і для неперсистентного варіанту, а саме O (n), де n - сумарна кількість операцій, що здійснюються з нашою чергою. До слова, якщо послабити вимоги до O (n log n), то черга емулюється за допомогою персистентного декартового дерева по неявному ключу. [1]

Простий інтерфейс роботи з нашою структурою даних: вихідні запити версії черг будемо нумерувати цілими невід'ємними числами. Спочатку є лише порожня черга під номером 0. Нехай у нас є N версій черг (включаючи вихідну порожню), тоді вони пронумеровані числами від 0 до N-1 і ми можемо виконати наступні чотири запити:

1. empty (query_id) – перевіряє чи порожня черга з заданим номером;

2. front (query_id) - повертає перший елемент черги, сама ж черга при цьому ніяк не змінюється і ніяких нових черг не створюється. Операція допустима, якщо черга не порожня;

3. push (query_id, new_element) - створює нову чергу під номером N, яка утворюється дописуванням в кінець до вихідної нового елемента. Стара версія при цьому як і раніше доступна під номером query_id;

4. pop (query_id) - створює нову чергу під номером N, яка утворюється витягом з вихідною першого елемента. Вихідна черга все також доступна під старим номером. У випадку, якщо вихідна черга була порожня, нова також буде порожньою.

Імітація черги за допомогою стеків

Як відомо, персистентний стек - проста структура даних з необхідною нам асимптотикою.[1] Крім того чергу можна імітувати за допомогою двох стеків. Теоретично можна зробити ці два стеки персистентними для вирішення задачі. Але при даній імітації у нас не всяка операція має асимптотику O(1): якщо при pop'е стек, з якого ми дістаємо елементи, виявляється порожнім, то ми перекладаємо в нього всі елементи з іншого стека. У випадку зі звичайним чергою кожен елемент перекладається тільки один раз, тому сумарна асимптотика залишається O(n), але в персистентному випадку кожен елемент може належати багатьом чергам і відповідно бути перекладений кілька разів. [2]

Нехай, наприклад, q - номер черги, у якої цей стек порожній, тоді після push (q, 1) і push (q, 2) у отриманих черг цей стек залишиться порожнім і при pop'е з них кожен елемент черги q буде перекладений по два рази. Організувати ж яке-небудь спільне використання перекладених елементів неможливо в силу того, що самі нижні елементи у отриманих перекладанням стеків будуть різні (1 і 2 соотвественно), а персистентний стек влаштований таким чином, що кожен елемент зберігає покажчик на елемент, що лежить нижче нього, тому в будь-якому випадку ми будемо змушені мати 2 копії передостаннього елемента, які вказуватимуть на відповідний останній, а значить і 2 копії передостаннього, щоб вказувати на потрібний передостанній і так далі по ланцюжку.

Проте існує алгоритм, заснований на такій ідеї (імітації черги за допомогою двох стеків), який гарантує що стек, з якого ми дістаємо при pop, ніколи не виявиться порожнім і використовує для забезпечення цього 6 стеків. Представлений алгоритм цю ідею в явному вигляді не використовує, хоча можна знайти загальні моменти[3].

Опис алгоритму

Спробуємо використовувати ту ж структуру, що і при реалізації персистентного стека: будемо зберігати додані елементи у вигляді дерева (точніше кажучи, набору дерев - ліси), в кожній вершині лежатиме доданий елемент і покажчик на попередній йому в черзі (точніше, на відповідну цьому попередньому елементу вершину дерева). Говорячи надалі елемент черги, я часто буду мати на увазі саме відповідну елементу вершину.

Непорожня черга в такому випадку може бути представлена парою покажчиків на перший і останній елемент черги, причому вершина, відповідна першому елементу, обов'язково буде предком вершини, відповідної останньому (ну або збігатися з нею у випадку черги з одного елемента). [4]

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

Наша єдина проблема при такому підході - це реалізація операції pop (інші три - тривіальні), незрозуміло, як визначити на яку вершину зрушити покажчик на перший елемент, адже для вершини ми зберігаємо лише покажчик на батька, але не на синів (яких у однієї вершини може бути кілька штук, і, навіть якщо їх всі зберігати, зовсім незрозуміло, який з них відповідає наступному елементу нашої черги). Тому для кожної черги, в якій більше двох елементів, будемо додатково зберігати покажчик на елемент деякого однозв'язного списку, такого, що елемент списку на наш вказівник містить покажчик на другий елемент нашої черги, а елементи, що лежать нижче його за списком, покажчики на третій, четвертий і так далі відповідно. Маючи такий покажчик для вихідної черги, при виконанні pop можна просто визначити нову голову черги, а покажчик на такий елемент списку для отриманої черзі - це просто покажчик на наступний елемент в даному списку.[5]

Однак, з причин, аналогічним тим, за якими емуляція черги двома стеками не працює, домогтися того, щоб для кожної черги нижче за списком лежали абсолютно всі її проміжні вершини, у нас не вийде, тому в ньому будуть лежати тільки певна кількість перших з них, а ми, коли цей список почне ставати занадто маленьким, будемо будувати новий список, просуваючись крок за кроком (збільшуючи споруджуваний список на 1 елемент з кожною операцією push або pop) з кінця черги в початок, йдучи за вказівниками на батьків вершин нашого дерева і намагаючись, щоб до моменту, коли старий список закінчиться, у нас вже був новий напоготові.

Тобто для кожної черги, крім покажчиків на початок і кінець і покажчика на елемент вже готового списку, будемо зберігати ще і покажчик на елемент що будується у списку (у випадку якщо ми нічого не будуємо, він буде дорівнює 0) і обчислювати його значення для нової черги (отриманої після застосування до вихідної push'a або pop'a) за наступним простому алгоритму:

• якщо у вихідній черзі даний покажчик дорівнював 0, перевіримо чи потрібно почати будувати новий список (критерій такої перевірки буде описаний трохи нижче);

• якщо необхідно, то створюємо елемент списку з нульовим покажчиком на наступний елемент за списком (тим самим цей створений елемент буде кінцем конструйованого списку), а покажчик на вершину ставимо на передостанній елемент нашої черги (батька останнього елемента);

• якщо ще не час, то покажчик залишаємо рівним нулю.

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

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

Критерій перевірки на початок конструювання

Поки розмір нашого списку більше або дорівнює 1/2 від кількості проміжних вершин (тобто вершин без першої і останньої), ми нічого не робимо, як тільки стане менше, починаємо конструювати новий. Зауважимо, що якщо проміжних вершин немає, то ми маємо нерівність 0 ≥ 0 і нічого не робимо. При такому підході ми ніколи не опинимося в ситуації, коли старий список скінчився, а новий ще не готовий.[5]

Доведення. Для початку доведемо наступний інваріант: якщо ми конструюємо новий список, то на кожному кроці 2k + l = s, де k - кількість елементів у старому списку, l - в конструйованому (після вже виконаної на цьому кроці добудови), s - сумарна кількість проміжних елементів. Доводити будемо методом математичної індукції. Розглянемо перший крок, коли ми тільки почали конструювання (l = 1). Зауважимо, що для нової черги 2k - s <0 (наш критерій), проте для вихідної 2kold - sold ≥ 0. Якщо наша операція push, то k = kold, а s = sold + 1, а якщо pop, то k = kold - 1 і s = sold - 1. Легко помітити, що в обох випадках 2k - s менше 2kold - sold рівно на одиницю і, оскільки обидві різниці - цілі числа, значить друга з них 0, а перша -1, отже, 2k + 1 = s, а наше l якраз одиниця і є. База індукції доведена.

Припустимо, що ми робимо операцію pop, а у вихідній черзі потрібний нам список порожній (при push ми цей список ніяк не використовуємо). Тоді може бути одне з двох:

• або для вихідної черги, що ми конструювали, новий список ще не починали, тоді у цій черзі 2k ≥ s, k = 0 => s = 0, тобто це черга розміром 0, 1 або 2 і знання її останнього елемента для pop достатньо;

• або новий список вже почали, тоді l ≠ 0, в силу інваріанта 2k + l = s, k = 0 => l = s ≠ 0 => конструйований список був непорожній і містив всі проміжні елементи, а значить, ми повинні зробити на тому кроці заміну і отримати непорожній список.

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

 

Література:

1. Персистентні структури: персистентний стек – [Електронний ресурс]. – Режим доступу: http://habrahabr.ru/post/113585/

2. Персистентні структури даних – [Електронний ресурс]. – Режим доступу: http://neerc.ifmo.ru/wiki/index.php?title=Персистентн..

3. Персистентний стек – [Електронний ресурс]. – Режим доступу: http://neerc.ifmo.ru/wiki/index.php?title=Персистентныйстек

4. Персистентна черга – [Електронний ресурс]. – Режим доступу: http://neerc.ifmo.ru/wiki/index.php?title=Персистентн..

5. Карл Бьорч, Постійні структури даних / Карл Бьорч // Коледж Хендрікс. - 2012. – c.10-15.

 

References:

1. Persystentni struktury: persystentnyi stek – [Electronic resource]. – Access mode: http://habrahabr.ru/post/113585/

2. Persystentni struktury danykh – [Electronic resource]. – Access mode: http://neerc.ifmo.ru/wiki/index.php?title=Persystentn.

3. Persystentnyi stek – [Electronic resource]. – Access mode: http://neerc.ifmo.ru/wiki/index.php?title=Persystentnыistek

4. Persystentna cherha – [Electronic resource]. – Access mode: http://neerc.ifmo.ru/wiki/index.php?title=Persystentn

5. Carl Burch, Persistent data structures / Carl Burch // Hendrix College - 2012. – р.10-15.

Site search

Конференции

Please publish modules in offcanvas position.