指で探す

コンピュータ サイエンスでは、データ構造上のフィンガー検索は、その構造がサポートする検索操作の拡張であり、クエリとともにデータ構造内の要素への参照 (フィンガー) が与えられます。要素の検索時間は、データ構造内の要素数の関数として表現されることが多いですが、フィンガー検索時間は、要素とフィンガー間の距離の関数です。

n個の要素からなる集合において、 2 つの要素xとy の間の距離d ( x , y ) (または明確な場合は単にd )は、それらの順位の差である。xとyが構造内でi番目とj番目に大きい要素である場合、順位の差は | i - j | である。ある構造における通常の検索が通常 O(f( n )) 時間かかる場合、指yによるxの指検索は理想的には O(f( d )) 時間かかるはずである。d ≤ n であるため、最悪の場合でも指検索は通常の検索と同じくらいしか悪くないということに注意する。しかし、実際にはこれらの退化した指検索は通常の検索よりも多くの作業を行う。たとえば、 f( n ) が log( n ) であり、最悪の場合でも指検索は通常の検索の 2 倍の比較を行うとすると、 d > √ nの場合に指検索の方が遅くなる。したがって、指検索は、ターゲットが実際に指の近くにあると合理的に期待できる場合にのみ使用すべきである。

一般的なデータ構造の中には、実際の構造に追加の変更を加えずにフィンガー検索をサポートするものがあります。要素xの検索がxが見つかる範囲を狭めることによって実行される構造では、 yからのフィンガー検索は通常、検索範囲がx を含むのに十分な大きさになるまでyからの検索プロセスを逆に実行することによって実行されます。その時点で、検索は通常どおり続行されます。

リンク リストでは、通常、一方の端からもう一方の端まで移動して要素を線形に検索します。リンク リストがソートされていて、y を含むノードへの参照がある場合は、 yから検索を開始することで、O( d ) 時間でx を見つけることができます。

ソートされた配列 Aでは、通常、二分探索を使用してA内の要素xを検索します。フィンガー探索は、 A [ j ] = yから片側探索を実行することによって実現されます。二分探索では各比較後に探索空間が半分になりますが、片側探索では各比較後に探索空間が 2 倍になります。具体的には、片側探索のk回目の反復 ( x > yと仮定) では、検討中の区間はA [ j , j +2 ^{k -1 ] です。} A [ j + 2 ^{k -1} ] ≥ xになるとすぐに拡張が停止し、この時点でこの区間でxの二分探索が行われます。

片側検索でx を含む区間を見つけるのにk回の反復が必要な場合、d > 2 ^{k -2}となります。この範囲のバイナリ検索にもさらにk回の反復が必要です。したがって、 yからx をフィンガー検索するにはO( k ) = O(log d ) の時間がかかります。

スキップリストでは、この点から検索を続けるだけで、要素y を含むノードからxをフィンガー検索できます。 x < yの場合は検索が逆方向に進み、x > yの場合は検索が順方向に進むことに注意してください。 逆方向の場合はスキップリストの通常の検索と対称的ですが、順方向の場合は実際にはより複雑です。 通常、スキップリストの検索は、リストの先頭のセンチネルが最も高いノードと同じ高さであるため、高速になると予想されます。 ただし、フィンガーは高さ 1 のノードである可能性があります。 このため、検索中に登る場合がありますが、これは通常は決して発生しません。 ただし、この複雑さがあっても、期待される検索時間は O(log d ) です。^[1]

トレップはランダム二分探索木(BST) です。トレップでの検索は、他の BST で要素を検索するのと同じです。ただし、トレップには、距離dの 2 つの要素間の期待パス長がO(log d ) であるという特性があります。したがって、 y を含むノードからxをフィンガー検索するには、 yからツリーを登ってxの祖先が見つかるまで進み、その時点で通常の BST 検索が通常どおり続行されます。ノードが別のノードの祖先であるかどうかを判断するのは簡単ではありませんが、この形式のクエリをサポートするようにツリーを拡張して、期待される O(log d ) のフィンガー検索時間を実現できます。^[1]

ロープ (データ構造)の実装では、通常、文字列をトラバースするためのコード位置反復子を実装します。反復子は、文字列の特定の文字を指す指と見ることができます。ほとんどのバランスのとれたツリーと同様に、ロープは、ツリーのルートのみが与えられた場合、ツリーの 1 つのリーフのデータを取得するのに O( log( n )) 時間かかります。ツリーのすべてのリーフを読み取るには、O( n *log( n )) 時間かかるように見えます。ただし、少し余分な情報を格納することで、反復子を使用して「次の」リーフを O(1) 時間で読み取り、ツリーのすべてのリーフを O( n ) 時間で読み取ることができます。ロープの実装では、通常、ルートから反復子の現在のノード位置までのパス全体に関する「余分な情報」をキャッシュします。ツリー データ構造の他の実装では、ツリー自体に「余分な情報」を格納することがあります。各ノードにその親または後続ノードへのポインタを格納し (各ノードの通常の子へのポインタに加えて)、反復子に現在のノード位置のみを格納します。^{[2] [3]}

指検索を反復的にO ( f ( d )) 時間で実行できる場合、各反復にO (1) 時間かかるため、 c 本の異なる指を用意すれば、指検索をO ( c min{ d ( x , y1 ),..., d ( x , yc )}) 時間で実行できます。これは、 c本すべての指の検索を開始し、最初の指が終了するまで 1 ステップずつ前方に反復すること _{で実現されます。}

m回のアクセスの任意のシーケンスA = [ a ₁ , ..., a _m ]が与えられたとき、 Aの実行時間が である場合、構造は固定フィンガーfに対して静的フィンガー特性を持つと言われます。スプレイ木は、十分に大きなアクセスシーケンスに対して追加の処理を行わずに、任意のfの選択に対してこの特性を持ちます。 ^[4]${\displaystyle O\left(\sum _{i=1}^{m}\log d(f,a_{i})\right)}$

フィンガー検索は、以前の検索ですでに行われた作業を再利用するために使用できます。たとえば、データ構造内の要素を反復処理する方法の 1 つは、順番にフィンガー検索することです。この場合、1 つのクエリのフィンガーは、最後のクエリの結果の場所です。検索が最後の検索の近くで頻繁に行われることがわかっている場合は、これを内部的に実行してデータ構造を最適化できます。

フィンガー検索ツリーは、フィンガーを指定できるデータ構造の一種で、フィンガーの近くの場所にアクセスしたり変更したりするときに、サポートされている操作のすべてまたは一部が高速化されます。この記事で説明されているフィンガー検索とは対照的に、これらのフィンガーはクエリ時に提供されず、将来のすべての操作でこれらのフィンガーが使用されるように個別に指定されます。これの利点の 1 つは、ユーザーが構造への内部参照を操作または保存する必要がなく、構造内の要素を指定するだけで済むことです。