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


Сравнение списков - часть 3


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

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

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

Для конфликтных операций вставки

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

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

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

Пусть вспомогательные списки

,
 представляют собой соответствующие последовательности вставки элементов
 и
. Тогда их дельта представима в виде:

 
 

Способы консолидации элементов из альтернативных списков задаются на основе

 следующими размещениями:

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

Рассмотрим следующий пример.


Начало  Назад  Вперед



Книжный магазин