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

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

Постановка завдання

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

Приймемо наступний простий інтерфейс роботи з нашої структурою даних, що отримуються в результаті запитів версії черг будемо нумерувати цілими неотрицательными числами, спочатку є лише порожня чергу під номером 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, яка утворюється витягом з вихідної першого елемента. Вихідна чергу також доступна під старим номером. У випадку, якщо вихідна чергу була порожня, нова також буде порожній.


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

For every there is a problem solution which is simple, fast, and wrong.
— The First Law of Online Judges
Як відомо, персистентный стек — дуже проста структура даних і асимптотика у нього та, що нам і потрібна. Крім того, ми знаємо, що чергу можна імітувати за допомогою двох стеків. Виникає очевидна ідея: зробимо ці два стеки персистентными і задача вирішена! На жаль, такий простий підхід не спрацює. Вся справа в тому, що при даній імітації у нас не всяка операція має асимптотику O(1): якщо при pop'е стек, з якого ми дістаємо елементи, виявляється порожнім, то ми перекладаємо всі елементи з іншого стека. У випадку зі звичайним чергою кожен елемент перекладається тільки один раз, тому сумарна асимптотика залишається O(n), але в персистентном випадку кожен елемент може належати багатьом черг і відповідно бути перекладений кілька разів. Нехай, наприклад, q — номер черги, у якої цей стек порожній, тоді після push(q, 1) та push(q, 2) в отриманих черг цей стек залишиться порожнім і при pop'ті з них кожен елемент черги q буде перекладено за два рази. Організувати ж якесь спільне використання перекладених елементів неможливо в силу того, що самі нижні елементи у отриманих перекладанням стеків будуть різні (1 і 2 відповідно), а персистентный стек влаштований таким чином, що кожен елемент зберігає покажчик на елемент, що лежить нижче, тому в будь-якому випадку ми будемо змушені мати 2 копії передостаннього елемента, які будуть вказувати на відповідний останній, а значить і 2 копії предпредпоследнего, щоб вказувати на потрібний передостанній і так далі по ланцюжку.

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

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

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

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



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

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

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

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

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

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



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

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

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

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

Для початку доведемо наступний варіант: якщо ми конструюємо новий список, то на кожному кроці 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 якраз одиниця і є. База індукції доведена. Доведемо перехід: нехай на якомусь кроці конструювання 2kold + lold = sold. Тоді l = lold + 1 (добудували список на 1 елемент), у разі push'a: k = kold, s = sold + 1, у разі pop'a: k = kold — 1, s = sold — 1. В обох випадках виконується рівність, а значить твердження доведено.

Припустимо тепер, що ми робимо операцію pop, а у вихідної черги потрібний нам список порожній (при push'е ми цей список ніяк не використовуємо). Тоді може бути одне з двох:
  • для вихідної черги ми конструювання нового списку не починали, тоді у цій черзі 2k ≥ s,
    k = 0 => s = 0, а значить, це черга розміром 0, 1 або 2 і знання її останнього елемента для здійснення pop'a достатньо,
  • або починали, тоді l ≠ 0, в силу інваріанта 2k + l = s, k = 0 => l = s ≠ 0 => конструйований список був непуст і містив всі проміжні елементи, а значить, ми повинні були зробити на тому кроці заміну і отримати непорожній список.
Залишилося лише довести, що, коли ми закінчуємо конструювання, умова відсутності конструювання виконується, тобто довжина отриманого списку не менше 1/2 від загальної кількості проміжних вершин, іншими словами, що в момент завершення 2l ≥ s або, що рівносильно, l ≥ s — l. Але що таке s — l? Це кількість проміжних вершин, які не містяться в нашому списку. Неважко зрозуміти, що воно дорівнює кількості операцій push, що сталися в процесі конструювання. Однак при кожній такій операції кількість елементів в нашому списку також збільшувалася на 1 (можлива ситуація, коли на попередньому кроці елемент конструируемого списку відповідає третьому за рахунком елемента черги і ми робимо pop, тоді для нової черги елемент списку починає відповідати першого проміжного елементу відразу без добудови, але таке можливо тільки на останньому кроці конструювання і тільки при операції pop). Тому l ≥ кількості таких push'їй не важко зрозуміти, що навіть строго більше), що нам і потрібно було довести.

Для наочності, продемонструємо, що відбувається в двох крайніх випадках: коли ми весь час виконуємо pop і коли весь час push'їм:


Реалізація на С++

Наостанок наведу реалізацію вищеописаною структури даних на мові С++ (при реалізації використовуються нововведення З++11). Варто сприймати цей код в якості прототипу, я старався написати як можна простіше і коротше, жертвуючи всім іншим на догоду цьому.
persistent_queue.h
#ifndef PERSISTENT_QUEUE_H
#define PERSISTENT_QUEUE_H

#include < cstdlib>
#include < vector>

using Element_type = int;

class Persistent_queue {
public:
Persistent_queue();
~Persistent_queue();
Persistent_queue(const Persistent_queue&) = delete;
Persistent_queue& operator =(const Persistent_queue&) = delete;

using Queue_id = size_t;
static const Queue_id start_queue_id = 0;
Queue_id push(Queue_id queue_id, const Element_type& value);
Queue_id pop(Queue_id queue_id);
const Element_type& front(Queue_id queue_id);
size_t size(Queue_id queue_id);
bool empty(Queue_id queue_id);
private:
struct TreeNode;
struct QueueIntermediateTreeNodeList;
struct Queue {
const TreeNode* const first;
const TreeNode* const last;
const size_t size;
const QueueIntermediateTreeNodeList* const known_intermediate_list;
const QueueIntermediateTreeNodeList* const constructing_intermediate_list;
const bool own_last;
const bool own_known_intermediate_list;

Queue(const TreeNode* const first, const TreeNode* const last, const size_t size,
const QueueIntermediateTreeNodeList* const known_intermediate_list,
const QueueIntermediateTreeNodeList* const constructing_intermediate_list,
const bool own_last, const bool own_known_intermediate_list);
~Queue() = default;
Queue(Черга&& source) = default; // needed for vector reallocation
Queue(const Queue&) = delete;
Queue& operator =(const Queue&) = delete;
};
std::vector<Queue> queues_;
Queue_id register_new_queue(const TreeNode* const first, const TreeNode* const last,
const size_t size,
const QueueIntermediateTreeNodeList* const known_intermediate_list,
const QueueIntermediateTreeNodeList* const constructing_intermediate_list,
const bool own_last, const bool own_known_intermediate_list);
void manage_intermediate_lists(const QueueIntermediateTreeNodeList*& known_intermediate_list,
const QueueIntermediateTreeNodeList*& constructing_intermediate_list,
bool& own_known_intermediate_list, const TreeNode* const first, const TreeNode* const last,
const size_t size);
};

#endif // PERSISTENT_QUEUE_H

persistent_queue.cpp
#include "persistent_queue.h"
#include <cassert>

struct Persistent_queue::TreeNode {
const TreeNode* const parent;
const Element_type element;

TreeNode(const TreeNode* const parent, const Element_type& value)
: parent(parent), element(value) {}
~TreeNode() = default;

TreeNode(const TreeNode&) = delete;
TreeNode& operator =(const TreeNode&) = delete;
};

struct Persistent_queue::QueueIntermediateTreeNodeList {
const Persistent_queue::TreeNode* const front;
const QueueIntermediateTreeNodeList* const next;
const size_t size;

QueueIntermediateTreeNodeList(const Persistent_queue::TreeNode* const front,
const QueueIntermediateTreeNodeList* const tail_list)
: front(front), next(tail_list), size{tail_list ? tail_list->size + 1 : 1} { assert(front); }
~QueueIntermediateTreeNodeList() = default;

QueueIntermediateTreeNodeList(const QueueIntermediateTreeNodeList&) = delete;
QueueIntermediateTreeNodeList& operator =(const QueueIntermediateTreeNodeList&) = delete;
};



Persistent_queue::Queue::Queue(
const Persistent_queue::TreeNode* const first, const Persistent_queue::TreeNode* const last,
const size_t size, const Persistent_queue::QueueIntermediateTreeNodeList* const known_intermediate_list,
const Persistent_queue::QueueIntermediateTreeNodeList* const constructing_intermediate_list,
const bool own_last, const bool own_known_intermediate_list
)
: first(first), останній(last), size(size), known_intermediate_list(known_intermediate_list)
, constructing_intermediate_list(constructing_intermediate_list)
, own_last(own_last), own_known_intermediate_list(own_known_intermediate_list)
{
// Some asserts
if (size == 0) {
assert(first == nullptr);
assert(last == nullptr);
} else {
assert(first);
assert(last);
if (size > 1)
assert(last->parent);
}
if (size <= 2) {
assert(known_intermediate_list == nullptr);
assert(constructing_intermediate_list == nullptr);
if (size == 1)
assert(first == last);
if (size == 2)
assert(first == last->parent);
} else {
assert(known_intermediate_list);
assert(first == known_intermediate_list->front->parent);
}
}



size_t Persistent_queue::size(const Persistent_queue::Queue_id queue_id)
{
return queues_.at(queue_id).size;
}

bool Persistent_queue::empty(const Queue_id queue_id)
{
return size(queue_id) == 0;
}

const Element_type& Persistent_queue::front(const Persistent_queue::Queue_id queue_id)
{
assert(!empty(queue_id));
return queues_.at(queue_id).first->element;
}

Persistent_queue::Queue_id
Persistent_queue::register_new_queue(const TreeNode* const first, const TreeNode* const last,
const size_t size, const QueueIntermediateTreeNodeList* const known_intermediate_list,
const QueueIntermediateTreeNodeList* const constructing_intermediate_list,
const bool own_last, const bool own_known_intermediate_list)
{
queues_.emplace_back(first, last, size, known_intermediate_list, constructing_intermediate_list,
own_last, own_known_intermediate_list);
return queues_.size() - 1;
}

Persistent_queue::Persistent_queue()
{
register_new_queue(nullptr, nullptr, 0, nullptr, nullptr, false, false);
}

Persistent_queue::~Persistent_queue()
{
for (const auto& q : queues_) {
if (q.own_last)
delete q.last;
if (q.own_known_intermediate_list)
delete q.known_intermediate_list;
delete q.constructing_intermediate_list;
}
}

Persistent_queue::Queue_id
Persistent_queue::push(const Persistent_queue::Queue_id queue_id, const Element_type& value)
{
const auto& queue_for_push = queues_.at(queue_id);
const size_t size = queue_for_push.size + 1;
const bool own_last = true;
const TreeNode* first;
const TreeNode* last;
if (queue_for_push.size == 0) {
first = last = new TreeNode(nullptr, value);
} else {
first = queue_for_push.first;
last = new TreeNode(queue_for_push.last, value);
}
bool own_known_intermediate_list;
const QueueIntermediateTreeNodeList* known_intermediate_list = queue_for_push.known_intermediate_list;
const QueueIntermediateTreeNodeList* constructing_intermediate_list =
queue_for_push.constructing_intermediate_list;
manage_intermediate_lists(known_intermediate_list, constructing_intermediate_list,
own_known_intermediate_list, first, last, size);
return register_new_queue(first, last, size, known_intermediate_list, constructing_intermediate_list,
own_last, own_known_intermediate_list);
}

Persistent_queue::Queue_id Persistent_queue::pop(const Persistent_queue::Queue_id queue_id)
{
const auto& queue_for_pop = queues_.at(queue_id);
const bool own_last = false;
const TreeNode* first;
const TreeNode* last;
size_t size;
const QueueIntermediateTreeNodeList* known_intermediate_list;
if (queue_for_pop.size <= 1) {
first = last = nullptr;
size = 0;
known_intermediate_list = nullptr;
} else {
last = queue_for_pop.last;
size = queue_for_pop.size - 1;
if (queue_for_pop.size == 2) {
first = queue_for_pop.last;
known_intermediate_list = nullptr;
} else {
assert(queue_for_pop.known_intermediate_list != nullptr);
first = queue_for_pop.known_intermediate_list->front;
known_intermediate_list = queue_for_pop.known_intermediate_list->next;
}
}
bool own_known_intermediate_list;
const QueueIntermediateTreeNodeList* constructing_intermediate_list =
queue_for_pop.constructing_intermediate_list;
manage_intermediate_lists(known_intermediate_list, constructing_intermediate_list,
own_known_intermediate_list, first, last, size);
return register_new_queue(first, last, size, known_intermediate_list, constructing_intermediate_list,
own_last, own_known_intermediate_list);
}

void Persistent_queue::manage_intermediate_lists(
const Persistent_queue::QueueIntermediateTreeNodeList*& known_intermediate_list,
const Persistent_queue::QueueIntermediateTreeNodeList*& constructing_intermediate_list,
bool& own_known_intermediate_list, const Persistent_queue::TreeNode* const first,
const Persistent_queue::TreeNode* const last, const size_t size)
{
own_known_intermediate_list = false;
const size_t intermediate_nodes_count = (size > 2 ? size - 2 : 0);
size_t known_intermediate_list_size =
(known_intermediate_list ? known_intermediate_list->size : 0);
if (2*known_intermediate_list_size < intermediate_nodes_count) {
auto try_to_replace_known_to_constructing = [&](){
if (constructing_intermediate_list && constructing_intermediate_list->front->parent == first) {
known_intermediate_list = constructing_intermediate_list;
known_intermediate_list_size = constructing_intermediate_list->size;
constructing_intermediate_list = nullptr;
return true;
}
return false;
};

if (!try_to_replace_known_to_constructing()) {
const auto adding_node = (constructing_intermediate_list ?
constructing_intermediate_list->front->parent : last->parent);
constructing_intermediate_list = new QueueIntermediateTreeNodeList(
adding_node, constructing_intermediate_list);
if (try_to_replace_known_to_constructing())
own_known_intermediate_list = true;
}
}
// Check інваріанти
if (2*known_intermediate_list_size >= intermediate_nodes_count)
assert(constructing_intermediate_list == nullptr);
const size_t constructing_intermediate_list_size =
(constructing_intermediate_list ? constructing_intermediate_list->size : 0);
const auto invariant_sum = 2*known_intermediate_list_size + constructing_intermediate_list_size;
assert(invariant_sum >= intermediate_nodes_count);
if (constructing_intermediate_list)
assert(invariant_sum == intermediate_nodes_count);
}


Типи TreeNode, Queue і QueueIntermediateTreeNodeList відповідає вершині дерева, черги і елементу односвязного списку із нашого алгоритму. Булеві змінні в Queue використовуються для коректного звільнення пам'яті в деструкторе нашого класу: вершину дерева і елемент списку видаляє чергу та, яка їх і створювала (як вже було зазначено вище, при кожному запиті створюється не більше однієї вершини і не більше одного елемента списку). Вершина дерева створюється тільки при операції push і покажчик на неї записується у last, відповідно, own_last вказує, записана в last нова чи стара вершина. Створений при конструюванні елемент списку майже завжди записується в constructing_intermediate_list, крім випадку, коли він був створений і конструювання на цьому ж кроці закінчилося, в такому випадку він переноситься в known_intermediate_list, а constructing_intermediate_list стає нулем, і друга булева змінна own_known_intermediate_list служить як раз для ідентифікації такого випадку.

Другий можливо неочевидний момент — це закрита функція-член manage_intermediate_lists, яка виглядає наступним чином:
void Persistent_queue::manage_intermediate_lists(
const Persistent_queue::QueueIntermediateTreeNodeList*& known_intermediate_list,
const Persistent_queue::QueueIntermediateTreeNodeList*& constructing_intermediate_list,
bool& own_known_intermediate_list, const Persistent_queue::TreeNode* const first,
const Persistent_queue::TreeNode* const last, const size_t size)
{
own_known_intermediate_list = false;
const size_t intermediate_nodes_count = (size > 2 ? size - 2 : 0);
size_t known_intermediate_list_size =
(known_intermediate_list ? known_intermediate_list->size : 0);
if (2*known_intermediate_list_size < intermediate_nodes_count) {
auto try_to_replace_known_to_constructing = [&](){
if (constructing_intermediate_list && constructing_intermediate_list->front->parent == first) {
known_intermediate_list = constructing_intermediate_list;
known_intermediate_list_size = constructing_intermediate_list->size;
constructing_intermediate_list = nullptr;
return true;
}
return false;
};

if (!try_to_replace_known_to_constructing()) {
const auto adding_node = (constructing_intermediate_list ?
constructing_intermediate_list->front->parent : last->parent);
constructing_intermediate_list = new QueueIntermediateTreeNodeList(
adding_node, constructing_intermediate_list);
if (try_to_replace_known_to_constructing())
own_known_intermediate_list = true;
}
}
// Check інваріанти
}

Ця функція реалізує вищеописаний алгоритм роботи з покажчиком на споруджуваний список (зверніть увагу, перші три параметри передаються по неконстантной посиланням, причому для перших двох передбачається, що змінні за посиланням ініціалізується потрібними значеннями перед викликом). Важливо перед добудовою списку спочатку перевіряти, а не став старий елемент першим проміжним, тому що, як вже зазначалося, у разі pop'а такий варіант можливий. Може бути хтось помітив, що ми завжди перевіряємо на наш критерій початку конструювання:
if (2*known_intermediate_list_size < intermediate_nodes_count) {
не виділяючи окремо випадок, коли конструювання вже йде. Справа в тому, що під час всього процесу конструювання наш критерій залишатиметься вірним, це очевидним чином випливає з нашого інваріанта конструювання: 2k + l = s, l > 0 => 2k < s.

Можливі оптимізації

По-перше, як видно на схемою, при вчиненні кількох різних операцій з однією і тією ж чергою, для якої йде конструювання (на схемі це операції pop(Q) та push(Q, 11)), створюється декілька абсолютно ідентичних між собою елементів списку (вони вказують на один і той же наступний елемент і одну і ту ж вершину дерева — на схемі це два блакитних кружечка з цифрою 7). Ми могли б спробувати «склеїти» такі елементи в один, використовуючи, наприклад, структуру, яка при добудову говорила б нам, а не зробив вже це хтось перед нами (в якості такої структури можна використовувати банальний вектор або двусвязный список). Очевидно, така оптимізація буде добре працювати (економити багато пам'яті) у випадку сильно розгалужених дерев.

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

Нарешті, по-третє, можна спробувати пограти з константами. Наприклад, можна добудовувати за крок за 1 елементу, а по 2, тоді починати конструювання досить при k < 1/3s. Можливо, це буде якось корисно.

На цьому все, спасибі всім, хто дочитав.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.