サイクル検出

コンピュータ サイエンスにおいて、サイクル検出またはサイクル発見は、反復された関数値のシーケンス内のサイクルを見つけるアルゴリズムの問​​題です。

有限集合S をそれ自身に写像する任意の関数 fと、S内の任意の初期値x ₀に対して、反復関数値のシーケンス

${\displaystyle x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots }$

結局、同じ値を 2 回使用する必要があります。つまり、x _i = x _jとなる異なるインデックスiとjのペアが存在する必要があります。これが発生すると、シーケンスはx _iからx _{j − 1}までの同じ値のシーケンスを繰り返すことにより、定期的に継続する必要があります。サイクル検出は、 fとx ₀が与えられたときにiとj を見つける問題です。

サイクルを素早く、少ないメモリで見つけるアルゴリズムはいくつか知られています。ロバート・W・フロイドのウサギとカメのアルゴリズムは、2 つのポインタを異なる速度で値のシーケンス内を移動し、両方が同じ値を指すようにします。一方、ブレントのアルゴリズムは指数検索の考え方に基づいています。フロイドとブレントのアルゴリズムはどちらも一定数のメモリ セルのみを使用し、シーケンスの開始から最初の繰り返しまでの距離に比例する数の関数評価を行います。他のいくつかのアルゴリズムは、より少ない関数評価と引き換えに大量のメモリを使用します。

サイクル検出の応用には、疑似乱数ジェネレーターと暗号化ハッシュ関数の品質テスト、計算数論アルゴリズム、コンピュータ プログラム内の無限ループとセルオートマトン内の周期的構成の検出、リンク リストデータ構造の自動形状分析、 DBMSのトランザクション管理のデッドロックの検出などがあります。

図は、集合S = {0,1,2,3,4,5,6,7,8}を_それ自身に写像する関数fを示している。x 0 = 2から始めてfを繰り返し適用すると、値のシーケンスが見える。

2、0、6、3、1、6、3、1、6、3、1、...。

この値シーケンスのサイクルは6、3、1です。

S を任意の有限集合、f をSからそれ自身への任意の関数、x _{0 を}Sの任意の要素とする。任意のi > 0について、x _i = f ( x _{i − 1} )とする。μ を、値x _{μ が}値のシーケンスx _i内で無限に繰り返し出現する最小のインデックスとし、λ (ループの長さ) を、 x _μ = x _{λ + μ}となる​​最小の正の整数とする。サイクル検出問題は、 λとμ を見つけるタスクである。^[1]

同じ問題をグラフ理論的に捉えるには、関数グラフ（つまり、各頂点が単一の出力辺を持つ有向グラフ）を構築し、その頂点がSの要素で、辺が要素を対応する関数値にマッピングする（図参照）という方法がある。開始頂点x ₀から到達可能な頂点の集合は、ギリシャ文字のロー（ρ ）に似た形状のサブグラフを形成する。つまり、 x ₀からλ頂点のサイクルまでの長さμのパスである。^[2]

通常、f は、上の図に示されているように、値のテーブルとして指定されることはありません。むしろ、サイクル検出アルゴリズムは、値のシーケンスx _iまたはf を計算するサブルーチンにアクセスできます。タスクは、シーケンスからできるだけ少ない値を調べたり、サブルーチン呼び出しをできるだけ少なくしたりしながら、λとμ を見つけることです。通常、サイクル検出問題のアルゴリズムの空間計算量も重要です。シーケンス全体を格納するのに必要な量よりも大幅に少ないメモリ量を使用して問題を解決したいのです。

一部のアプリケーション、特に整数因数分解のためのポラードのローアルゴリズムでは、アルゴリズムによるSおよびfへのアクセスははるかに制限されています。たとえば、ポラードのローアルゴリズムでは、S は因数分解される数の未知の素因数を法とする整数の集合であるため、Sのサイズさえもアルゴリズムには不明です。サイクル検出アルゴリズムをこのような限られた知識で使用できるようにするために、アルゴリズムは次の機能に基づいて設計される場合があります。最初に、アルゴリズムはメモリ内に開始値x ₀へのポインターを表すオブジェクトを持っていると想定されます。どのステップでも、次の 3 つのアクションのいずれかを実行できます。メモリ内の別のオブジェクトへのポインターをコピーする、fを適用してそのポインターのいずれかをシーケンス内の次のオブジェクトへのポインターに置き換える、またはそのポインターのうちの 2 つがシーケンス内で等しい値を表しているかどうかを判定するサブルーチンを適用する、のいずれかです。等価性テストアクションには、いくつかの非自明な計算が含まれる場合があります。たとえば、ポラードのローアルゴリズムでは、2つの格納された値の差が因数分解される数と非自明な最大公約数を持つかどうかをテストすることによって実装されます。^{[2]このコンテキストでは、計算の}ポインタマシンモデルに類似して、ポインタのコピー、シーケンス内の前進、および等価性テストのみを使用するアルゴリズムは、ポインタアルゴリズムと呼ばれることがあります。

入力がf を計算するサブルーチンとして与えられた場合、サイクル検出問題は、値のシーケンスx _iを計算し、ハッシュ テーブルなどのデータ構造を使用してこれらの値を格納し、後続の各値がすでに格納されているかどうかをテストするだけで、 λ + μ関数アプリケーションのみを使用して簡単に解決できます。ただし、このアルゴリズムの空間計算量はλ + μに比例し、不必要に大きくなります。さらに、このメソッドをポインター アルゴリズムとして実装するには、各値のペアに等価性テストを適用する必要があり、全体で 2 乗の時間が必要になります。そのため、この分野の研究は、この単純なアルゴリズムよりも少ないスペースを使用することと、より少ない等価性テストを使用するポインター アルゴリズムを見つけることという 2 つの目標に集中しています。

フロイドのサイクル検索アルゴリズムは、異なる速度でシーケンス内を移動する 2 つのポインタのみを使用するポインタ アルゴリズムです。イソップ童話の「ウサギとカメ」にちなんで、「ウサギとカメのアルゴリズム」とも呼ばれています。

このアルゴリズムは、ドナルド・クヌースによって発明されたロバート・W・フロイドにちなんで名付けられました。^{[3] [4]}しかし、このアルゴリズムはフロイドの出版された研究には登場せず、これは誤った帰属である可能性があります。フロイドは1967年の論文で有向グラフ内のすべての単純サイクルをリストするアルゴリズムについて説明していますが、 ^[5]この論文では、この記事の主題である関数グラフのサイクル検索問題については説明されていません。実際、引用なしでフロイドに帰属するクヌースの声明（1969年）は、印刷物で最初に登場したものであり、したがってこれは特定の個人に帰属するものではなく、民間定理である可能性があります。 ^[6]

アルゴリズムの重要な洞察は次のとおりです。サイクルがある場合、任意の整数i ≥ μおよびk ≥ 0について、x _i = x _{i + kλ}です。ここで、λは検出するループの長さ、μ はサイクルの最初の要素のインデックス、k はループの数を表す整数です。これに基づくと、あるkについて、 x _i = x _{2 i}の場合にのみ、i = kλ ≥ μであることが示されます(サイクルでx _i = x _{2 i}の場合、 2 i = i + kλとなるkが存在し、これはi = kλを意味します。また、 i = kλとなるiとkが存在する場合、2i = i + kλかつx _{2 i} = x _{i + kλ}です)。したがって、アルゴリズムでは、シーケンスの開始から他の 2 倍の距離にあるこの特別な形式の繰り返し値を確認するだけで、 λの倍数である繰り返しの周期ν を見つけることができます。νが見つかると、アルゴリズムはシーケンスを最初からたどり直し、シーケンス内の最初の繰り返し値x _{μ を}見つけます。このとき、 λ はν を割り切るため、 x _μ = x _{μ + v と}なります。最後に、μの値がわかれば、 x _{μ + λ} = x _μとなる​​最初の位置μ + λを検索することで、最短の繰り返しサイクルの長さλ を簡単に見つけることができます。

したがって、アルゴリズムは、与えられたシーケンスへの 2 つのポインターを維持します。1 つ (カメ) はx _iに、もう 1 つ (ウサギ) はx _{2 i}にあります。アルゴリズムの各ステップで、iが 1 ずつ増加し、シーケンス内でカメを 1 ステップ前進させ、ウサギを 2 ステップ前進させてから、これら 2 つのポインターのシーケンス値を比較します。カメとウサギが等しい値を指すi > 0の最小値が、目的の値νです。

次のPythonコードは、このアイデアをアルゴリズムとして実装する方法を示しています。

def  floyd ( f ,  x0 )  ->  ( int ,  int ): 
"""フロイドのサイクル検出アルゴリズム。""" # アルゴリズムの主なフェーズ: 繰り返しの検出 x_i = x_2i。# ウサギはカメの 2 倍の速さで移動し、# ウサギとカメの間の距離は各ステップで 1 ずつ増加します。# 最終的には両方ともサイクル内に入り、その後、# ある時点で、ウサギとカメの間の距離は周期 λ で割り切れるようになります。tortoise = f ( x0 ) # f(x0) は x0 の次の要素/ノードです。hare = f ( f ( x0 )) while tortoise != hare : tortoise = f ( tortoise ) hare = f ( f ( hare ))    
    
    
    
    
    
    
       
      
       
          
          
  
    # この時点で、カメの位置 ν は
    ウサギとカメの間の距離に等しく、
    周期 λ で割り切れます。したがって、一度に 1 歩ずつ周期内を移動するウサギ
    と、周期に向かって移動するカメ (x0 にリセット) は、
    周期の初めに交差します。
    両者の距離は 2ν で一定であり、λ の倍数であるため、
    カメがインデックス μ に到達するとすぐに両者は一致します。

    # 最初の繰り返しの位置 μ を見つけます。     
    mu  =  0 
    tortoise  =  x0 
    while  tortoise  !=  hare : 
        tortoise  =  f ( tortoise ) 
        hare  =  f ( hare )    # ウサギとカメは同じ速度で動きます
        mu  +=  1
 
    # x_μ から始まる最短サイクルの長さを見つけます
    。 # ウサギは一度に 1 歩ずつ動きますが、カメは静止しています。
    # lam は λ が見つかるまで増加します。
    lam  =  1 
    hare  =  f ( tortoise ) 
    while  tortoise  !=  hare : 
        hare  =  f ( hare ) 
        lam  +=  1
 
     ラム、 ムを返す

このコードは、ポインタの保存とコピー、関数の評価、等価性テストによってのみシーケンスにアクセスするため、ポインタアルゴリズムとして適格です。このアルゴリズムは、これらのタイプのO（λ + μ）回の演算とO（1）回の記憶領域を使用します。^[7]

リチャード・P・ブレントは、ウサギとカメのアルゴリズムと同様に、シーケンスへのポインタを 2 つだけ必要とする、別のサイクル検出アルゴリズムを説明した。^[8]しかし、これは異なる原理に基づいており、λとμ の両方よりも大きい2 の最小の累乗 2 ⁱを検索する。i = 0、1、2、...の場合、アルゴリズムはx _{2 ⁱ} −1_を次の 2 の累乗までの各後続シーケンス値と比較し、一致するものが見つかったら停止する。ウサギとカメのアルゴリズムと比較して、サイクルの正しい長さλ を直接見つけることができるため、後続の段階で検索する必要がないことと、関数fの評価が3 回ではなく1 回だけである点が 2 つの利点である。 ^[9]

次の Python コードは、この手法がどのように機能するかをより詳細に示しています。

def  brent ( f ,  x0 )  ->  ( int ,  int ): 
"""Brent のサイクル検出アルゴリズム。""" # メインフェーズ: 連続する 2 の累乗を検索power = lam = 1 tortoise = x0 hare = f ( x0 ) # f(x0) は x0 の次の要素/ノードです。# これはサイクルがあると想定しています。そうでなければ、このループは終了しませんwhile tortoise != hare : if power == lam : # 新しい 2 の累乗を開始する時間ですか? tortoise = hare power *= 2 lam = 0 hare = f ( hare ) lam += 1    
    
        
      
        
    
       
             
              
              
              
          
          

    # 長さ λ の最初の繰り返しの位置を見つけます。
    tortoise  =  hare  =  x0 
    for  i  in  range ( lam ): 
    # range(lam) は、値 0、1、...、lam-1 のリストを生成します。 
        hare  =  f ( hare ) 
    # ウサギとカメの間の距離は λ になりました。

    # 次に、ウサギとカメは同じ速度で動き、
    カメ!=ウサギであるmu  =  0に一致するまで動きます
    。カメ= f (カメ)ウサギ= f (ウサギ) mu += 1   
          
          
          
 
     ラム、 ムを返す

ウサギとカメのアルゴリズムと同様に、これはO ( λ + μ )回のテストと関数評価、およびO (1) 回の記憶領域を使用するポインタ アルゴリズムです。関数評価の回数がフロイドのアルゴリズムよりも多くなることはないことは簡単に示せます。ブレントは、平均して彼のサイクル検索アルゴリズムはフロイドのアルゴリズムよりも約 36% 高速に実行され、ポラード ロー アルゴリズムを約 24% 高速化すると主張しています。また、2 つのポインタのうち遅いほうによってトレースされるインデックスのシーケンスが 2 の累乗そのものではなく、2 の累乗のランダムな倍数である、アルゴリズムのランダム化バージョンの平均ケース分析も行っています。ブレントの主な用途は整数因数分解アルゴリズムでしたが、ブレントは擬似乱数ジェネレータのテストへの応用についても説明しています。^[8]

RWゴスパーのアルゴリズム^{[10] [11]}は、周期、開始点の下限と上限、および最初のサイクルの を求めます。下限と上限の差は周期と同じオーダー、つまり です。 ${\displaystyle \lambda}$${\displaystyle \mu_{l}}$${\displaystyle \mu_{u}}$${\displaystyle \mu _{l}+\lambda \sim \mu _{h}}$

Gosper のアルゴリズムの主な特徴は、ジェネレータ関数を再評価するために決して後退しないこと、そして空間的にも時間的にも経済的であることです。これは、大まかに言えば、Brent のアルゴリズムの並行バージョンと言えます。Brent のアルゴリズムがウサギとカメの間隔を徐々に広げていくのに対し、Gosper のアルゴリズムは、ほぼ指数的に間隔を空けた複数のカメ (以前の値がいくつか保存される) を使用します。HAKMEM 項目 132 の注記によると、^[11]このアルゴリズムは、任意の値が 3 回目に出現する前に繰り返しを検出します。つまり、サイクルは最大で 2 回繰り返されます。この注記には、以前の値を保存すれば十分であるとも記載されていますが、提供されている実装^[10]では値を保存します。たとえば、関数値が 32 ビットの整数であり、サイクルの2 回目の反復が、開始以来最大で 2 ^{32 回の}関数評価の後で終了するとします (つまり、)。次に、Gosper のアルゴリズムは、33 個の値 (各値は 32 ビットの整数) のスペースを消費しながら、 最大 2 ^{32 回の}関数評価の後にサイクルを見つけます。${\displaystyle \Theta (\log \lambda )}$${\displaystyle \Theta (\log(\mu +\lambda ))}$${\displaystyle \mu +2\lambda \leq 2^{32}}$

ジェネレータ関数の - 番目の評価時に、アルゴリズムは生成された値を以前の値と比較します。は少なくとも まで、最大でまで増加することに注意してください。したがって、このアルゴリズムの時間計算量は です。値を格納するため、空間計算量は です。これは、この記事全体にわたって使用されている、関数値のサイズは一定であるという通常の仮定に基づいています。この仮定がない場合、空間計算量は です。少なくとも 個の異なる値が必要であり、各値のサイズは であるためです。 ${\displaystyle i}$${\displaystyle O(\log i)}$${\displaystyle i}$${\displaystyle \mu +\lambda }$${\displaystyle \mu +2\lambda }$${\displaystyle O((\mu +\lambda )\cdot \log(\mu +\lambda ))}$${\displaystyle \Theta (\log(\mu +\lambda ))}$${\displaystyle \Theta (\log(\mu +\lambda ))}$${\displaystyle \Omega (\log ^{2}(\mu +\lambda ))}$${\displaystyle \mu +\lambda }$${\displaystyle \Omega (\log(\mu +\lambda ))}$

多くの著者が、フロイドやブレントの手法よりも多くのメモリを使用するものの、より迅速にサイクルを検出するサイクル検出手法を研究してきました。一般に、これらの手法では、以前に計算されたシーケンス値をいくつか保存し、新しい値のそれぞれが以前に計算された値の 1 つと等しいかどうかをテストします。これを迅速に行うために、通常は以前に計算された値を格納するためにハッシュ テーブルまたは同様のデータ構造を使用するため、ポインタ アルゴリズムではありません。特に、通常、ポラードのロー アルゴリズムには適用できません。これらの方法が異なるのは、保存する値を決定する方法です。Nivasch に従って、^[12]ではこれらの手法を簡単に概観します。

• ブレント^[8]は、保存されたシーケンス値のインデックスが2以外の数Rの累乗である彼のテクニックのバリエーションをすでに説明しています。Rを1に近い数に選択し、シーケンス値をRの連続する累乗のシーケンスに近いインデックスに保存することで、サイクル検出アルゴリズムは、最適なλ + μの任意の小さな係数内の関数評価の数を使用できます。^{[13] [14]}
• Sedgewick、Szymanski、Yao ^[15]は、 M個のメモリセルを使用し、最悪の場合でも関数評価のみを必要とする 方法を提案している。この方法では、定数cに対してこれが最適であることが示される。この手法では、数値パラメータdを維持し、シーケンス内のdの倍数の位置のみをテーブルに格納し、格納されている値が多すぎる場合はテーブルをクリアしてdを2倍にする。${\displaystyle (\lambda +\mu )(1+cM^{-1/2})}$
• 何人かの著者は、関数値を、位置に基づく（Sedgewickらの方法のように）値を含む基準に基づいてテーブルに格納する、際立ったポイント法について説明している。例えば、ある値dを法としてゼロに等しい値が格納される可能性がある。^{[16] [17]}より簡単に言えば、Nivasch ^{[12] は}、以前に見た値のランダムなサンプルを格納し、各ステップで適切なランダムな選択を行ってサンプルがランダムなままになるようにするというDP Woodruffの提案を認めている。
• Nivasch ^[12]は、固定量のメモリを使用しないアルゴリズムについて説明していますが、そのアルゴリズムでは、使用されるメモリの予想量（入力関数がランダムであるという仮定の下）はシーケンス長の対数になります。この手法では、後続の項目に小さい値がない場合に、項目がメモリ テーブルに格納されます。Nivaschが示すように、この手法による項目はスタック データ構造を使用して維持でき、後続の各シーケンス値はスタックの先頭とのみ比較する必要があります。アルゴリズムは、最小値を持つ繰り返しシーケンス要素が見つかると終了します。複数のスタックで同じアルゴリズムを実行し、値のランダムな順列を使用して各スタック内の値を並べ替えると、以前のアルゴリズムと同様の時間と空間のトレードオフが可能になります。ただし、スタックが1つのバージョンでも、2つの値のどちらが小さいかを判断するために必要な比較のため、ポインター アルゴリズムではありません。

入力シーケンスから最大M個の値を格納するサイクル検出アルゴリズムは、少なくとも関数評価を実行する必要がある。^{[18] [19]}${\displaystyle (\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)}$

サイクル検出は多くのアプリケーションで使用されてきました。

• 擬似乱数生成器の周期の長さを決定することは、その強さの 1 つの尺度です。これは、Knuth が Floyd の方法を説明する際に引用した応用です。^[3] Brent ^{[8] は、この方法で}線形合同型生成器をテストした結果について説明しています。その周期は宣伝されているよりも大幅に短いことが判明しました。より複雑な生成器の場合、周期が見つかる値のシーケンスは、生成器の出力ではなく、内部状態を表す場合があります。
• いくつかの数論アルゴリズムはサイクル検出に基づいており、その中には整数因数分解のためのポラードのローアルゴリズム^[20]や離散対数問題のための関連するカンガルーアルゴリズム^[21]が含まれます。
• 暗号アプリケーションでは、ある暗号関数ƒによって同じ値x _μにマッピングされた 2 つの異なる値x _{μ −1}とx _{λ + μ −1を見つける能力は、} ƒの弱点を示している可能性があります。たとえば、Quisquater と Delescaille [ ^{17] は}、メッセージとそのメッセージを同じ暗号化された値にマッピングする一対のデータ暗号化標準キーの検索にサイクル検出アルゴリズムを適用しています。Kaliski 、Rivest、およびSherman ^{[22]も、DES を攻撃するためにサイクル検出アルゴリズムを使用しています。この手法は、}暗号ハッシュ関数の衝突を見つけるためにも使用できます。^[23]
• サイクル検出は、特定の種類のコンピュータプログラムにおける無限ループを発見する方法として役立つ可能性がある。^[24]
• セルオートマトンシミュレーションにおける周期的な構成は、オートマトン状態のシーケンスにサイクル検出アルゴリズムを適用することによって発見される可能性がある。^[12]
• リンクリストデータ構造の形状解析は、それらの構造を使用してアルゴリズムの正しさを検証するための手法です。リスト内のノードが同じリスト内の前のノードを誤って指している場合、構造はこれらのアルゴリズムによって検出できる循環を形成します。^[25] Common Lispでは、変数の制御下にあるS式*print-circle*プリンタが循環リスト構造を検出し、コンパクトに印刷します。
• テスケ^[14]は計算群論への応用について説明している：アーベル群の構造をその生成子の集合から決定する。カリスキら^[22]の暗号アルゴリズムも未知の群の構造を推測しようとする試みとみなすことができる。
• フィッチ（1981）は、ウィリアム・カーハンによる天体力学のコンピュータシミュレーションへの応用について簡単に言及している。この応用では、軌道系の位相空間における周期検出を使用して、系がシミュレーションの精度の範囲内で周期的であるかどうかを判断できる。^[18]
• マンデルブロ集合のフラクタル生成では、画像生成を高速化するためにいくつかのパフォーマンス技術が使用されます。その 1 つは「周期チェック」と呼ばれ、点軌道のサイクルを見つけるものです。この記事では「周期チェック」技術について説明します。別の説明については、こちらを参照してください。この技術を実装するには、いくつかのサイクル検出アルゴリズムを実装する必要があります。

• ガブリエル・ニヴァシュ、「サイクル検出問題とスタックアルゴリズム」
• ウサギとカメ、ポートランドパターンリポジトリ
• フロイドのサイクル検出アルゴリズム (ウサギとカメ)
• ブレントのサイクル検出アルゴリズム (テレポートするタートル)