Персистентна черга та її друзі

Якийсь час тому я натрапив на персистентні структури даних і, зокрема, на опис персистентної черги на вікі-конспектах ІТМО. Все добре, тільки якось складно: щоб реалізувати одну маленьку чергу використовується п'ять (в іншому варіанті - шість) стеків.

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

Персистентність

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

На малюнку показаний приклад персистентного стека до операції та після операції θ = push (δ, 78) . Грецькими літерами позначені версії стека, наприклад, версіїη відповідає стек з елементами 34, 12, 55, 26, аα - порожній стек. У процесі роботи зі стеком можуть з'являтися нові вершини, але старі не зникатимуть, ні змінюватися, в цьому і є сенс персистентності.

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

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

Персистентна черга

Як відомо, чергу легко реалізувати за допомогою двох стеків: з одного забираємо елементи, в інший кладемо, при необхідності беремо і перекидаємо всі елементи з другого до першого. Замінивши обидва стеки на персистентні виходить персистентна черга, то навіщо в статті на вікі-конспектах складності із шістьма стеками? Справа в тому, що можна реалізувати чергу через два стеки, це дасть оцінку O(1) на операцію, але ця оцінка амортизована. А персистенізація, на жаль, не зберігає амортизованих оцінок.

Дійсно, нехай у черзі версіїξ перший стек був порожній, і при наступній операціїget (тут і далі я називатиму операцію «покласти елемент у чергу» якput, "взяти з черги" -get ) доведеться перекидати елементи за O(n) , деn - кількість цих елементів. У звичайній черзі ця операція виконалася б, і наступніn операційget будуть виконуватися легко і невимушено за чисту одиницю. Але в персистентному випадку від черги можуть вимагати щось зробити з збереженою версієюξ — і кожна така операція виконуватиметься за O(n) . Неуспіх.

Власне, нагромадження з п'ятьма-шістьма стеками і потрібні щоб побудувати чергу, яка з одного боку заснована на стеках, з іншого - виконує операції за істинну O(1) , а не за амортизовану, тобто намагається перекидати елементи з другого стеку в перший заздалегідь , по одному, за кілька допоміжних. Така черга вже легко персистенізується. Але я почав з того, що п'ять (тим більше шість) стеків — це важко і зараз спробую обійтися чотирма.

Чотири стеки

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

Другий стек (help ) зберігатиме деякі актульні елементи у зворотному порядку, так щоб з нього завжди можна було брати елементи для операціїget. Тобто операціяget братиме елемент зhelp (і теж перераховуватиме і робити щось).

Щоб не сталося так, що елементи брати ні звідки, потрібен ще один стек (help2 ). У ньому будуть деякі елементи черги, він зростатиме і колиhelp закінчиться (або раніше) прийде на заміну.

Щоб вирощувати стекhelp2 потрібна (увага) персистентна копія стекаmain, з якої ми будемо брати елементи та перекидати елементи вhelp2. Ця копія у мене називаєтьсяmain2.

Виглядає це приблизно так:

Дія, яку я назвав щось - це і є насичення стекаhelp2 і саме для цього треба зберігати пару лічильників. Достатньо знати кількість елементів у черзі (нехай буде називатисяmain_size, хоча насправді вmain зберігаються ще й застарілі елементи) та кількість елементів, що залишилисяперекинути у допоміжний стек (відповідноmain2_size ). Операціяput робить main_size++ і не чіпаєmain2_size, операціяget робить main_size--, main2_size-- .

Ну а щось має робити таке:

Якщо main2_size > 0 , то перемістити один елемент зmain2 вhelp2 і main2_size--

Якщо main2_size == 0 , то замінитиhelp наhelp2, аhelp2 таmain2 замінити на порожні стеки

Якщоhelp2 порожній, то скопіюватиmain вmain2 (за O(1) , персистентний стек це дуже підтримує) і проставити main2_size = main_size .

Ще слід довести, що не буде ситуації, коли черга не порожня, а стекhelp порожній, але я залишу це читачеві. У ВКонтакті я викладав код, який у мене вийшов на цю тему.

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

Перший мінус – це використання пам'яті. Якщо ззовні є інформація, що використовувати треба не всі версії, а лише якісь конкретні, то можна збирати сміття та заощаджувати пам'ять. У мене ж старі елементи так і висітимуть у хвостіmain.

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