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

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

Обновление

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

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

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

Обновление

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

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

benchmarks-bytes_vs_nodes
(источник: flickr.com)

14
задан Glorfindel 12 July 2019 в 22:25
поделиться

4 ответа

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

Некоторые "back-of-an-evelope" наполняют для получения ощущения того, куда оно идет. Но это было бы, виду нужен я для имения идеи того, как сделать xml синтаксический анализатор. Для не алгоритмические сравнительные тесты смотрят здесь:

3
ответ дан 1 December 2019 в 16:39
поделиться

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

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

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

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

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

1
ответ дан 1 December 2019 в 16:39
поделиться

Rob Walker прав: проблема не определяется достаточно подробно. При рассмотрении просто синтаксических анализаторов (и игнорировании вопроса того, выполняют ли они проверку), существует две основных разновидности: дерево-based— думает, что DOM— и streaming/event-based— думают SAX (нажатие) и StAX (получение по запросу). Говоря в огромных общих местах, основанные на дереве подходы используют больше памяти и медленнее (потому что необходимо закончить анализировать целый документ), в то время как подходы streaming/event-based используют меньше памяти и быстрее. Основанные на дереве синтаксические анализаторы обычно считают легче использовать, хотя StAX был объявлен как огромное улучшение (в простоте в употреблении) по SAX.

1
ответ дан 1 December 2019 в 16:39
поделиться

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

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

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

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

0
ответ дан 1 December 2019 в 16:39
поделиться
Другие вопросы по тегам:

Похожие вопросы: