0

後でそのデータにアクセスしたい 5 MB の XML フラット構造があります。Java で XOM パーサーを使用して XML を解析していますが、ファイル サイズのために時間がかかるため、データを取得するたびにツリー全体をループしたくありません。

XMLは次のようになります

<TypeDesc Type="Person" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="test 1"/>
<TypeDesc Type="Person" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="test 2"/>
<TypeDesc Type="Person" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="test 2"/>
...
<TypeDesc Type="Person" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="payment"/>
<TypeDesc Type="Student" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="good"/>
<TypeDesc Type="Student" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="bad"/>
<TypeDesc Type="Student" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="fair"/>
...
<TypeDesc Type="Student" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="fair"/>

私のロジックでは、PKEY = SOMETTUFF AND Type = OtherStuff の場合、ノードの longDes を取得したいと考えています。

全体をループして、他の属性が満たされている場合に longDes を取得すると、非常にコストがかかります。

O(n) ではなく O(1) でデータにアクセスできるようにデータを保存して、XML 全体を 1 回ループし、後で反復するためにデータ構造にアクセスするにはどうすればよいですか。

4

2 に答える 2

1

現在の形式でこれを満たすための一定時間のルックアップ手順を見つけることはまずありません。さらに、一定時間のルックアップは特定の要件ですか、それともプロジェクトのステータス/セットアップのまばたきした視点の一部としてそれを構成していますか? 別名「XY問題」。あなたが見つける可能性が最も高いのはO(n log n)orO(log n)アルゴリズムです。Big O チートシートを参照してください

この構造の解析を可能にする既存のフレームワークを確認することをお勧めします。

  1. エクスストリーム
  2. JAXB
  3. XML Bean

XOM に満足している場合は、別の場所に移動する必要はありませんが、インデックスを使用するなど、検索時にデータの構造を考慮するか、効率的な形式 (たとえば、プレフィックス) でデータを格納する必要があると思います。ツリー/トライ - そしてそれをディスク/ストレージにシリアル化して、明らかなスペース/時間のトレードオフを介して再解析を高速化しますか?

さらに、データはXML である必要がありますか? 別のフォーマットに変換できますか？Protocol Buffers やデータベース (SQL または NoSQL) へのデータの配置など。

また、次の質問も自問します。

  1. このデータを取得するにはどうすればよいですか? 検索に役立つ可能性のある情報を失っていますか?
  2. 効率的な検索アルゴリズムはここで役立ちますか?
  3. このデータはソートされていますか? 後続のルックアップがより効率的になるように、効率的に並べ替えることができますか?
于 2013-09-18T11:00:21.190 に答える
0

ハッシュテーブルを使用してデータを保存しました。各タイプのハッシュ テーブルを作成しました。各ハッシュ テーブルのキーは、チェックしたいすべての属性の連結であり、格納された値は取得したいものです。非常に効率的で、O(1) に近い

于 2013-09-18T16:35:24.500 に答える