Сравнение множеств

Начнем рассмотрение с наиболее простого типа коллекций

— множества элементов типа T, предполагающего неявное задание и выполнение единственного семантического ограничения уникальности элементов

. Дельта для двух версий множества

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

Корректное представление дельты

предполагает, что выполняется условие

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

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

, в котором функция

возвращает модифицированное представление коллекции, полученное в результате применения дельты к заданному представлению коллекции X.

Две конкурентные транзакции

могут оказаться конфликтными в случае

, когда в одной транзакции некоторый элемент добавляется в коллекцию, а в другой транзакции тот же самый элемент удаляется. Однако, если обе дельты вычислялись относительно общей версии коллекции в рамках распространенной схемы слияния “3-way Merge”:

, то подобные конфликты исключены в силу того, что удаляемый элемент обязан принадлежать базовой версии коллекции X и не может быть добавлен в нее повторно вследствие ограничения уникальности элементов множества. В случае иных схем слияния с участием нескольких базовых версий, например, схемы “4-way Merge”, подобные конфликты должны идентифицироваться и корректно разрешаться. Тривиальными способами разрешения являются следующие опции

, предполагающие игнорирование обеих конфликтных операций или принятие одной из них.

Сложность вычисления дельты

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

. Сложность оптимальной реализации, основанной на предварительной сортировке исходных множеств, например, методом пирамидальной сортировки или методом слияния списков, можно оценить как

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

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

. Ниже приведен пример сравнения двух версий множества натуральных чисел

. Пусть

— основная и модифицированная версии коллекции, содержащие следующие элементы:

. Тогда дельта, вычисленная путем сравнения двух версий множества, представляется как

.

Содержание раздела

Главная сайта