実装の詳細

ウィキペディア小見出し辞書

実装の詳細

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/12 19:08 UTC 版)

「スキップリスト」の記事における「実装の詳細」の解説

スキップリストで用いられる要素は1つ以上のポインタを含む可能性があるが、それは、1つ以上のリストに属している可能性があるからである。 挿入と削除は、連結リストの対応する操作と同様の実装になるが、"背の高い"要素は2つ以上の連結リストに対して挿入及び削除する必要がある。 また、全てのノードを昇順に訪れるような O ( n ) の操作において、裏でスキップリストのレベル構造のランダム性を取り除き、探索時間が O ( log ⁡ n ) である最適な構造に変えてもよい。（i番目のノードの高さをi=m*2^n（mは奇数）とした場合のnに1加えたものにする。また、i=0 は最大の高さとする。）しかし、この方法では誰かが何処に高い要素があるかを知ってそれをリストから削除することができる。 その代わりに、次のように高さを擬似的にランダマイズすることができる。最初に全てのノードの高さを1にする。次に各i番目のノードについて、奇数ならば高さを2にするかどうかをランダムに決める。偶数ならば直前のノードの高さが2になっていないときのみ高さを2にする。高くなったノードの数が2以上なら高さを上げてこれを繰り返す。ランダム性の削除と同様に、この擬似的なランダマイズはノードを全て訪れる場合にのみ実行する。 擬似的なランダマイズを行う利点は、ランダム性の無い場合と違い、敵意のあるユーザーに高さに関する情報を漏らさないことである。悪意あるユーザが高さに関する情報を知っていると、レベルの高いノードを削除するだけで性能を悪化させことができるため、この性質は望ましい。(これに対し、BetheaとReiterは、悪意あるユーザが性能劣化を起こすために、確率的タイミング方法を使用できると主張している。)検索時間については、ランダム性の無い場合と同様、対数時間であることが保証されている。 以下の「最適化」を考えてみよう。「次に, 各i番目のノードに対して・・・」の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを1回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。これで、コイン投げの回数は、 O ( n log ⁡ n ) でなく O ( log ⁡ n ) に削減できる。この方法では、悪意を持ったユーザが、ある1つのノードの高さを正しく推測できる確率は非常に低いにも関わらず、「全ての偶数番目のノードは高さが1より大きいだろう」という推測が50％の確率で当たってしまう。 スキップリストは、より伝統的な平衡木と同じ最悪時のパフォーマンスを保証しない。なぜなら、（確率はとても低いが）バランスの悪い構造になる場合が常にあるからである。しかし実際にはよく動作し、ランダム化されたバランスとりの仕組みは平衡二分探索木の決定論的なバランスとりの仕組みより実装が容易であることが示されている。スキップリストは並列計算においても有用で、挿入はスキップリストのいくつかの部分で並列に実施でき、全体のリバランスが不要である。この並列化は、アドホック無線ネットワークでのリソース探索において特に有用となりうる。なぜなら、ランダム性のあるスキップリストは単一ノード損失に対して堅牢にすることができるからである。

実装の詳細

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/14 03:52 UTC 版)

「ランタイム (プログラムライフサイクルフェーズ)」の記事における「実装の詳細」の解説

プログラムを実行する場合、ローダは最初に必要なメモリセットアップを実行し、プログラムを必要なダイナミックリンクライブラリにリンクする。次に、プログラムのエントリーポイントから実行を開始する。場合によっては、言語または実装では、代わりに言語ランタイムによってこれらのタスクが実行されるが、これは一般的なコンシューマーオペレーティングシステムの主流言語では珍しいことである。 一部のプログラムのデバッグは、実行時にのみ実行できる（または、実行するとより効率的または正確になる）。論理エラーと配列境界チェックはひとつの例である。このため、高度なコンパイル時チェックとプレリリーステストにもかかわらず、プログラムが実際のデータを使用して実稼働環境でテストされるまで、一部のプログラミングバグは発見されない。この場合、エンドユーザーは「ランタイムエラー」メッセージを受け取る可能性がある。