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