Алгоритмическая сложность обработки XML и подобных языков
операции какие? чистый парсинг?
Распространённые.
Парсинг, валидация, поиск.
Парсинг, валидация, поиск.
Простой поиск - это фактически парсинг.
Сложный поиск обычно делают уже не по xml-у, а по некоему промежуточному представлению (например, базе).
Ресурсоемкость парсинга зависит от вида парсера:
Sax, Dom, XmlReader.
Простая валидация - это тоже фактически парсинг.
Про сложную валидацию не в курсе - т.к. она бывает очень и очень разная.
Сложный поиск обычно делают уже не по xml-у, а по некоему промежуточному представлению (например, базе).
Ресурсоемкость парсинга зависит от вида парсера:
Sax, Dom, XmlReader.
Простая валидация - это тоже фактически парсинг.
Про сложную валидацию не в курсе - т.к. она бывает очень и очень разная.
Уговорил. Можно пока остановиться на парсинге.
http://www.pankaj-k.net/xpb4j/docs/Measurements-May30/measurements-May30-2002.html
http://www.infoworld.com/article/04/04/30/HNxmlmessages_1.html
http://www.infoworld.com/article/04/04/30/HNxmlmessages_1.html
для больших объемов данных предполагается использовать
http://www.w3.org/XML/Binary/
http://www.w3.org/XML/Binary/
хм
понятно, что измерения найти можно, и самому проделать тоже
вопрос-то в другом
зато вторая ссылка прикольней - скоро можно будет завалить роутер, просто послав через него сложный xml
понятно, что измерения найти можно, и самому проделать тоже
вопрос-то в другом
зато вторая ссылка прикольней - скоро можно будет завалить роутер, просто послав через него сложный xml
Сложность Sax-процессора можно самому оценить.
как устроен sax-парсер представляешь?
как устроен sax-парсер представляешь?
Посмотрел на SAX.
Я бы не назвал это парсером.
У него поток лексем на выходе, за структурой он не следит вроде
Я бы не назвал это парсером.
У него поток лексем на выходе, за структурой он не следит вроде
что такое "структура" для XML?
> У него поток лексем на выходе
Скорее поток событий.
ps
что ты вообще ожидаешь на выходе парсера?
что например выдают парсеры других языков?
> У него поток лексем на выходе
Скорее поток событий.
ps
что ты вообще ожидаешь на выходе парсера?
что например выдают парсеры других языков?
> Скорее поток событий.
Его событие - и есть по сути обнаружение лексемы.
Парсер как минимум должен проверять well-formedness и
возвращать что-нибудь типа дерева (ну то есть какие-либо ссылки для
каждого элемента на то, что снаружи, и что внутри).
Ещё неплохо бы валидацию провести, но это уже будет алгоритм обработки дерева.
Интуитивно мне кажется, что простые схемы должны обрабатываться условно за линейное время,
а сложные - наверное, помедленнее. Обработка - это валидация и преобразование в удобный для работы формат.
Короче, идея ясна, надо самому разбираться, если задался получить ответ.
Что выдают другие парсеры - я не особенно в курсе, никогда не использовал XML.
Вот рендеринг HTML - тоже обработка.
Судя по поведению браузеров, сложность нелинейная
Его событие - и есть по сути обнаружение лексемы.
Парсер как минимум должен проверять well-formedness и
возвращать что-нибудь типа дерева (ну то есть какие-либо ссылки для
каждого элемента на то, что снаружи, и что внутри).
Ещё неплохо бы валидацию провести, но это уже будет алгоритм обработки дерева.
Интуитивно мне кажется, что простые схемы должны обрабатываться условно за линейное время,
а сложные - наверное, помедленнее. Обработка - это валидация и преобразование в удобный для работы формат.
Короче, идея ясна, надо самому разбираться, если задался получить ответ.
Что выдают другие парсеры - я не особенно в курсе, никогда не использовал XML.
Вот рендеринг HTML - тоже обработка.
Судя по поведению браузеров, сложность нелинейная
> Парсер как минимум должен проверять well-formedness и
Sax - well-formedness проверяет (там все проверки - это одно лишнее состояние в автомате).
> возвращать что-нибудь типа дерева
дерево в результате - это уже DOM.
ты в курсе, что не всякое дерево (не всякий xml) влезет в память?
и что не для всякой задачи необходимо хранить в памяти все дерево?
> Вот рендеринг HTML - тоже обработка.
В Html-е основная проблема - это таблицы - т.к. до окончания получения последнего закрывающего тега таблицы - по хорошему, нельзя делать рендеринг.
Соответственно приходится весь разобранный html-держать в памяти.
Sax - well-formedness проверяет (там все проверки - это одно лишнее состояние в автомате).
> возвращать что-нибудь типа дерева
дерево в результате - это уже DOM.
ты в курсе, что не всякое дерево (не всякий xml) влезет в память?
и что не для всякой задачи необходимо хранить в памяти все дерево?
> Вот рендеринг HTML - тоже обработка.
В Html-е основная проблема - это таблицы - т.к. до окончания получения последнего закрывающего тега таблицы - по хорошему, нельзя делать рендеринг.
Соответственно приходится весь разобранный html-держать в памяти.
> Sax - well-formedness проверяет (там все проверки - это одно лишнее состояние в автомате).
Автомат должен быть стековый, как я понимаю?
А что тогда "ещё одно состояние"?
А максимальный размер стека будет уже линейно зависить от размера документа,
если не ограничивать схему.
> ты в курсе, что не всякое дерево (не всякий xml) влезет в память?
В курсе.
Поэтому и уточнил, что нужны какие-то ссылки.
Например, это может быть ленивое дерево.
Или какое-то ещё представление, удобное приложению.
То есть, удобное API должно позволять приложению получать ту структуру,
что ему требуется, не заставляя при этом его самого хранить лишний контекст
для проверки корректности входа.
> В Html-е основная проблема - это таблицы - т.к. до окончания получения последнего закрывающего тега таблицы - по хорошему, нельзя делать рендеринг.
И вот когда он получен - тут-то и начинаются вычисления нелинейной сложности.
Автомат должен быть стековый, как я понимаю?
А что тогда "ещё одно состояние"?
А максимальный размер стека будет уже линейно зависить от размера документа,
если не ограничивать схему.
> ты в курсе, что не всякое дерево (не всякий xml) влезет в память?
В курсе.
Поэтому и уточнил, что нужны какие-то ссылки.
Например, это может быть ленивое дерево.
Или какое-то ещё представление, удобное приложению.
То есть, удобное API должно позволять приложению получать ту структуру,
что ему требуется, не заставляя при этом его самого хранить лишний контекст
для проверки корректности входа.
> В Html-е основная проблема - это таблицы - т.к. до окончания получения последнего закрывающего тега таблицы - по хорошему, нельзя делать рендеринг.
И вот когда он получен - тут-то и начинаются вычисления нелинейной сложности.
> А что тогда "ещё одно состояние"?
Еще один case в switch-е
> А максимальный размер стека будет уже линейно зависить от размера документа,
если не ограничивать схему.
в общем случае - да
в среднем - скорее ближе к логарифму
> То есть, удобное API должно позволять приложению получать ту структуру,
так сразу я не смогу придумать такое API, кому-то важна информация о родительских элементах, кому-то о соседних, кому-то о последующих, кому-то о детях, кому-то от конткекста и т.д.
> И вот когда он получен - тут-то и начинаются вычисления нелинейной сложности
Так сама постановка задачи нелинейная - оптимизировать размеры ячеек на основе содержимого каждой ячейки.
Еще один case в switch-е
> А максимальный размер стека будет уже линейно зависить от размера документа,
если не ограничивать схему.
в общем случае - да
в среднем - скорее ближе к логарифму
> То есть, удобное API должно позволять приложению получать ту структуру,
так сразу я не смогу придумать такое API, кому-то важна информация о родительских элементах, кому-то о соседних, кому-то о последующих, кому-то о детях, кому-то от конткекста и т.д.
> И вот когда он получен - тут-то и начинаются вычисления нелинейной сложности
Так сама постановка задачи нелинейная - оптимизировать размеры ячеек на основе содержимого каждой ячейки.
> Еще один case в switch-е
Я таки не понял, при использовании SAX нужно будет стек делать самому,
или он внутри сам делает?
> в общем случае - да
> в среднем - скорее ближе к логарифму
Утверждение бессмысленно, пока не определено, что значит "в среднем".
В зависимости от применения, для практики может иметь значение оптимальная оценка,
"средняя", или наихудшая.
> так сразу я не смогу придумать такое API, кому-то важна информация о родительских элементах,
> кому-то о соседних, кому-то о последующих, кому-то о детях, кому-то от конткекста и т.д.
Ну можно например предложить всё, пусть берут, что нужно.
> Так сама постановка задачи нелинейная - оптимизировать размеры ячеек на основе содержимого каждой ячейки.
Возникает аналогичный вопрос про другие типичные применения markup languages.
Я таки не понял, при использовании SAX нужно будет стек делать самому,
или он внутри сам делает?
> в общем случае - да
> в среднем - скорее ближе к логарифму
Утверждение бессмысленно, пока не определено, что значит "в среднем".
В зависимости от применения, для практики может иметь значение оптимальная оценка,
"средняя", или наихудшая.
> так сразу я не смогу придумать такое API, кому-то важна информация о родительских элементах,
> кому-то о соседних, кому-то о последующих, кому-то о детях, кому-то от конткекста и т.д.
Ну можно например предложить всё, пусть берут, что нужно.
> Так сама постановка задачи нелинейная - оптимизировать размеры ячеек на основе содержимого каждой ячейки.
Возникает аналогичный вопрос про другие типичные применения markup languages.
> Я таки не понял, при использовании SAX нужно будет стек делать самому,
или он внутри сам делает?
Стек необходимый для Wellformed-валидации он сам сделает.
> Ну можно например предложить всё, пусть берут, что нужно.
дык, это не эффективно.
> Возникает аналогичный вопрос про другие типичные применения markup languages
какие, например?
или он внутри сам делает?
Стек необходимый для Wellformed-валидации он сам сделает.
> Ну можно например предложить всё, пусть берут, что нужно.
дык, это не эффективно.
> Возникает аналогичный вопрос про другие типичные применения markup languages
какие, например?
> > Ну можно например предложить всё, пусть берут, что нужно.
> дык, это не эффективно.
Почему же? Предлагать - не значит вычислять. Вычислять, ясен перец, нужно лишь то, что требуется.
> Возникает аналогичный вопрос про другие типичные применения markup languages
Ну вот, например, индексирование и последующий поиск.
Или преобразование в другие форматы.
Дальше вам виднее, какие там ещё применения.
> дык, это не эффективно.
Почему же? Предлагать - не значит вычислять. Вычислять, ясен перец, нужно лишь то, что требуется.
> Возникает аналогичный вопрос про другие типичные применения markup languages
Ну вот, например, индексирование и последующий поиск.
Или преобразование в другие форматы.
Дальше вам виднее, какие там ещё применения.
> Дальше вам виднее, какие там ещё применения.
сколько максимально-разнообразных реальных применений xml-я ты уже посмотрел?
сколько максимально-разнообразных реальных применений xml-я ты уже посмотрел?
АПВC?
Несколько осмысленных и несколько бессмысленных видел.
Несколько осмысленных и несколько бессмысленных видел.
какие, например?
Оставить комментарий
Marinavo_0507
Я тут попробовал поискать на тему сабжа в гугле, ничего хорошего не нашёл.Интересно, кто-нибудь располагает оценками?
Если предлагают хранить большие объёмы данных в XML, либо принимать данные от удалённых систем,
то неплохо бы иметь оценки эффективности обработки: время вычислений, объём задействованной памяти.
В среднем и в наихудшем случае.