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

Question

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

Обновить

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

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

Статья является вот.

Обновить

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

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

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

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

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

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

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

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

Answer 3

Роб Уокер прав:проблема не описана достаточно подробно.Рассматривая только парсеры (и игнорируя вопрос о том, выполняют ли они проверку), существует два основных варианта:основанный на дереве—think DOM-и потоковый / основанный на событиях—think САКСОФОН (толчок) и Штакс (тянет).Говоря в общих чертах, древовидные подходы потребляют больше памяти и работают медленнее (потому что вам нужно завершить синтаксический анализ всего документа), в то время как подходы, основанные на потоковой передаче / событиях, потребляют меньше памяти и работают быстрее.Древовидные анализаторы обычно считаются более простыми в использовании, хотя StAX был объявлен как огромное улучшение (в плане простоты использования) по сравнению с SAX.

Answer 4

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

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

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

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