Сравнение множеств
Начнем рассмотрение с наиболее простого типа коллекций
— множества элементов типа T, предполагающего неявное задание и выполнение единственного семантического ограничения уникальности элементов
. Дельта для двух версий множества
может быть естественным образом представлена в виде неупорядоченного набора операций добавления и удаления соответствующих элементов коллекции:
Корректное представление дельты
предполагает, что выполняется условие
, означающее, что один и тот же элемент не может одновременно участвовать в операции добавления и удаления. Более того, будем исключать повторение операций добавления и удаления с одним и тем же элементом, которое при исполнении операций противоречило бы определению множества:
и
.
Применение операций, определяемых дельтой, довольно прозрачно. К заданному исходному множеству добавляются элементы, определяемые операциями ins, и удаляются элементы, определяемые операциями del. Тем самым, гарантируется тождественность условия
, в котором функция
возвращает модифицированное представление коллекции, полученное в результате применения дельты к заданному представлению коллекции X.
Две конкурентные транзакции
могут оказаться конфликтными в случае
, когда в одной транзакции некоторый элемент добавляется в коллекцию, а в другой транзакции тот же самый элемент удаляется. Однако, если обе дельты вычислялись относительно общей версии коллекции в рамках распространенной схемы слияния “3-way Merge”:
,
, то подобные конфликты исключены в силу того, что удаляемый элемент обязан принадлежать базовой версии коллекции X и не может быть добавлен в нее повторно вследствие ограничения уникальности элементов множества. В случае иных схем слияния с участием нескольких базовых версий, например, схемы “4-way Merge”, подобные конфликты должны идентифицироваться и корректно разрешаться. Тривиальными способами разрешения являются следующие опции
, предполагающие игнорирование обеих конфликтных операций или принятие одной из них.
Сложность вычисления дельты
определяется, прежде всего, способом представления исходных множеств (список, массив, сбалансированное дерево), а также алгоритмами поиска добавляемых и удаляемых элементов.
Вычислительная сложность наивной реализации, основанной на простом поиске элемента в неупорядоченном списке и не требующей определения на элементах множеств полного порядка может быть оценена как
. Сложность оптимальной реализации, основанной на предварительной сортировке исходных множеств, например, методом пирамидальной сортировки или методом слияния списков, можно оценить как
. А в случае использования для работы с множеством сбалансированного дерева, хранящего элементы в уже отсортированном порядке, сложность операции построения дельты оценивается как
. Понятно, что последняя оценка не может рассматриваться как реальная оценка, поскольку в данном случае основная часть затрат перенесена на стадию формирования исходных множеств. Наиболее корректной оценкой в данном случае является также
.
Ниже приведен пример сравнения двух версий множества натуральных чисел
. Пусть
— основная и модифицированная версии коллекции, содержащие следующие элементы:
,
. Тогда дельта, вычисленная путем сравнения двух версий множества, представляется как
.
Содержание раздела
