Splay tree実生活アプリケーション

Question

ここでは、実稼働環境でsplay-treeを使用しますか？私は、リアルライフの例を意味します。

私は試行とスプレイツリーを使ってオートコンプリートを実装しようと考えていました。大規模なデータセットの場合、結果を返すためにノードxから葉までトライを通過するのは良い考えではないので、ユーザーは「sta」を入力するとstaに移動します、 'a' - ノードを作成し、スプレイツリーの上位5個の要素を返します（必ずしもツリーを変更/変更するわけではありませんが、BFS /レベルのトラバースによって）

もちろん、オートコンプリートバリアントが選択された後、トライをトラバースし、それらのノード内のすべてのスプレイツリーを更新する。スプレー木以来

は、私は生産に

あなたのアイデアをその使用状況を問うた同時環境に敏感ですか？

Answer 1

特に、スレッド環境では、ほとんどまたはまったく変更されないデータに対して、スプレイツリーはよく一致しません。読取り操作中の追加の突然変異は、メモリー・キャッシュを無効にし、不要なロック競合を作成する可能性があります。いずれにしても、読み取り専用データ構造の場合、最適なツリーの1回限りの計算を行うことができます。計算が遅い場合でも、長期実行時間に影響はありません。

大規模な試行が遅く、確かにオートコンプリートではないという主張によって完全に説得されていません。それほど現代的ではないハードウェアでも、ユーザーが文字を入力するのにかかる時間、または基礎となるキーボード・ドライバーと入力プロセッサーがキーを押すまでに要する時間に比べて、トライ・トラバーサルのコストはほとんどありませんあなたの申請。

トライを最適化する必要がある場合は、代替がキャッシュラインに収まるようになると、ルートでトライを持つハイブリッドデータ構造が線形（またはバイナリ）検索と組み合わされていると考えてよいでしょう。これにより、トライの大きなファンアウトの利点を最大限に引き出しながら、キャッシングの動作が貧弱になり、行の最後にストレージオーバーヘッドが過剰に発生することがなくなります。

スプレイツリーは、頻繁に変更されるデータ構造上で最も有用です（まったく便利な場合）。 ckassicの例は、 "ロープ"データ構造（文字列セグメントのツリー）です。これは、大きな文字列コピーを避けることによってテキストエディタを最適化する方法の1つです。 RBツリーのような決定論的なツリーバランシングアルゴリズムと比較して、スプレイツリーアルゴリズムは単純さの利点を有するだけでなく、ツリートラバーサルの一部を形成するノードに触れるだけである。

しかし、しばしば失望した経験的結果と組み合わされたセルフバランシングツリーライブラリ（現代の多くのプログラミング言語の標準ライブラリの一部）が用意されているため、スプレイアルゴリズムはせいぜいニッチな製品になりますが、確かに魅力的ですアイディア。