三元検索がある場合、なぜバイナリ検索を使用するのですか？
https://stackoverflow.com/questions/3498382
-
29-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は最近、3つの部分に配列を分割して比較する三元検索について聞いた。ここでは、2つの比較がありますが、配列をn/3に減らします。なぜ人々はそんなに使わないのですか？
解決
実際、人々は任意のkにk-aryツリーを使用しています。
ただし、これはトレードオフです。
k-aryツリーで要素を見つけるには、K*ln（n）/ln（k）操作の周りに必要です（ベースの変化式を覚えておいてください）。 Kが大きいほど、必要な全体的な操作が増えます。
あなたが言っていることの論理的拡張は、「なぜ人々はnデータ要素にn-aryツリーを使用しないのですか？」です。もちろん、これは配列になります。
他のヒント
三元検索は、同じ漸近的な複雑さを引き続き提供します o（log n） 検索時間、および実装に複雑さを追加します。
クワッド検索やその他の高次を望まない理由について、同じ議論が言えます。
10億（米国10億から1,000,000,000）のソートされたアイテムを検索すると、バイナリ検索と平均約15の比較が必要であり、約9が3成分検索と比較しますが、大きな利点ではありません。また、各「三元比較」には2つの実際の比較が含まれる場合があります。
わお。最上位の回答は、これでボートを逃したと思います。
CPUは、単一の操作として三元ロジックをサポートしていません。それは、三元ロジックをバイナリロジックのいくつかのステップに分割します。 CPUの最も最適なコードは、バイナリロジックです。単一の操作として三元ロジックをサポートするチップが一般的であれば、あなたは正しいでしょう。
Bツリーは、各ノードに複数の分岐を持つことができます。注文-3 Bツリーは三元ロジックです。ツリーの各ステップが1つではなく2つの比較が必要になり、おそらくCPU時間で遅くなります。
ただし、Bツリーはかなり一般的です。ツリー内のすべてのノードがディスク上に個別に保存されると仮定すると、ほとんどの時間をディスクから読み取ります...そしてCPUはボトルネックにはなりませんが、ディスクはそうになります。したがって、ノードあたり100,000人の子供を持つB-Treeを取得します。 かろうじて メモリの1つのブロックに収まります。この種の分岐係数を持つBツリーは、3つのノードを3つ以上高くすることはめったになく、ボトルネックに3つのディスク読み取り（3つのストップ）があり、巨大な巨大なデータセットを検索します。
レビュー：
- 三元ツリーはハードウェアでサポートされていないため、速度が低下します。
- 注文が大きく、3よりもはるかに高いB-Stressは、大きなデータセットのディスク最適化に一般的です。 2を過ぎて行ったら、3を超えて行きます。
3ウェイパーティションの決定を2ウェイ比較の約1.55倍未満で実行できる場合、バイナリ検索よりも高速になる唯一の方法は、バイナリ検索です。アイテムがソートされた配列に保存されている場合、3方向の決定は平均で2ウェイの決定のように1.66倍高価になります。ただし、情報がツリーに保存されている場合、情報を取得するためのコストは実際に比較するコストに比べて高く、局所性をキャッシュすることは、関連データのペアをランダムに取得するコストが1つのコストを取得するコストよりもそれほど悪くないことを意味します。データム、三元またはnウェイツリーは、効率を大幅に改善する可能性があります。
三元検索はより速くなるはずだと思う理由は何ですか？
比較の平均数：
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).
したがって、三元検索は悪いようです。
また、このシーケンスは、続行すれば線形検索に一般化することに注意してください
Binary search
Ternary search
...
...
n-ary search ≡ linear search
したがって、n-ary検索では、実際の比較に至るまでの「唯一の比較」があります。
「Terinary」（Ternary？）検索は、最初の要素を検索することを伴う最良のケースでより効率的です（または、最初の比較に応じて最後の要素を検索します）。最後から遠く離れた要素の場合、最初にチェックしていますが、2つの比較によりアレイが2/3に狭くなります。
それに加えて、バイナリ検索はより簡単です。最初の3分の1を取得するのではなく、比較するのではなく、1つを比較して取得します。
三元検索は、並列アーキテクチャ（FPGAおよびASIC）で効果的に使用できます。たとえば、検索に必要な内部FPGAメモリがFPGAリソースの半分未満である場合、複製メモリブロックを作成できます。これにより、2つの異なるメモリアドレスに同時にアクセスし、単一のクロックサイクルですべての比較を実行できます。これが、100MHz FPGAが4GHz CPUを上回ることがある理由の1つです:)
これがそうです 私がまったく吟味していないというランダムな実験的証拠 バイナリ検索よりも遅いことを示しています。
バイナリ検索ツリーのほとんどすべての教科書やウェブサイトは、バイナリツリーについて実際には話していません！彼らはあなたに三元の検索ツリーを見せます！真のバイナリツリーは、内部ノードではなく葉にデータを保存します（ナビゲートするキーを除く）。これらの葉の木を呼び出して、教科書に示されているノードツリーを区別します。
J. Nievergelt、C.-K。ウォン：バイナリツリーの合計パス長の上限、Journal ACM 20（1973）1–6。
これに関する以下は、データ構造に関するPeter Brassの本からのものです。
2.1検索ツリーの2つのモデル
ちょうど与えられたアウトラインでは、最初は些細なように見える重要な点を抑えましたが、実際には検索ツリーの2つの異なるモデルにつながるという重要な点を抑えました。
各ノードでクエリキーをノードに含むキーと比較し、クエリキーが小さい場合は左ブランチに従って、クエリキーが大きい場合は右ブランチに従うと、等しい場合はどうなりますか？検索ツリーの2つのモデルは次のとおりです。
クエリキーがノードキーよりも小さい場合は、左ブランチを取ります。そうでなければ、木の葉に到達するまで、正しい枝を取ります。ツリーの内部ノードのキーは比較のためだけです。すべてのオブジェクトは葉の中にあります。
クエリキーがノードキーよりも小さい場合は、左ブランチを取ります。クエリキーがノードキーよりも大きい場合は、右のブランチを取ります。ノードが等しい場合は、ノードに含まれるオブジェクトを取ります。
このマイナーなポイントには多くの結果があります。
{モデル1では、下にあるツリーはバイナリツリーですが、モデル2では、各ツリーノードは実際には特別な中央の隣人を持つ三元ノードです。
{モデル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の木には左右のサブツリーがそれぞれ最大の高さの木を持ち、モデル2にはそれらの間に1つの追加のオブジェクトがあるため、簡単にわかります。
{モデル1では、内部ノードのキーは比較のためにのみ機能し、オブジェクトの識別のために葉に再び現れることがあります。モデル2では、各キーはそのオブジェクトとともに一度だけ表示されます。
モデル1では、オブジェクトが削除されている場合など、オブジェクトに属さない比較に使用されるキーがあることも可能です。比較と識別のこれらの機能を概念的に分離することにより、これは驚くことではなく、後の構造では、検索スペースの適切な分割を取得するためだけに、オブジェクトに対応しない人工テストを定義する必要さえあります。モデル1ツリーでは、各インテリアノードには空でない左および右サブツリーがあるため、比較に使用されるすべてのキーは必然的に異なります。したがって、各キーは、比較キーとして1回、葉の識別キーとして1回、せいぜい2回発生します。
モデル2は、ほとんどの教科書でオブジェクトとそのキーの区別が作成されていないため、優先教科書のバージョンになりました。キーはオブジェクトです。その後、ツリー構造のキーを複製することは不自然になります。しかし、すべての実際のアプリケーションでは、キーとオブジェクトの区別は非常に重要です。一連の数字を追跡することはほとんどありません。数値は通常、いくつかのさらなる情報に関連付けられており、多くの場合、キー自体よりもはるかに大きくなります。
スケールで物事を計量することを含む謎での三元検索が使用されているのを聞いたことがあるかもしれません。これらのスケールは3つの回答を返すことができます：左は軽く、どちらも同じか、左が重いです。したがって、三元検索では、1つの比較のみが必要です。ただし、コンピューターはBooleanロジックを使用しており、2つの回答しかありません。三元検索を行うには、実際には1ではなく2つの比較を行う必要があります。以前のポスターが述べたようにこれがまだ速い場合がある場合がありますが、三元検索は必ずしも良いわけではないことがわかります。コンピューターに実装するのがより紛らわしく、自然ではありません。
理論的には最小限です k/ln(k) で達成されます e そして、3が近くにあるため e 2よりも比較が少なくなります。あなたはそれをチェックすることができます 3/ln(3) = 2.73.. と 2/ln(2) = 2.88.. バイナリ検索がより速くなる可能性がある理由は、そのコードの分岐が少なくなり、最新のCPUでより速く実行されるためです。
両方の検索ツリーで同じBig-Oの複雑さ（LN N）を取得しますが、違いは定数にあります。各レベルで3成分検索ツリーについてさらに比較する必要があります。したがって、違いはk/ln（k）に要約されます。これはE = 2.7で最小値を持ち、K = 2は最適な結果を提供します。
