4

そこで、私は独自の二分探索ツリーを実装していましたが、私がやっている方法では醜い if ステートメントがあまりにも頻繁に現れることに気付きました (これはおそらく最善の方法ではありませんが、それは私たちが議論しているものではありません)。ノードの子は左または右の子です。例:

if (leftChild)
    parent.setLeft(child.getRight());
else
    parent.setRight(child.getRight());

それから私はこれを考えました：

parent.setChild(childIndex, child.getRight());

ここで、childIndex は、leftChild が決定された場所で以前に決定されたバイトです。

ご覧のとおり、これははるかに簡潔ですが、このようにするには、setChild メソッドに if ステートメントを含めるか、子を長さ 2 の配列として表す必要があります。ここで、この BST には最大のパフォーマンスが必要であると仮定するとスペース効率、変数のペアではなく、子ノード参照のストレージを 2 要素配列に切り替える (または単に setChild メソッド内の if ステートメントを非表示にする) と、どのようなトレードオフになるでしょうか。

現実の状況では、これはそれほど重要ではないことはわかっていますが、どの方法が最善の方法であるかについてはまだ関心があります。

4

2 に答える 2

10

私が理解しているように、次の2つのうちどちらがより効率的かを尋ねています。

if (condition)
    x = value
else
    y = value

と

xyArray[index] = value

まず第一に、JLSはどのタイプのステートメントの実行時間も言及していないため、答えはコンパイラーおよび/またはJVMの実装に依存します。

そうは言っても、JVMは配列オフセットを計算して配列境界をチェックする必要がないため、-statementの方がわずかに高速になると思います。if

いずれにせよ、これは時期尚早の最適化のように思えます。どちらが読みやすく、デバッグしやすいかに基づいてアプローチを選択してください。

于 2012-07-18T08:33:29.573 に答える
1

2つのフィールドとして格納する場合、1つだけではなくif、コードがそれらとともにクロールすることになると思います。おそらくif、より効率的であり、さらに別のヒープ割り当てオブジェクト（通常のオーバーヘッドを伴う完全なオブジェクト）の代わりに2つのフィールドを持つことは、メモリ的にもより効率的です。ツリーが本当に、本当に巨大になる（数百万のノード）場合、これは懸念事項です。また、各ノードのペイロードがオーバーヘッドと比較して小さい場合。

于 2012-07-18T08:41:31.627 に答える