Complessità algoritmica dei parser/validatori XML

Question

Ho bisogno di sapere in che modo le prestazioni di diversi strumenti XML (parser, validatori, valutatori di espressioni XPath, ecc.) sono influenzate dalle dimensioni e dalla complessità del documento di input.Esistono risorse che documentano il modo in cui il tempo della CPU e l'utilizzo della memoria sono influenzati da...quindi cosa?Dimensioni del documento in byte?Numero di nodi?E la relazione è lineare, polinomiale o peggio?

Aggiornamento

In un articolo su IEEE Computer Magazine, vol 41 nr 9, settembre 2008, gli autori esaminano quattro popolari modelli di parsing XML (DOM, SAX, StAX e VTD).Eseguono alcuni test prestazionali molto basilari che mostrano che un parser DOM avrà il suo throughput dimezzato quando la dimensione del file di input viene aumentata da 1-15 KB a 1-15 MB, o circa 1000 volte più grande.La produttività degli altri modelli non è influenzata in modo significativo.

Sfortunatamente non hanno eseguito studi più dettagliati, ad esempio sul throughput/utilizzo della memoria in funzione del numero di nodi/dimensione.

L'articolo è Qui.

Aggiornamento

Non sono riuscito a trovare alcun trattamento formale di questo problema.Per quello che vale, ho fatto alcuni esperimenti misurando il numero di nodi in un documento XML in funzione della dimensione del documento in byte.Sto lavorando su un sistema di gestione del magazzino e i documenti XML sono tipici documenti di magazzino, ad es.avviso di spedizione anticipato ecc.

Il grafico seguente mostra la relazione tra la dimensione in byte e il numero di nodi (che dovrebbe essere proporzionale all'impronta di memoria del documento in un modello DOM).I diversi colori corrispondono a diversi tipi di documenti.La scala è log/log.La linea nera si adatta meglio ai punti blu.È interessante notare che per tutti i tipi di documenti, la relazione tra dimensione in byte e dimensione del nodo è lineare, ma che il coefficiente di proporzionalità può essere molto diverso.

Answer 1

Se dovessi affrontare questo problema e non riuscissi a trovare nulla su Google, probabilmente proverei a farlo da solo.

Alcune cose "in fondo alla busta" per avere un'idea di dove sta andando.Ma avrei bisogno che io avessi un'idea di come fare un parser xml.Per i benchmark non algoritmici dai un'occhiata qui:

• 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

Penso che ci siano troppe variabili coinvolte per elaborare una semplice metrica di complessità a meno che non si facciano molte ipotesi.

Un semplice parser in stile SAX dovrebbe essere lineare in termini di dimensione del documento e piatto in termini di memoria.

Qualcosa come XPath sarebbe impossibile da descrivere in termini del solo documento di input poiché la complessità dell'espressione XPath gioca un ruolo enorme.

Allo stesso modo, per la convalida dello schema, uno schema grande ma semplice potrebbe essere lineare, mentre uno schema più piccolo con una struttura molto più complessa mostrerebbe prestazioni di runtime peggiori.

Come per la maggior parte delle domande sulle prestazioni, l'unico modo per ottenere risposte precise è misurarle e vedere cosa succede!

Answer 3

Rob Walker ha ragione:il problema non è specificato in modo sufficientemente dettagliato.Considerando solo i parser (e ignorando la questione se eseguono o meno la validazione), ci sono due versioni principali:basato su alberi, pensa al DOM, e basato su streaming/eventi, pensa SAX (spingere) e StAX (tiro).Parlando in termini generali, gli approcci basati su albero consumano più memoria e sono più lenti (perché è necessario completare l'analisi dell'intero documento), mentre gli approcci basati su streaming/eventi consumano meno memoria e sono più veloci.I parser basati su alberi sono generalmente considerati più facili da usare, sebbene StAX sia stato annunciato come un enorme miglioramento (in termini di facilità d'uso) rispetto a SAX.

Answer 4

Avevo intenzione di caricare file XML estremamente grandi nella mia applicazione.Ho posto la domanda qui su Stack Overflow: Gestione XML più veloce possibile per documenti molto grandi.

E sì, era la parte dell'analisi che rappresentava il collo di bottiglia.

Alla fine ho deciso di non utilizzare più i parser XML.Invece, ho analizzato i caratteri uno per uno nel modo più efficiente possibile ottimizzando la velocità.Ciò ha portato ad una velocità di 40 MB al secondo su un PC Windows da 3 GHz per la lettura, l'analisi e il caricamento della struttura dati interna.

Sarei molto interessato a sapere come si confrontano le varie modalità di analisi XML con questa.