8

複数のスレッドからのアクセスを簡素化するために、Javaで不変のDOMツリーを作成しています。*

ただし、可能な限り高速に挿入と更新をサポートする必要があります。また、不変であるため、ツリーのN番目のレベルのノードに変更を加えた場合、新しいツリーを返すには、少なくともN個の新しいノードを割り当てる必要があります。

私の質問は、ツリーが変更されるたびに新しいノードを作成するよりも、ノードを事前に割り当てる方が劇的に速いでしょうか？実行するのはかなり簡単です。数百の未使用ノードのプールを保持し、変更操作に必要なときにノードを作成するのではなく、プールから1つプルします。他に何も起こっていないときにノードプールを補充できます。（明らかでない場合は、このアプリケーションでは、ヒープスペースよりも実行時間がはるかに長くなります）

これを行う価値はありますか？それをスピードアップするための他のヒントはありますか？

あるいは、不変のDOMライブラリがすでにあるかどうか誰かが知っていますか？検索しましたが、何も見つかりませんでした。

*注：不変性の概念に精通していない場合は、基本的に、オブジェクトを変更する操作で、メソッドが変更されたオブジェクトではなく、変更されたオブジェクトのコピーを返すことを意味します物体。したがって、別のスレッドがまだオブジェクトを読み取っている場合、ひどくクラッシュするのではなく、変更が加えられたことに気付かずに、「古い」バージョンで問題なく動作し続けます。http://www.javapractices.com/topic/TopicAction.do?Id=29を参照してください

4

6 に答える 6

12

最近では、オブジェクトの作成は非常に高速であり、オブジェクトプーリングの概念はやや時代遅れになっています（少なくとも一般的には、接続プーリングはもちろん有効です）。

時期尚早の最適化は避けてください。コピーを行うときに必要なときにノードを作成し、それが非常に遅くなるかどうかを確認します。もしそうなら、それをスピードアップするためにいくつかのテクニックを調べてください。しかし、あなたが持っているものが十分に速くないことをすでに知っていない限り、私はあなたがプーリングを始めるために必要となるであろうすべての複雑さを紹介するつもりはありません。

于 2008-09-03T19:47:53.833 に答える
3

答えを出さないのは嫌ですが、このようなパフォーマンスの質問に答える唯一の決定的な方法は、両方のアプローチをコーディングし、2つをベンチマークし、結果を比較することだと思います。

于 2008-09-03T19:45:38.003 に答える
1

すべてがスレッドセーフであることを確認するために、特定のメソッドを明示的に同期することを避けることができるかどうかはわかりません。

新しく作成されたノードを他のスレッドで使用できるようにするために、一方または他方を同期する必要がある特定のケースがあります。そうしないと、VM/CPU が共有ノードへの参照の書き込みを過ぎてフィールドの書き込みを並べ替え、公開するリスクがあります。パーティ構築オブジェクト。

より高いレベルで考えてみてください。IMMUTABLE ツリー (基本的には、その子を指すノードのセット) があります。そこにノードを挿入します。その場合、抜け道はありません。新しい WHOLE ツリーを作成する必要があります。

子を指すノードのセットとしてツリーを実装することを選択した場合は、変更されたノードからルートへのパスに沿って新しいノードを作成する必要があります。その他は以前と同じ値を持ち、通常は共有されます。したがって、部分的な新しいツリーを作成する必要があります。これは通常、(編集されたノードの深さ) 親ノードを意味します。

直接的ではない実装に対処できる場合は、純粋に機能的なデータ構造で説明されているものと同様の手法を使用してノードの一部のみを作成して、作成の平均コストを削減するか、または-半機能的なアプローチを使用してそれを渡します (既存のイテレーターをラップするが、時間が経つにつれて構造内のそのようなパッチを修復するメカニズムと共に、古いノードではなく新しいノードを返すイテレーターを作成するなど)。その場合、XPath スタイルの API は DOM API よりも優れている可能性があります。ノードをツリーからもう少し分離し、変更されたツリーをよりインテリジェントに処理することができます。

于 2008-09-04T00:11:36.010 に答える
0

@Outlawには意味があると思います。DOMツリーの構造はノード自体にあり、その子を指すノードがあります。ツリーの構造を変更するには、ノードを変更する必要があるため、ノードをプールすることはできません。新しいノードを作成する必要があります。

より高いレベルで考えてみてください。IMMUTABLEツリー（基本的にはその子を指すノードのセット）があります。その中にノードを挿入したいとします。次に、抜け道はありません。新しい全体ツリーを作成する必要があります。

はい、不変ツリーはスレッドセーフですが、パフォーマンスに影響を与えます。オブジェクトの作成は高速である可能性がありますが、オブジェクトの作成がない場合よりも高速ではありません。:)

于 2008-09-03T20:42:44.450 に答える
0

そもそもあなたがやろうとしていることについて少し混乱しています。すべてのノードを不変にし、それらをプールしたいですか？これらの2つのアイデアは相互に排他的ではありませんか？プールからオブジェクトを引き出すとき、子をリンクするためにセッターを呼び出す必要はありませんか？

不変ノードを使用しても、そもそも必要な種類のスレッドセーフは得られないと思います。別のスレッドがノードを追加/削除しているときに、1つのスレッドがノード（検索など）を反復処理している場合はどうなりますか？検索結果は無効になりませんか？すべてがスレッドセーフであることを確認するために、特定のメソッドを明示的に同期することを回避できるかどうかはわかりません。

于 2008-09-03T19:59:59.797 に答える
0

@アウトロープログラマー

オブジェクトをプールから引き出すとき、セッターを呼び出して子をリンクする必要はありませんか?

各ノードは、パッケージに対して内部的に不変である必要はなく、外向きのインターフェイスに対してのみ不変である必要があります。node.addChild()パブリックな可視性を持つ不変の関数であり、ドキュメントを返しnode.addChildInternal()ますが、パッケージの可視性を持つ通常の可変関数です。ただし、これはパッケージの内部にあるため、の子孫としてのみ呼び出すことができaddChild()、構造全体がスレッド セーフであることが保証されます (オブジェクト プールへのアクセスを同期する場合)。これに欠陥があると思いますか...？もしそうなら、教えてください！

不変ノードを使用しても、そもそも必要な種類のスレッド セーフが得られない可能性があると思います。1 つのスレッドがノード (検索など) を反復処理しているときに、別のスレッドがノードの追加/削除を行っている場合はどうなりますか?

ツリーは全体として不変になります。Thread1 と Thread2、およびツリー dom1 があるとします。スレッド 1 は dom1 で読み取り操作を開始し、同時にスレッド 2 は dom1 で書き込み操作を開始します。ただし、Thread2 が行うすべての変更は、実際には新しいオブジェクト dom2 に対して行われ、dom1 は不変になります。Thread1 によって読み取られる値が (数マイクロ秒) 古くなっていることは事実ですが、IndexOutOfBounds または NullPointer 例外でクラッシュしたり、書き込まれている可変オブジェクトを読み取っていた場合にクラッシュしたりすることはありません。その後、Thread2 は、dom2 を含むイベントを Thread1 に対して起動し、必要に応じて再度読み取りを実行して結果を更新できるようにします。

編集：明確化

于 2008-09-03T20:25:49.220 に答える