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

Question

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

更新

在 IEEE Computer Magazine（2008 年 9 月）第 41 卷第 9 卷上的一篇文章中，作者调查了四种流行的 XML 解析模型（DOM、SAX、StAX 和 VTD）。他们运行了一些非常基本的性能测试，结果表明，当输入文件的大小从 1-15 KB 增加到 1-15 MB 或大约 1000 倍时，DOM 解析器的吞吐量将减半。其他模型的吞吐量没有受到显着影响。

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

这篇文章是 这里。

更新

我无法找到解决这个问题的任何正式方法。不管怎样，我已经做了一些实验，测量 XML 文档中的节点数作为文档大小（以字节为单位）的函数。我正在开发一个仓库管理系统，XML 文档是典型的仓库文档，例如提前发货通知等

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

Answer 1

如果我遇到这个问题并且在谷歌上找不到任何东西，我可能会尝试自己做。

一些“信封背面”的东西来了解它的发展方向。但它需要我了解如何做 xml 解析器。对于非算法基准测试请看这里：

• 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

罗布·沃克是对的：问题没有描述得足够详细。仅考虑解析器（并忽略它们是否执行验证的问题），有两种主要风格：基于树——想想 DOM——和基于流/事件——想想 萨克斯 （推）和 斯塔克斯 （拉）。一般来说，基于树的方法消耗更多的内存并且速度更慢（因为您需要完成整个文档的解析），而基于流/事件的方法消耗更少的内存并且速度更快。基于树的解析器通常被认为更易于使用，尽管 StAX 被誉为相对于 SAX 的巨大改进（在易用性方面）。

Answer 4

我计划在我的应用程序中加载非常大的 XML 文件。我在 Stack Overflow 上问了这个问题： 对非常大的文档进行最快的 XML 处理.

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

我最终根本没有使用 XML 解析器。相反，我尽可能高效地逐个解析字符，以优化速度。这使得在 3 GHz Windows PC 上读取、解析和加载内部数据结构的速度达到每秒 40 MB。

我非常有兴趣了解各种 XML 解析模式与此的比较。