最近、配列を3つの部分に分割して比較する3値検索について聞いたことがあります。ここでは2つの比較がありますが、配列はn/3に減少します。どうしてこんなに使わないの？
質問する
20482 次
15 に答える
44
実際、人々は任意の k に対して k-ary ツリーを使用します。
ただし、これはトレードオフです。
k-ary ツリーで要素を見つけるには、k*ln(N)/ln(k) 操作が必要です (基数の変更式を思い出してください)。k が大きいほど、必要な全体的な操作が多くなります。
あなたが言っていることの論理的な拡張は、「N個のデータ要素にN分木を使用しないのはなぜですか?」です。もちろん、これは配列になります。
于 2010-08-17T00:14:20.747 に答える
26
三元検索でも、同じ漸近的な複雑さO（log N）の検索時間が得られ、実装が複雑になります。
クワッド検索やその他の高階関数が必要ない理由についても、同じ議論が言えます。
于 2010-08-17T00:12:48.067 に答える
25
10 億 (米国の 10 億 - 1,000,000,000) の並べ替えられたアイテムを検索するには、二分検索と比較して平均約 15 回、三分検索と比較して約 9 回の比較が必要です。これは大きな利点ではありません。また、各「三項比較」には 2 つの実際の比較が含まれる場合があることに注意してください。
于 2010-08-17T00:19:31.650 に答える
10
わお。投票数の多い回答は、これに関するボートを見逃していると思います。
お使いの CPU は、3 値ロジックを単一の操作としてサポートしていません。三値論理を二進論理のいくつかのステップに分割します。CPU に最適なコードはバイナリ ロジックです。1 つの操作として 3 値ロジックをサポートするチップが一般的だったとしたら、その通りです。
B ツリーは、各ノードに複数のブランチを持つことができます。次数 3 の B ツリーは 3 項論理です。ツリーを下るたびに、1 回ではなく 2 回の比較が行われるため、CPU 時間が遅くなる可能性があります。
ただし、B ツリーはかなり一般的です。ツリー内のすべてのノードがディスク上のどこかに個別に格納されると仮定すると、ディスクからの読み取りにほとんどの時間を費やすことになります...そして、CPU はボトルネックにはなりませんが、ディスクはボトルネックになります。したがって、ノードごとに 100,000 の子を持つ B ツリー、またはメモリの 1 ブロックにほとんど収まらないものを使用します。この種の分岐係数を持つ B ツリーのノードの高さが 3 つを超えることはめったになく、非常に膨大なデータセットを検索するために 3 回のディスク読み取り (ボトルネックでの 3 回の停止) しかありません。
レビュー:
- 三分木はハードウェアでサポートされていないため、実行速度が遅くなります。
- 大規模なデータセットのディスク最適化では、次数が 3 をはるかに超える B トレスが一般的です。2 を超えたら 3 を超えます。
于 2010-08-19T19:56:05.760 に答える
8
三元検索をもっと速くすべきだと思う理由は何ですか？
比較の平均数：
in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
比較の最悪の数：
in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
したがって、3値検索の方が悪いようです。
于 2010-08-17T01:03:36.073 に答える
8
三分探索が二分探索より高速になる唯一の方法は、2 方向比較の約 1.55 倍未満のコストで 3 方向分割決定を実行できる場合です。アイテムが並べ替えられた配列に格納されている場合、3 方向の決定は平均して 2 方向の決定の 1.66 倍のコストがかかります。ただし、情報がツリーに格納されている場合、情報をフェッチするコストは、実際に比較するコストに比べて高くなります。キャッシュの局所性とは、関連するデータのペアをランダムにフェッチするコストが、単一のデータをフェッチするコストよりもそれほど悪くないことを意味します。データム、三分木または n-way ツリーは、効率を大幅に改善する可能性があります。
于 2010-08-17T02:09:26.463 に答える
5
また、このシーケンスは、続行すると線形検索に一般化されることに注意してください
Binary search
Ternary search
...
...
n-ary search ≡ linear search
したがって、n-ary検索では、最大n個の実際の比較を行う可能性のある「1つだけのCOMPARE」があります。
于 2010-08-17T04:48:47.380 に答える
2
「三項」（三項？）検索は、最初の要素（または最初に行う比較に応じて、おそらく最後の要素）の検索を含む最良のケースでより効率的です。最初にチェックしている要素の末尾から遠い場合、2 つの比較では配列が毎回 2/3 ずつ狭められますが、同じ 2 つの二分探索の比較では検索空間が 3/4 ずつ狭められます。
それに加えて、二分探索の方が簡単です。最初の 3 分の 1 未満の場合は比較し、2 番目の 3 分の 1 未満の場合は比較し、最後の 3 分の 1 を取得します。
于 2010-08-17T00:17:50.337 に答える
1
二分探索木に関するほとんどすべての教科書や Web サイトでは、二分木については実際には語られていません。彼らは三分探索木を見せてくれます！真の二分木は、データを内部ノードではなくリーフに格納します (ナビゲートするキーを除く)。これらをリーフ ツリーと呼び、教科書に示されているノード ツリーを区別する人もいます。
J. Nievergelt、C.-K. Wong: バイナリ ツリーの合計パス長の上限、Journal ACM 20 (1973) 1–6。
これに関する次の記述は、Peter Brass のデータ構造に関する本からのものです。
2.1 検索木の 2 つのモデル
上記の概要では、最初は些細なことのように思える重要な点を省略しましたが、実際には、検索ツリーの 2 つの異なるモデルにつながります。どちらも以下の資料の多くと組み合わせることができますが、そのうちの 1 つが強く推奨されます。
各ノードでクエリ キーとノードに含まれるキーを比較し、クエリ キーが小さい場合は左の分岐をたどり、クエリ キーが大きい場合は右の分岐をたどると、それらが等しい場合はどうなるでしょうか。検索ツリーの 2 つのモデルは次のとおりです。
クエリ キーがノード キーよりも小さい場合は、左の分岐を使用します。それ以外の場合は、木の葉に到達するまで、右の枝に進みます。ツリーの内部ノードのキーは比較専用です。すべてのオブジェクトは葉にあります。
クエリ キーがノード キーよりも小さい場合は、左の分岐を使用します。クエリ キーがノード キーより大きい場合は、右の分岐を選択します。それらが等しい場合、ノードに含まれるオブジェクトを取得します。
この些細な点は、多くの結果をもたらします。
{ モデル 1 では、基になるツリーはバイナリ ツリーですが、モデル 2 では、各ツリー ノードは実際には、特別な中間隣接ノードを持つ 3 値ノードです。
{ モデル 1 では、各内部ノードに左と右のサブツリー (それぞれがおそらくツリーのリーフ ノード) がありますが、モデル 2 では、左または右のサブツリーが欠落している可能性のある不完全なノードを許可する必要があり、比較オブジェクトとキーが存在することが保証されます。
したがって、モデル 1 の検索ツリーの構造は、モデル 2 の検索ツリーの構造よりも規則的です。これは、少なくとも実装に関しては明らかな利点です。
{ モデル 1 では、内部ノードのトラバースに必要な比較は 1 回だけですが、モデル 2 では、3 つの可能性を確認するために 2 回の比較が必要です。
実際、モデル 1 と 2 の同じ高さのツリーには、最大でほぼ同じ数のオブジェクトが含まれますが、ツリーの最も深いオブジェクトに到達するには、モデル 2 で 2 倍の比較が必要です。もちろん、モデル 2 では、はるかに早く到達するオブジェクトもいくつかあります。ルート内のオブジェクトは 2 回の比較のみで検出されますが、ほとんどすべてのオブジェクトが最深レベルまたはその近くにあります。
定理。高さ h のモデル 1 のツリーには、最大で 2^h 個のオブジェクトが含まれます。高さ h のモデル 2 の木には、最大で 2^h+1 − 1 個のオブジェクトが含まれます。
これは、高さ h の木が左と右の部分木としてそれぞれ最大で h − 1 の高さの木を持ち、モデル 2 ではそれらの間に 1 つの追加オブジェクトがあるため、簡単にわかります。
{ モデル 1 では、内部ノードのキーは比較のためにのみ機能し、オブジェクトの識別のために葉に再表示される場合があります。モデル 2 では、各キーはそのオブジェクトと共に 1 回だけ表示されます。
モデル 1 では、オブジェクトが削除された場合など、どのオブジェクトにも属さない比較に使用されるキーが存在する可能性さえあります。比較と識別のこれらの機能を概念的に分離することによって、これは驚くべきことではありません。後の構造では、探索空間を適切に分割するためだけに、どのオブジェクトにも対応しない人為的なテストを定義する必要さえあるかもしれません。モデル 1 ツリーでは、各内部ノードに空でない左右のサブツリーがあるため、比較に使用されるすべてのキーは必然的に異なります。そのため、各キーは多くても 2 回発生します。1 回は比較キーとして、もう 1 回はリーフ内の識別キーとして発生します。
ほとんどの教科書では、オブジェクトとそのキーが区別されていないため、モデル 2 が推奨される教科書バージョンになりました。キーはオブジェクトです。すると、木構造でキーを複製するのが不自然になります。しかし、すべての実際のアプリケーションでは、キーとオブジェクトの区別が非常に重要です。数字のセットだけを追跡したいと思うことはほとんどありません。数字は通常、いくつかの追加情報に関連付けられており、多くの場合、キー自体よりもはるかに大きくなります。
于 2014-09-13T16:42:04.907 に答える
1
これは、二分探索よりも遅いことを示す、まったく精査していないランダムな実験的証拠です。
于 2010-08-17T00:13:53.367 に答える
0
両方の検索ツリーで同じ big-O の複雑さ (ln n) が得られますが、違いは定数にあります。各レベルで三分探索木の比較をさらに行う必要があります。そのため、差は k-ary 探索木の k/ln(k) に要約されます。これは e=2.7 で最小値を持ち、k=2 で最適な結果が得られます。
于 2015-10-29T01:22:34.557 に答える
0
理論的には、最小値はek/ln(k)で達成され、3 は 2 よりもeに近いため、必要な比較は少なくなります。二分探索が高速になる理由は、そのコードの分岐が少なくなり、最新の CPU でより高速に実行されるためです。3/ln(3) = 2.73..2/ln(2) = 2.88..
于 2010-08-18T20:48:06.707 に答える
0
天秤で物を量る謎解きで三分探索が使われているのを聞いたことがあるかもしれません。これらのスケールは 3 つの答えを返すことができます: 左が軽い、両方が同じ、または左が重いです。したがって、三項検索では、比較は 1 回だけです。ただし、コンピューターはブール論理を使用するため、答えは 2 つしかありません。三分探索を行うには、実際には 1 回ではなく 2 回の比較を行う必要があります。以前の投稿者が言及したように、これはまだ高速な場合があると思いますが、三分探索が常に優れているとは限らないことがわかります。コンピュータに実装するのはより混乱し、不自然です。
于 2010-08-17T05:22:58.623 に答える