マージ中のギャロッピングモード

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

マージ中のギャロッピングモード

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

「ティムソート」の記事における「マージ中のギャロッピングモード」の解説

配列R1とR2を個別にマージすると、配列から選択された連続する要素の数が保持されます。この数が最小ギャロッピングしきい値（ min_gallop ）に達すると、ティムソートは、その配列から多くの連続する要素がまだ選択されている可能性があると見なし、ギャロッピングモードに切り替えます。 R1がそれをトリガーする責任があると仮定しましょう。このモードでは、アルゴリズムは、配列R1の配列R2の次の要素xに対して、ギャロッピング検索とも呼ばれる指数検索を実行します。これは2つの段階で行われます。最初の段階では、xがである範囲（2 k − 1、2 k + 1 − 1）を見つけます。第2段階では、第1段階で見つかった範囲内の要素xの二分探索を実行します。ギャロッピングモードは、配列中の要素間の間隔のパターンにマージアルゴリズムを適応させる試みです。 ギャロッピングは必ずしも効率的ではありません。場合によっては、ギャロッピングモードでは、単純な線形探索よりも多くの比較が必要になります。開発者が行ったベンチマークによると、ギャロッピングは、一方の配列の最初の要素がもう一方の配列の最初の7つの要素の1つではない場合にのみ有益です。これは、初期しきい値が7であることを意味します。ギャロッピングモードの欠点を回避するために、次の2つのアクションが実行されます。（1）ギャロッピングの効率がバイナリ検索よりも低いことが判明した場合、ギャロッピングモードは終了します。 （2）ギャロッピングの成功または失敗は、 min_gallopを調整するために使用されます。選択した要素が以前に要素を返したのと同じ配列からのものである場合、 min_gallopは1つ減り、ギャロッピングモードへの復帰を促します。それ以外の場合、値は1ずつ増加するため、ギャロッピングモードに戻ることはできません。ランダムデータの場合、 min_gallopの値が非常に大きくなるため、ギャロッピングモードが繰り返されることはありません。