Сравнение мультимножеств
Перейдем к задаче сравнения мультимножеств
с функцией
для подсчета числа вхождений элемента
в коллекцию
. При модификации коллекции данного типа дельта представляется как неупорядоченный набор множественного добавления и удаления элементов. Пусть
— две версии мультимножества, тогда дельта может быть сформирована как
В используемых обозначениях Z — множество целых чисел. Положительное значение параметра n в операции изменения кардинальности card(x,n) указывает на добавление элемента в коллекцию соответствующее число раз, отрицательное значение — на удаление элемента из коллекции. Нулевое значение n не содержательно для представления дельты, поскольку означает, что количество экземпляров элемента в коллекции не изменилось. В корректно сформированном представлении дельты
предполагается, что элемент мультимножества не может одновременно участвовать в нескольких операциях
. В противном случае сравнение идентичных версий коллекции могло бы привести к неожиданному результату, отличному от пустого представления дельты, например:
.
Применение базовой операции дельты card(x,n) состоит в кратном добавлении соответствующего элемента x
при положительном значении параметра n и в его кратном удалении при отрицательном значении параметра. Это гарантирует выполнение необходимого тождества
.
Две операции
конфликтуют друг с другом, если параметры кратности перемещения экземпляров одного и того же элемента в конкурентных транзакциях отличаются друг от друга
. Тривиальные способы разрешения конфликта состоят в выборе одной из опций
. Вместе с тем, логичным представляется расширение возможных опций путем назначения параметру кратности всего интервала значений, порождающего конфликтную ситуацию:
. Это означает, что может быть выбрано любое число кратности для операции перемещения, лежащее в интервале между соответствующими параметрами конфликтных операций. В случаях, когда обе конфликтные операции являются родственными, конфликт целесообразно разрешать, исходя из промежуточных значений.
В случаях, когда одна из конфликтных операций — операция добавления, а другая — операция удаления, допустимым является также весь диапазон значений параметра кратности, означая удаление или добавление числа элементов, не превышающего используемое значение соответствующей операции.
Сложность построения
определяется теми же факторами, что и сложность вычисления дельты обычного множества. Имеет место незначительное увеличение числа операций, однако это не влияет на асимптотическую оценку, которая в среднем выражается как
.
В качестве примера рассмотрим процедуру сравнения двух версий мультимножества символов. Пусть
— основная и модифицированная версии коллекции, содержащие следующие натуральные элементы
,
. Тогда дельта, вычисленная в результате сравнения двух версий коллекции, представляется как
.
Содержание раздела
