グローバルを廃止しますか?

Question

深さが 20 年代の木のオブジェクトのセットがあります。このツリー内の各ノードは、そのツリーのルートにアクセスする必要があります。

いくつかの解決策:

1. 各ノードはルートへの参照を直接保存できます (メモリを無駄にします)
   • 「上に進む」ことで実行時にルートを計算できます（サイクルを無駄にします）
   • 静的フィールドを使用できます (ただし、これはグローバルになります)

グローバルを (あらゆるバリエーションで) 使用せず、メモリまたはサイクルの両方でそれぞれ #1 または #2 よりも効率的な設計を誰かが提供できますか?

編集： ツリーのセットがあるので、ツリーを区別するのが難しいため、単純にそれを静的に保存することはできません。(ありがとうマッカルト)

Answer 1

ルートを必要とするノード内の関数にパラメーターとしてルートを渡します。

編集：実際のオプションは次のとおりです。

1. ルート参照をノードに保存します
2. ルート参照をまったく保存しない
3. ルート参照をグローバルに保存する
4. ルート参照をスタックに保存します (私の提案、訪問者パターンまたは再帰的)

これはあらゆる可能性があると思いますが、選択肢 5 はありません。

Answer 2

なぜグローバルを廃止する必要があるのでしょうか?グローバルが悪いという偏見があることは理解していますが、場合によっては、すべての要素を含むグローバル データ構造を用意することが最も早い解決策であることもあります。

次のようなトレードオフを行います。コードが明確になり、将来のパフォーマンスの問題が軽減されます。それは「まだ最適化しないでください」という意味です。最適化の段階にあるため、場合によっては、パフォーマンスを優先して、読みやすさや優れたプログラミングの実践を一部省略する必要があります。つまり、ビットごとのハックは読み取れませんが、高速です。

あなたがどれだけのツリーオブジェクトを持っているかはわかりませんが、個人的にはオプション1を選択します。数千以上のツリーを扱っている場合を除き、ポインタは実際には数文字列以上にはなりません。メモリが本当に非常に重要な問題である場合は、両方の方法 (実装は非常に簡単なようです) を試し、プロファイラーを通して実行してください。または優れたものを使用してください プロセスエクスプローラー.

編集：私が取り組んでいるアプリの 1 つに、約 55,000 個のノードを含むノード ツリーがあります。ツリー構造を構築しますが、O(1) ルックアップ用の配列も維持します。再帰的な FindNodeByID メソッドを使用したときに得られた O(m*n) よりもはるかに優れています。

Answer 3

一般に、ルートをパラメータとして渡すことが最善です。ツリー内を移動するために何らかのイテレーターを使用している場合は、その中にルートへの参照を保存するという方法もあります。

Answer 4

ポイント 1 は、時期尚早なメモリの最適化です。#2 は時期尚早なパフォーマンスの最適化です。アプリのプロファイリングを行って、メモリまたは CPU のボトルネックが問題の原因となっているかどうかを判断しましたか?そうでない場合、ユーザーの役に立たない「最適化」のために、より保守しやすい設計を犠牲にする必要はありません。

#2 を使用することを強くお勧めします。代わりに計算できるものを保存するときは常に、実行していることはキャッシュです。キャッシュを使用するのが良い場合もありますが、メンテナンスが面倒になることもあります。(たとえば、親を変更してノードをあるツリーから別のツリーに移動したが、ルート フィールドの更新も忘れた場合はどうなりますか?) キャッシュする必要がない場合はキャッシュしないでください。

Answer 5

TreeView からクラスを派生させてから、シングルトンの静的プロパティを追加できます。こうすることで、クラスの単一インスタンスを参照するグローバル フィールドを効果的に追加することになりますが、名前空間のスコープがそのクラスになるという利点があります。

Answer 6

内部クラスに対する嫌悪感を無視して、Tree クラスを定義し、ノードを内部クラスとして定義することもできます。各ノードは、ルートを含むツリーの状態にアクセスできます。

Java がノードをその親にどのように関連付けるかによっては、これは #1 と同じになる可能性があります。(よくわからないのでプロファイリングする必要があります)