Создание алгоритмической машины времени

Для решения некоторых очень специфических задач геолокации и учетных баз данных нам необходимо прибегать к структурам данных, которые позволяют разработчику совершить «путешествие во времени» — вернуть структуру в прежнее состояние или изменить порядок выполняемых операций и посмотреть каким будет нынешний результат.

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

Типы настойчивости

1. Частично стойкий

В этих типах структур данных вы можете прочитать информацию о любом состоянии структуры, но можете только изменить «настоящее». Вы можете думать об этом как о структуре данных с памятью. Вы можете извлечь информацию из прошлого, но не можете изменить ее. Течение времени не нарушено.

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

Одним из примеров такой структуры данных является менеджер пакетов, такой как npm или PyPi. У каждого пакета есть версия, представляющая собой монотонно возрастающий ряд чисел. Если вы хотите, вы можете изменить версию на меньшую и вернуть код к той точке в прошлом, но вы не можете изменить его.

2. Полностью стойкий

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

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

Примером этого может быть система распределенного реестра, такая как блокчейн. Мы можем вернуться в цепочку и начать ремайнить блоки, создавая альтернативные ветки цепочки, но только самая длинная будет считаться действительной.

3. Cполностью сохраняемый

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

Тем самым вы берете историю изменений из обеих временных ветвей, объединяя их в одну. Если вы когда-либо работали с системами контроля версий, вы уже знаете, как выполняется слияние.

4. Обратная сила

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

Выполнение

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

1. Копирование при записи

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

Кроме того, каждая операция изменения приводит к созданию полной копии, даже если внесенные изменения были относительно небольшими.

2. Копирование пути

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

3. Жировые узлы

Даже при копировании пути мы не можем избежать ненужных копий. На изображении выше вы можете заметить, что элементы d, f и g имеют свои прошлые дубликаты, несмотря на то, что операция вставки практически не изменила их.

Итак, что, если мы изменим точку зрения? Вместо того, чтобы гарантировать постоянство структуры данных в целом, мы будем принудительно обеспечивать постоянство отдельных частей структуры.

Если мы разделим структуру на отдельные узлы фиксированного размера, которые можно изменять независимо, и обеспечим возможность изменения ссылок на другие узлы так же, как и данные, мы превратим структуру в нечто, известное как машина указателей.

Многие известные структуры данных могут быть представлены в виде указателя. Хорошим примером является двоичное дерево: каждый узел в двоичном дереве имеет фиксированный размер и хранит только базовые данные и указатели на другие узлы.

Хорошая новость заключается в том, что в случае стрелочной машины мы можем добиться постоянства с низкими затратами.

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

Эти алгоритмы не будут создавать ненужных копий, позволят выполнять любые операции по изменению ценой O(1), так как любое изменение просто запишет себя в журналы изменений узла. Изменение в узле может вызвать изменения во всех других узлах, что делает сценарий наихудшего случая довольно дорогим, но, к счастью, граница амортизированного времени по-прежнему составляет O(1), что позволяет нам сделать практически любую структуру данных постоянной без дополнительных затрат. расходы.

Заключение

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