validar - xml validator xsd
Complejidad algorítmica de analizadores/validadores XML (4)
Necesito saber cómo el rendimiento de las diferentes herramientas XML (analizadores, validadores, evaluadores de expresiones XPath, etc.) se ve afectado por el tamaño y la complejidad del documento de entrada. ¿Existen recursos que documentan cómo el tiempo de CPU y el uso de la memoria se ven afectados por ... bueno, qué? ¿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 en IEEE Computer Magazine, vol 41 nr 9, sept 2008, los autores estudian cuatro modelos de análisis XML populares (DOM, SAX, StAX y VTD). Ejecutan algunas pruebas de rendimiento muy básicas que muestran que un analizador DOM tendrá su rendimiento reducido a la mitad cuando el tamaño del archivo de entrada aumente de 1 a 15 KB a 1 a 15 MB o aproximadamente 1000 veces más. El rendimiento de los otros modelos no se ve significativamente afectado.
Lamentablemente, no realizaron estudios más detallados, como el uso de rendimiento / memoria en función del número de nodos / tamaño.
El artículo está aquí.
Actualizar
No pude encontrar ningún tratamiento formal de este problema. Por lo que vale, he realizado algunos experimentos para medir la cantidad 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 almacén y los documentos XML son documentos de almacén típicos, por ejemplo, aviso de envío avanzado, 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 que el coeficiente de proporcionalidad puede ser muy diferente.
Si tuviera que enfrentar ese problema y no pudiera encontrar nada en google, probablemente trataría de hacerlo por mi cuenta.
Algunas cosas del tipo "back-of-a-evelope" para tener una idea de hacia dónde se dirige. Pero me necesitaría tener una idea de cómo hacer un analizador xml. Para puntos de referencia no algorítmicos, mire aquí:
Creo que hay demasiadas variables involucradas para llegar a una métrica de complejidad simple a menos que haga muchas suposiciones.
Un analizador de estilo SAX simple debe ser lineal en términos de tamaño del documento y plano para la memoria.
Algo como XPath sería imposible de describir en términos de solo el 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 tiene una estructura mucho más compleja mostraría un peor rendimiento en el tiempo de ejecución.
Al igual que con la mayoría de las preguntas de rendimiento, la única forma de obtener respuestas precisas es medirlo y ver qué sucede.
Rob Walker tiene razón: el problema no se especifica con suficiente detalle. Teniendo en cuenta solo los analizadores (e ignorando la cuestión de si realizan la validación), hay dos sabores principales: DOM basado en árboles y streaming / basado en eventos, piense en SAX (push) y StAX (pull). 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 de transmisión / 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.
Estaba planeando cargar archivos XML extremadamente grandes en mi aplicación. Hice la pregunta aquí en : el manejo de XML más rápido posible para documentos muy grandes .
Y sí, era la parte de análisis, ese era el cuello de botella.
Terminé no usando analizadores XML en absoluto. En cambio, analicé los caracteres uno por uno de la manera más eficiente posible optimizando la velocidad. Esto dio como resultado velocidades de 40 MB por segundo en una PC con Windows de 3 GHz para la lectura, el análisis y la carga de la estructura de datos interna.
Me interesaría mucho escuchar cómo los diferentes modos de análisis XML se comparan con esto.