Сравнение мультимножеств

Перейдем к задаче сравнения мультимножеств

с функцией

для подсчета числа вхождений элемента

в коллекцию

. При модификации коллекции данного типа дельта представляется как неупорядоченный набор множественного добавления и удаления элементов. Пусть

— две версии мультимножества, тогда дельта может быть сформирована как

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

предполагается, что элемент мультимножества не может одновременно участвовать в нескольких операциях

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

Применение базовой операции дельты card(x,n) состоит в кратном добавлении соответствующего элемента x при положительном значении параметра n и в его кратном удалении при отрицательном значении параметра. Это гарантирует выполнение необходимого тождества

Две операции

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

. Тривиальные способы разрешения конфликта состоят в выборе одной из опций

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

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

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

. В качестве примера рассмотрим процедуру сравнения двух версий мультимножества символов. Пусть

— основная и модифицированная версии коллекции, содержащие следующие натуральные элементы

. Тогда дельта, вычисленная в результате сравнения двух версий коллекции, представляется как

.

Содержание раздела

Главная сайта