「スキップリスト」を編集中
表示
この編集を取り消せます。
下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を公開して取り消しを完了してください。
最新版 | 編集中の文章 | ||
94行目: | 94行目: | ||
検索時間については、ランダム性の無い場合と同様、対数時間であることが保証されている。 |
検索時間については、ランダム性の無い場合と同様、対数時間であることが保証されている。 |
||
以下の﹁最適化﹂を考えてみよう。﹁次に, 各i番目のノードに対して・・・﹂の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを1回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。これで、コイン投げの回数は、<math> \mathcal{O} ( n \log n ) </math> でなく <math> \mathcal{O} ( \log n ) </math> に削減できる。この方法では、悪意 |
以下の﹁最適化﹂を考えてみよう。﹁次に, 各i番目のノードに対して・・・﹂の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを1回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。これで、コイン投げの回数は、<math> \mathcal{O} ( n \log n ) </math> でなく <math> \mathcal{O} ( \log n ) </math> に削減できる。 しかし、この方法では、悪意あるユーザの﹁全ての偶数番目のノードは高さが1より大きいだろう﹂という推測が50%の確率で当たってしまう。悪意あるユーザが、ある1つのノードの高さを正しく推測できる確率は非常に低いにも関わらず。
|
||
<!-- これらの2つの主張を説明しよう。まず、検索が対数時間で終わることを示す。高さが1以上である全てのノードの中でn番目のノードを見つけることを考える。nが偶数であれば、その高さが1より大きい確率は1/2であるが、もしノードの高さが1であるならばn-1番目のノードの高さは1より大きいことが保証される。nが奇数であれば、その高さが1より大きい確率は1/2である。このときn番目のノードの高さが1でかつn-1番目のノードの高さも1であるとすると、n-2番目のノードの高さは1より大きいことが保証される。この解析を高さが2以上のノード、3以上のノード……と繰り返していく。それぞれの解析でnは高さがk以上であるようなノードの中で何番目であるかということを注意しておく。以上から、検索時間はランダマイズされていないスキップリストと比べて最良の場合︵探しているノードが考えうる限り最も高さが高いとき︶は同じで、最悪でも2倍となる︵左に1回ではなく2回動かなければならないため︶。-->
|
<!-- これらの2つの主張を説明しよう。まず、検索が対数時間で終わることを示す。高さが1以上である全てのノードの中でn番目のノードを見つけることを考える。nが偶数であれば、その高さが1より大きい確率は1/2であるが、もしノードの高さが1であるならばn-1番目のノードの高さは1より大きいことが保証される。nが奇数であれば、その高さが1より大きい確率は1/2である。このときn番目のノードの高さが1でかつn-1番目のノードの高さも1であるとすると、n-2番目のノードの高さは1より大きいことが保証される。この解析を高さが2以上のノード、3以上のノード……と繰り返していく。それぞれの解析でnは高さがk以上であるようなノードの中で何番目であるかということを注意しておく。以上から、検索時間はランダマイズされていないスキップリストと比べて最良の場合︵探しているノードが考えうる限り最も高さが高いとき︶は同じで、最悪でも2倍となる︵左に1回ではなく2回動かなければならないため︶。-->
|
||
101行目: | 101行目: | ||
<!-- 次に、敵意のあるユーザがどの程度の正確さでノードが高さk以上であるという想定ができるかを示す。まず、敵意のあるユーザはある特定のノードが高さ2以上であるかどうかを1/2の確率で当てることができる。もしそのユーザが2つの連続する高さが2以上のノードの位置を知っており、その2つのうち左側のノードが高さが2以上のノードの中で奇数番目であることがわかれば、そのユーザがどのノードが高さが3以上であるかを当てられる確率は1/2になる。したがって、高さが3以上のノードについてそのユーザの想定が正しいかどうかは1/4となる。この解析を帰納的に適用すると、ある特定のノードが高さk以上であるかどうかを当てることができる確率は1/(2^(k-1))である。-->
|
<!-- 次に、敵意のあるユーザがどの程度の正確さでノードが高さk以上であるという想定ができるかを示す。まず、敵意のあるユーザはある特定のノードが高さ2以上であるかどうかを1/2の確率で当てることができる。もしそのユーザが2つの連続する高さが2以上のノードの位置を知っており、その2つのうち左側のノードが高さが2以上のノードの中で奇数番目であることがわかれば、そのユーザがどのノードが高さが3以上であるかを当てられる確率は1/2になる。したがって、高さが3以上のノードについてそのユーザの想定が正しいかどうかは1/4となる。この解析を帰納的に適用すると、ある特定のノードが高さk以上であるかどうかを当てることができる確率は1/(2^(k-1))である。-->
|
||
スキップリストは、より伝統的な |
スキップリストは、より伝統的な平衡木と同じ最悪時のパフォーマンスを保証しない。なぜなら、(確率はとても低いが)バランスの悪い構造になる場合が常にあるからである。しかし実際にはよく動作し、ランダム化されたバランスとりの仕組みは平衡二分探索木の決定論的なバランスとりの仕組みより実装が容易であることが示されている。スキップリストは[[並列計算]]においても有用で、挿入はスキップリストのいくつかの部分で並列に実施でき、全体のリバランスが不要である。この並列化は、アドホック無線ネットワークでのリソース探索において特に有用となりうる。なぜなら、ランダム性のあるスキップリストは単一ノード損失に対して堅牢にすることができるからである。 |
||
<!-- メモリアクセスの局所性の問題やその他の問題のため、スキップリストが実際の性能とメモリ効率において[[B木]]より悪いという証拠が存在する([http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html])。--> |
<!-- メモリアクセスの局所性の問題やその他の問題のため、スキップリストが実際の性能とメモリ効率において[[B木]]より悪いという証拠が存在する([http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html])。--> |