Алгоритмическая сложность парсеров / валидаторов XML

Question

Мне нужно знать, как производительность различных инструментов XML (анализаторы, валидаторы, оценщики выражений XPath и т. Д.) Зависит от размера и сложности входного документа. Существуют ли ресурсы, в которых описывается, как время процессора и использование памяти зависят от ... ну, что? Размер документа в байтах? Количество узлов? И являются ли отношения линейными, полиномиальными или хуже?

Обновление

В статье в журнале IEEE Computer Magazine, том 41, номер 9, сентябрь 2008 года авторы рассматривают четыре популярные модели синтаксического анализа XML (DOM, SAX, StAX и VTD). Они запускают несколько базовых тестов производительности, которые показывают, что пропускная способность DOM-парсера будет уменьшена вдвое при увеличении размера входного файла с 1-15 КБ до 1-15 МБ или примерно в 1000 раз больше. Пропускная способность других моделей существенно не влияет.

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

Статья здесь .

Обновление

Мне не удалось найти какое-либо официальное решение этой проблемы. Что бы это ни стоило, я провел несколько экспериментов, измеряя количество узлов в документе XML как функцию размера документа в байтах. Я работаю над системой управления складом, а XML-документы являются типичными складскими документами, например, предварительное уведомление о доставке и т. д.

На приведенном ниже графике показана взаимосвязь между размером в байтах и ​​количеством узлов (которая должна быть пропорциональна объему памяти документа в модели DOM). Разные цвета соответствуют разным видам документов. Шкала лог / лог. Черная линия лучше всего подходит для синих точек. Интересно отметить, что для всех видов документов соотношение между размером байта и размером узла является линейным, но коэффициент пропорциональности может быть очень разным.

Answer 1

Если бы я столкнулся с этой проблемой и не смог ничего найти в Google, я, вероятно, попытался бы сделать это сам.

Некоторый материал "обратно в конверт", чтобы понять, куда он идет. Но мне бы хотелось иметь представление о том, как сделать парсер xml. Для неалгоритмических тестов посмотрите здесь:

• http://www.xml.com/pub/a/Benchmark/exec.html
• http://www.devx.com/xml/Article/16922
• http://xerces.apache.org/xerces2-j/faq-performance.html

Answer 2

Роб Уокер прав: проблема не указана достаточно подробно. Учитывая только синтаксические анализаторы (и игнорируя вопрос о том, выполняют ли они проверку), существует два основных варианта: основанный на дереве - думаю, DOM - и потоковый / основанный на событиях - think SAX (push) и StAX (тянуть). Говоря в общих чертах, древовидные подходы потребляют больше памяти и работают медленнее (потому что вам нужно закончить анализ всего документа), в то время как потоковые / основанные на событиях подходы занимают меньше памяти и работают быстрее. Парсеры на основе дерева, как правило, считаются более простыми в использовании, хотя StAX был объявлен огромным улучшением (в простоте использования) по сравнению с SAX.

Answer 3

Я думаю, что слишком много переменных задействовано, чтобы придумать простой показатель сложности, если вы не сделаете много предположений.

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

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

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

Как и в большинстве вопросов о производительности, единственный способ получить точные ответы - это измерить его и посмотреть, что произойдет!

Answer 4

Я планировал загрузить очень большие файлы XML в свое приложение. Я задал вопрос здесь о переполнении стека: Самая быстрая обработка XML для очень больших документов .

И да, это была часть анализа, которая была узким местом.

Я вообще не использовал XML-парсеры. Вместо этого я анализировал символы один за другим максимально эффективно, оптимизируя скорость. Это привело к скорости 40 МБ в секунду на ПК с Windows 3 ГГц для чтения, анализа и загрузки внутренней структуры данных.

Мне было бы очень интересно услышать, как различные режимы синтаксического анализа XML сравниваются с этим.