Язык модификации данных формата XML функциональными методами



Алгоритмическая сложность - часть 3


На этапе обхода дерева SXML-документа производится вызов обработчиков на обрабатываемых узлах и формирование нового дерева в соответствии с возвращаемыми результатами обработчиков.
Количество обработчиков, которое может быть ассоциировано с одним узлом SXML-документа, не превосходит суммарного количества базовых узлов по всем операциям модификации, т.е. произведения m·n .
Поскольку по семантике предлагаемого языка запросов несколько обработчиков, ассоциированных с одним и тем же узлом, вызываются по правилам суперпозиции, на время выполнения одного обработчика влияют узлы, которые могли быть добавлены в результате вызовов предыдущих по порядку обработчиков, и поэтому это время оценивается сверху выражением T(n+N(n)).
Произведение максимального времени работы одного обработчика на максимальное количество ассоциированных с одним узлом обработчиков и на количество узлов в исходном документе и дает (5).

Производимые проверки корректности сделанных модификаций уже не зависят от вида запроса на модификацию или количества операций модификации в нем, но зависят только от сконструированного результирующего SXML-документа. В терминах введенных в условии теоремы обозначений, данное соображение означает, что временная оценка этапа проверки корректности сделанных модификаций зависит только от числа (n+N(n)), т.е. от количества узлов в новом SXML-документе.
Среди производимых проверок асимптотически доминирует проверка на отсутствие у данного элемента нескольких атрибутов с одинаковыми именами.
Проверка на отсутствие совпадающих имен атрибутов у данного элемента производится с помощью известного алгоритма сортировки слиянием по именам атрибутов данного элемента. Время работы алгоритма сортировки слиянием оценивается выражением

O( (n+N(n))·log2(n+N(n)) )   . 

Ввиду того, что данная проверка производится для каждого элемента в результирующем SXML-документе, записанная оценка умножается на число узлов в документе, что окончательно дает (6).

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




Содержание  Назад  Вперед