14

三分木がハッシュテーブルよりも優れているかどうかを知る必要があります。

この質問に出くわしたのは、別の質問への回答で、三分木はハッシュ テーブルよりも高速であることが多いと誰かが言ったときでした。信じがたいことだったので、少し調べてみることにしました。

プリンストンからのこの 1 つの Web サイトは、信念の源のようです。O(log n + k) と記述されているアルゴリズムを調べました。ここで、n は格納されている単語の数、k はキーの長さです。

これを高速化する唯一の方法は、まだ保存されていない要素を頻繁に検索する場合です。私を悩ませているもう 1 つのことは、トライの非連続的なクロールにより、スワップ アウトされたページにヒットする傾向があることですが、これが大きな影響であるかどうかは、ベンチマークによってのみ確認できます。

どちらにもおそらく長所と短所があることがわかったので、もしそうなら、それらが何であるかを知りたい. ベンチマークも役立ちます。

4

5 に答える 5

7

これは、あなたが提供したプリンストンのリンクから到達可能なドブス博士の記事から収集したものです。

  1. 一部の検索問題では、三分探索木はハッシュ テーブルよりも最大 10% 高速です。使用するマシンに大きく依存しますが、速度が遅くなることがあります。
  2. TRT は、コンピュータ サイエンスの最も優れた 2 人の頭脳によって調整されたカスタム データ構造です。Jon Bentley と Robert Sedgewick はどちらも優れた 教科書を書き、実践的なプログラミングの分担を行っています。ハッシュ テーブルはありふれたものと見なされます。
  3. Hao Wooi Lin が言うように、関連する定数は重要です。
  4. 全体として、これは解決しようとしている問題によって異なります。多くの場合、開発時間の短縮と、多くのプログラミング言語でのハッシュ テーブルのほぼすべてのサポートは、実行時間の 10% の改善よりも重要です。
于 2009-05-05T07:53:56.400 に答える
4

この質問に答える唯一の方法は経験的にです。答えは、実装の詳細、実行する検索の種類、使用しているハードウェア、および使用しているコンパイラによって異なります。Princeton から C コードをコピーできます。関数型言語を試してみたい場合は、標準 ML にハッシュ テーブルがあり ( SML/NJを参照)、三分探索木用の ML を次に示します。

type key = Key.ord_key
type item = Key.ord_key list

datatype set = NODE of { key : key, lt : set, eq : set, gt : set }
             | LEAF

val empty = LEAF

fun member (_, LEAF) = false
  | member (h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => member(t, eq)
          | LESS    => member(h::t, lt)
          | GREATER => member(h::t, gt))
  | member ([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => true
          | LESS    => member([], lt)
          | GREATER => member([], gt))

exception AlreadyPresent

fun insert(h::t, LEAF) =
      NODE { key = h, eq = insert(t, LEAF), lt = LEAF, gt = LEAF }
  | insert([], LEAF) =
      NODE { key = Key.sentinel, eq = LEAF, lt = LEAF, gt = LEAF }
  | insert(h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => NODE {key = key, lt = lt, gt = gt, eq = insert(t, eq)}
          | LESS    => NODE {key = key, lt = insert(h::t, lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert(h::t, gt), eq = eq})
  | insert([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => raise AlreadyPresent
          | LESS    => NODE {key = key, lt = insert([], lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert([], gt), eq = eq})

fun add(l, n) = insert(l, n) handle AlreadyPresent => n
于 2009-05-07T03:16:22.553 に答える
1

log(n) はゆっくりと十分に成長するため、定数係数を考慮すると、O(1) アルゴリズムよりも遅くなる前に大量のデータが必要になることがよくあります。

于 2009-05-05T08:02:56.220 に答える
0

tstdb を参照してください: http://code.google.com/p/tstdb/

この kv-store は三分探索木に基づいており、Memcached と互換性があります。さらに、tstdb は、Ternary Search Tree によって促進されるプレフィックス検索と範囲クエリをサポートします。

于 2012-03-04T06:57:48.167 に答える
0

これは私もかなり興味をそそられます。しかし、私が読んだ wiki によると、ほとんどの検索問題では 3 項ツリーの方が高速であると主張していました。これは驚くべきことではありません。ハッシュ テーブルには O(1) ルックアップがありますが、ハッシュを行うにはまだ時間が必要だからです。つまり、実際には O(1) ではなく、k が N (データ構造内の項目の数) に依存しない O(k) に似ています。これは、Hash Table の方が速いという印象を与えるかもしれません。ただし、大きな構造を扱っている場合、k はすぐに加算され、Hash Table の検索速度が Ternary Tree よりも遅くなるポイントが来ます。

于 2009-05-05T07:45:38.057 に答える