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


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


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

При подобной интерпретации каждая операция вставки элементов

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

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

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

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

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

Отметим, что агрегированная операция удаления общих элементов

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


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