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

Question

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

更新

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

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

文章在这里。

更新

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

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

_{（来源：flickr.com）}

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

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 解析模式与此相比如何。