/A>Эксперименты
Рассмотренный алгоритм вычисления выражений языка XPath был полностью реализован в виде расширения к системе SXPath, предоставляющей возможности языка запросов к SXML-документам. Для определения количественного эффекта, достигаемого благодаря оптимизации вычисления обратных осей языка XPath, были проведены эксперименты по замерам производительности. В экспериментах сравнивалась реализация SXPath "до оптимизации'', в которой вычисление обратных осей XPath производилось за счет поиска необходимых узлов от корня документа, и реализованное расширение к SXPath, в котором выражения XPath вычисляются с помощью предложенного в работе алгоритма.
В качестве тестовых SXML-документов для экспериментов использовались автоматически сгенерированные документы различной глубины, элементы в каждом документе образуют сбалансированное дерево. Пример используемого в эксперименте SXML-документа для глубины 4 приведен на рис. 4. У каждого элемента в документе есть дочерний текстовый узел. Также каждый элемент за исключением элементов самого нижнего уровня имеет по 2 дочерних элемента, т.е. элементы документа образуют сбалансированное двоичное дерево. Имена всех элементов в документе различны, также различны значения всех текстовых узлов.
Рис. 4: Тестовый SXML-документ глубины 4.
В качестве тестовых выражений XPath использовались случайным образом сгенерированные пути доступа, состоящие из фиксированного числа шагов доступа. Каждый из шагов доступа использует произвольную из осей языка XPath, один из тестов узлов node(), * или text(), и не содержит предикатов. Пример одного из сгенерированных тестовых путей доступа, состоящего из 4 шагов доступа, приведен на рис. 5.
Рис. 5: Пример тестового пути доступа, состоящего из 4 шагов доступа.
В таблицах на рисунках 6 и 7 приведены результаты временных затрат на вычисление путей доступа, состоящих из 3 и 4 шагов доступа соответственно. В строках каждой таблицы указаны глубины тестовых SXML-документов, над которыми проводилось вычисление путей доступа. В результаты эксперимента вошли только те из случайно сгенерированных путей доступа, результатом вычисления которых являлось непустое множество узлов документа. Каждый из таких нетривиальных путей доступа вычислялся при помощи неоптимизированной реализации SXPath, в которой вычисление обратных осей XPath производится за счет поиска необходимых узлов от корня документа, и при помощи реализованного расширения SXPath, в котором выражения XPath вычисляются с помощью предложенного в работе алгоритма. В ячейках таблиц на рисунках 6 и 7 показаны усредненные времена вычисления, полученные для нескольких (по 20 для каждой строки) случайных путей доступа. Данные в таблицах не включают в себя время, требуемое для разбора путей доступа, и поэтому более точно отражают время вычисления над тестовыми документами.
Рис. 6: Результаты изменений для путей доступа XPath, состоящих из 3 шагов доступа.
Рис. 7: Результаты изменений для путей доступа XPath, состоящих из 4 шагов доступа.
Из таблиц легко видеть, что среднее время вычисления выражений XPath с использованием предложенного в работе алгоритма всегда меньше среднего времени, необходимого для вычисления тех же выражений, когда обратные оси вычисляются за счет поиска предков контекстного узла от корня документа. Относительный разрыв во времени увеличивается при увеличении глубины рассматриваемого тестового документа, т.е. при увеличении числа узлов в нем.
В ходе дополнительных экспериментов также было установлено, что накладные расходы предложенного алгоритма при вычислении выражений XPath, не содержащих обратных осей, незначительны, что достигается за счет описанного в разделе 5 распределения количества предков по грамматическим правилам языка XPath, минимизирующего количество хранимых в контексте предков контекстного узла.
