XML パーサー/バリデーターのアルゴリズムの複雑さ

StackOverflow https://stackoverflow.com/questions/31826

  •  09-06-2019
  •  | 
  •  

質問

さまざまな XML ツール (パーサー、バリデーター、XPath 式エバリュエーターなど) のパフォーマンスが入力ドキュメントのサイズと複雑さによってどのような影響を受けるかを知る必要があります。CPU 時間とメモリ使用量がどのように影響を受けるかを文書化したリソースはありますか?さて、何ですか？ドキュメントのサイズはバイト単位ですか?ノード数?そして、その関係は線形ですか、多項式ですか、あるいはそれより悪いのでしょうか?

アップデート

IEEE Computer Magazine、第 41 巻、第 9 号、2008 年 9 月の記事で、著者らは 4 つの一般的な XML 解析モデル (DOM、SAX、StAX、および VTD) を調査しています。彼らは、非常に基本的なパフォーマンス テストをいくつか実行し、入力ファイルのサイズが 1 ～ 15 KB から 1 ～ 15 MB、つまり約 1000 倍に増加すると、DOM パーサーのスループットが半分になることを示しました。他のモデルのスループットは大きな影響を受けません。

残念ながら、ノード数/サイズの関数としてのスループット/メモリ使用量など、より詳細な調査は行われませんでした。

記事は ここ。

アップデート

この問題に対する正式な対処法は見つかりませんでした。価値があるものとして、XML ドキュメント内のノード数をドキュメントのバイト単位のサイズの関数として測定するいくつかの実験を行ってきました。私は倉庫管理システムに取り組んでいますが、XML ドキュメントは典型的な倉庫ドキュメントです。事前発送通知など

以下のグラフは、バイト単位のサイズとノード数 (DOM モデルではドキュメントのメモリ フットプリントに比例するはずです) の関係を示しています。異なる色は、異なる種類の文書に対応します。スケールは対数/対数です。黒い線が青い点に最もよく適合します。興味深いのは、あらゆる種類のドキュメントで、バイト サイズとノード サイズの関係は線形ですが、比例係数は大きく異なる可能性があるということです。

benchmarks-bytes_vs_nodes

役に立ちましたか？

解決

もし私がその問題に直面して、Google で何も見つからなかったら、おそらく自分で解決しようとするでしょう。

今後の状況を把握するための「封筒の裏側」の内容。ただし、XML パーサーの実行方法を理解する必要があります。アルゴリズム以外のベンチマークについては、ここをご覧ください。

他のヒント

多くの仮定を置かない限り、単純な複雑さの指標を思いつくには、関係する変数が多すぎると思います。

単純な SAX スタイルのパーサーは、ドキュメント サイズに関して線形であり、メモリに関してはフラットである必要があります。

XPath のようなものは、XPath 式の複雑さが大きな役割を果たすため、入力ドキュメントだけの観点から説明することは不可能です。

スキーマ検証の場合も同様に、大規模だが単純なスキーマは線形である可能性がありますが、より複雑な構造を持つ小さなスキーマは実行時のパフォーマンスが低下します。

ほとんどのパフォーマンスに関する質問と同様、正確な答えを得る唯一の方法は、パフォーマンスを測定して何が起こるかを確認することです。

ロブ・ウォーカーは正しい：問題が十分に詳細に指定されていません。パーサーだけを考慮すると (検証を実行するかどうかという問題は無視して)、主に 2 つの種類があります。ツリーベース - DOM を考えてください - およびストリーミング/イベントベース - 考えてください サックス （押す）そして StAX （引く）。非常に一般的に言えば、ツリーベースのアプローチはより多くのメモリを消費し、速度が遅くなります (ドキュメント全体の解析を完了する必要があるため)。一方、ストリーミング/イベントベースのアプローチはメモリ消費が少なく、高速です。一般にツリーベースのパーサーは使いやすいと考えられていますが、StAX は SAX に比べて (使いやすさが) 大幅に改善されていると評判です。

非常に大きな XML ファイルをアプリケーションにロードする予定でした。私はここ Stack Overflow で質問をしました。 非常に大きなドキュメントの最速の XML 処理.

そう、それは解析部分であり、それがボトルネックでした。

結局、XML パーサーはまったく使用しませんでした。代わりに、速度を最適化して、文字を 1 つずつできるだけ効率的に解析しました。これにより、3 GHz Windows PC 上で内部データ構造の読み取り、解析、ロードの速度が 40 MB/秒になりました。

さまざまな XML 解析モードがこれとどのように比較されるのかを知りたいと思っています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top