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

Partse.ru предлагает: запчасти на Honda Crosstour в Екатеринбурге!

Сравнение упорядоченных множеств - часть 2


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

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

 должно быть запрещено:

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

Для корректного применения дельты

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

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


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



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