Complejidad algorítmica de analizadores/validadores XML

Question

Necesito saber cómo el tamaño y la complejidad del documento de entrada afectan el rendimiento de diferentes herramientas XML (analizadores, validadores, evaluadores de expresiones XPath, etc.).¿Existen recursos que documenten cómo el tiempo de CPU y el uso de memoria se ven afectados por...¿bien que?¿Tamaño del documento en bytes?¿Número de nodos?¿Y la relación es lineal, polinómica o peor?

Actualizar

En un artículo de IEEE Computer Magazine, vol 41 nr 9, septiembre de 2008, los autores analizan cuatro modelos populares de análisis XML (DOM, SAX, StAX y VTD).Realizan algunas pruebas de rendimiento muy básicas que muestran que el rendimiento de un analizador DOM se reducirá a la mitad cuando el tamaño del archivo de entrada aumente de 1-15 KB a 1-15 MB, o aproximadamente 1000 veces más grande.El rendimiento de los otros modelos no se ve afectado significativamente.

Desafortunadamente, no realizaron estudios más detallados, como el rendimiento/uso de memoria en función del número de nodos/tamaño.

el articulo es aquí.

Actualizar

No pude encontrar ningún tratamiento formal para este problema.Por si sirve de algo, he realizado algunos experimentos midiendo el número de nodos en un documento XML en función del tamaño del documento en bytes.Estoy trabajando en un sistema de gestión de almacenes y los documentos XML son documentos de almacén típicos, p.aviso de envío anticipado, etc.

El siguiente gráfico muestra la relación entre el tamaño en bytes y el número de nodos (que debe ser proporcional a la huella de memoria del documento en un modelo DOM).Los diferentes colores corresponden a diferentes tipos de documentos.La escala es log/log.La línea negra es la que mejor se ajusta a los puntos azules.Es interesante observar que para todo tipo de documentos, la relación entre el tamaño del byte y el tamaño del nodo es lineal, pero el coeficiente de proporcionalidad puede ser muy diferente.

Answer 1

Si me enfrentara a ese problema y no pudiera encontrar nada en Google, probablemente intentaría hacerlo yo mismo.

Algunas cosas "al final del sobre" para tener una idea de hacia dónde se dirige.Pero necesitaría que tuviera una idea de cómo hacer un analizador xml.Para puntos de referencia no algorítmicos, eche un vistazo aquí:

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

Answer 2

Creo que hay demasiadas variables involucradas para llegar a una métrica de complejidad simple, a menos que se hagan muchas suposiciones.

Un analizador simple de estilo SAX debe ser lineal en términos de tamaño de documento y plano en cuanto a memoria.

Algo como XPath sería imposible de describir simplemente en términos del documento de entrada, ya que la complejidad de la expresión XPath juega un papel muy importante.

Del mismo modo, para la validación de esquemas, un esquema grande pero simple puede ser lineal, mientras que un esquema más pequeño que tenga una estructura mucho más compleja mostraría un peor rendimiento en tiempo de ejecución.

Como ocurre con la mayoría de las preguntas sobre rendimiento, la única forma de obtener respuestas precisas es medirlo y ver qué sucede.

Answer 3

Rob Walker tiene razón:el problema no se especifica con suficiente detalle.Considerando solo los analizadores (e ignorando la cuestión de si realizan la validación), hay dos tipos principales:basado en árbol (piense en DOM) y basado en transmisión/eventos (piense en SAXÓFONO (empujar) y StAX (jalar).Hablando en grandes generalidades, los enfoques basados ​​en árboles consumen más memoria y son más lentos (porque es necesario terminar de analizar todo el documento), mientras que los enfoques basados ​​en streaming/eventos consumen menos memoria y son más rápidos.Los analizadores basados ​​en árboles generalmente se consideran más fáciles de usar, aunque StAX ha sido anunciado como una gran mejora (en facilidad de uso) con respecto a SAX.

Answer 4

Estaba planeando cargar archivos XML extremadamente grandes en mi aplicación.Hice la pregunta aquí en Stack Overflow: Manejo XML más rápido posible para documentos muy grandes.

Y sí, fue la parte del análisis, ese fue el cuello de botella.

Terminé sin utilizar analizadores XML en absoluto.En cambio, analicé los caracteres uno por uno de la manera más eficiente posible optimizando la velocidad.Esto resultó en velocidades de 40 MB por segundo en una PC con Windows de 3 GHz para leer, analizar y cargar la estructura de datos interna.

Me interesaría mucho saber cómo se comparan los distintos modos de análisis XML con esto.