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


Последовательности фиксированной длины


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

 будем использовать следующее представление дельты:

,

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

 заменяет значение элемента исходного массива
 с индексом i значением соответствующего элемента модифицируемого массива
.

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

 предполагает, что индексы модифицируемых элементов не повторяются в разных операциях:

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

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

Рассмотрим следующий пример согласования изменений в массиве. Пусть

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


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