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


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


Подобные структуры обеспечивают быстрое преобразование индексов, необходимое для эффективной реализации следующих этапов.
  • Поиск циклической перестановки элементов множества
    , приводящей к последовательности элементов множества
    . Наиболее простым способом реализации данного этапа видится предварительная замена алфавита исходного множества
     на последовательность натуральных чисел
     и применение методики, применяемой в доказательстве теоремы о единственности специальной формы соединительного произведения перестановки линейно упорядоченного мультимножества [19].
  • Определение множества операторов вставки
    , упорядоченного по индексам вставки элементов, используя структуры соответствия индексов элементов множеств
     и
    .
  • Определение множества операторов удаления
    , упорядоченного по индексам удаляемых элементов, используя структуры соответствия индексов элементов множеств
     и
    .
  • Формирование единого списка операций дельты в соответствии с принятым порядком исполнения: сначала следуют операции перестановок, затем — операции вставок и в конце — операции удаления.

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

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

    .

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

    1. Вставка тождественных элементов в разные позиции.


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



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