XML解析器/验证器的算法复杂性

Question

我需要知道不同XML工具（解析器，验证器，XPath表达式评估器等）的性能如何受输入文档大小和复杂度的影响。那里有资源记录CPU时间和内存使用情况如何受到影响......那么，是什么？文档大小以字节为单位节点数量？关系是线性的，多项式的还是更坏的？

更新

在IEEE计算机杂志的一篇文章，第41卷NR 9，2008年9月，笔者调查四大流行XML解析模型（DOM，SAX，StAX的和VTD）。他们运行一些非常基本的性能测试，这些测试表明，当输入文件的大小从1-15 KB增加到1-15 MB或大约1000倍时，DOM解析器的吞吐量将减半。其他模型的吞吐量不会受到显着影响。

不幸的是，他们没有执行更详细的研究，例如吞吐量/内存使用量作为节点数量/大小的函数。

这篇文章是here.

更新

我无法找到这个问题的任何正规治疗。对于它的价值，我做了一些实验，测量XML文档中节点的数量，作为文档大小的函数。我正在研究仓库管理系统，XML文档是典型的仓库文档，例如高级发货通知等。

下图显示了以字节为单位的大小和节点数量（应与DOM模型下文档的内存占用量成正比）之间的关系。不同的颜色对应于不同种类的文档。规模是日志/日志。黑线是最适合蓝点的线。有趣的是，对于各种文档，字节大小和节点大小之间的关系是线性关系，但比例系数可能会有很大的不同。

Answer 1

如果我面临着这个问题，但没有找到任何关于谷歌我可能会尝试这样做我自己。

一些“信封背后”的东西，以感受它的去向。但它会需要我有一个想法如何做一个XML解析器。 对于非algorithmical基准看看这里：

• 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

我觉得有参与拿出一个简单的复杂度，除非你做太多的变数很多假设。

一个简单的SAX样式解析器在文档大小和内存平面方面应该是线性的。

由于XPath表达式的复杂性起着巨大的作用，所以像XPath这样的东西不可能仅仅依据输入文档来描述。

同样，对于模式验证，一个大而简单的模式可能是线性的，而具有更复杂结构的较小模式会显示更差的运行时性能。

与大多数性能问题一样，获得准确答案的唯一方法就是测量它，看看会发生什么！

Answer 3

Rob Walker是对的：问题没有详细说明。考虑只是解析器（并忽略它们是否执行验证的问题），有两种主要特性：基于树的思考DOM和流/基于事件的思考SAX（推）和StAX（拉）。基于树的方法消耗更多的内存并且速度更慢（因为您需要完成对整个文档的解析），而基于流/事件的方法消耗更少的内存并且速度更快。基于树的解析器通常被认为更易于使用，虽然StAX相对SAX而言是一个巨大的改进（易于使用）。

Answer 4

我打算在我的应用程序中加载非常大的XML文件。我在这里问了Stack Overflow的问题：Fastest Possible XML handling for very large documents。

是的，这是解析部分，这是瓶颈。

我最终没有使用XML解析器。相反，我会尽可能有效地分析字符，以便优化速度。这导致3 GHz Windows PC上的每秒40 MB的读取，解析和加载内部数据结构的速度。

我会非常有兴趣听到各种XML解析模式如何与此相比较。