Complexidade algorítmica de analisadores/validadores XML

Question

Preciso saber como o desempenho de diferentes ferramentas XML (analisadores, validadores, avaliadores de expressões XPath, etc.) é afetado pelo tamanho e complexidade do documento de entrada.Existem recursos que documentam como o tempo de CPU e o uso de memória são afetados por...bem o que?Tamanho do documento em bytes?Número de nós?E a relação é linear, polinomial ou pior?

Atualizar

Num artigo na IEEE Computer Magazine, vol 41 nr 9, set 2008, os autores pesquisam quatro modelos populares de análise XML (DOM, SAX, StAX e VTD).Eles executam alguns testes de desempenho muito básicos que mostram que um analisador DOM terá seu rendimento reduzido pela metade quando o tamanho do arquivo de entrada for aumentado de 1-15 KB para 1-15 MB, ou cerca de 1000x maior.O rendimento dos outros modelos não é significativamente afetado.

Infelizmente, eles não realizaram estudos mais detalhados, como o uso de taxa de transferência/memória em função do número de nós/tamanho.

O artigo é aqui.

Atualizar

Não consegui encontrar nenhum tratamento formal para esse problema.Para constar, fiz alguns experimentos medindo o número de nós em um documento XML em função do tamanho do documento em bytes.Estou trabalhando em um sistema de gerenciamento de armazém e os documentos XML são documentos típicos de armazém, por exemploaviso de envio antecipado etc.

O gráfico abaixo mostra a relação entre o tamanho em bytes e o número de nós (que deve ser proporcional ao consumo de memória do documento em um modelo DOM).As diferentes cores correspondem a diferentes tipos de documentos.A escala é log/log.A linha preta é a que melhor se ajusta aos pontos azuis.É interessante notar que, para todos os tipos de documentos, a relação entre o tamanho do byte e o tamanho do nó é linear, mas o coeficiente de proporcionalidade pode ser muito diferente.

Answer 1

Se eu me deparasse com esse problema e não conseguisse encontrar nada no Google, provavelmente tentaria fazer isso sozinho.

Algumas coisas do tipo "back-of-an-evelope" para ter uma ideia de para onde está indo.Mas seria necessário que eu tivesse uma ideia de como fazer um analisador xml.Para benchmarks não algorítmicos, dê uma olhada aqui:

• 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

Acho que há muitas variáveis ​​envolvidas para chegar a uma métrica de complexidade simples, a menos que você faça muitas suposições.

Um analisador simples de estilo SAX deve ser linear em termos de tamanho do documento e plano para memória.

Algo como XPath seria impossível de descrever apenas em termos do documento de entrada, uma vez que a complexidade da expressão XPath desempenha um papel importante.

Da mesma forma para a validação de esquema, um esquema grande, mas simples, pode muito bem ser linear, enquanto um esquema menor com uma estrutura muito mais complexa apresentaria pior desempenho em tempo de execução.

Tal como acontece com a maioria das questões de desempenho, a única maneira de obter respostas precisas é medi-lo e ver o que acontece!

Answer 3

Rob Walker está certo:o problema não está especificado com detalhes suficientes.Considerando apenas os analisadores (e ignorando a questão de saber se eles realizam validação), existem dois tipos principais:baseado em árvore – pense em DOM – e baseado em streaming/evento – pense SAXOFONE (empurrar) e StAX (puxar).Falando em grandes generalidades, as abordagens baseadas em árvore consomem mais memória e são mais lentas (porque você precisa terminar de analisar o documento inteiro), enquanto as abordagens baseadas em streaming/eventos consomem menos memória e são mais rápidas.Os analisadores baseados em árvore são geralmente considerados mais fáceis de usar, embora o StAX tenha sido anunciado como uma grande melhoria (em facilidade de uso) em relação ao SAX.

Answer 4

Eu estava planejando carregar arquivos XML extremamente grandes em meu aplicativo.Fiz a pergunta aqui no Stack Overflow: Manipulação de XML mais rápida possível para documentos muito grandes.

E sim, foi a parte da análise, esse foi o gargalo.

Acabei não usando analisadores XML.Em vez disso, analisei os caracteres um por um da maneira mais eficiente possível, otimizando a velocidade.Isso resultou em velocidades de 40 MB por segundo em um PC Windows de 3 GHz para leitura, análise e carregamento da estrutura de dados interna.

Eu ficaria muito interessado em saber como os vários modos de análise XML se comparam a isso.