Introduction

異なるデータ構造に格納されたデータを検索することは、ほとんどすべてのアプリケーションで重要な部分です。

与えられたタスクに対して特定のアルゴリズムを選択できることは、開発者にとって重要なスキルであり、高速で信頼性が高く安定したアプリケーションと、単純な要求から崩れるアプリケーションとの違いを意味することができる。

• メンバーズ演算子
• 線形探索
• 二項探索
• ジャンプ探索
• フィボナッチ探索
• 指数探索
• 内挿探索

Membership Operators

アルゴリズムは、絶え間ない進化と、異なるドメインの根本的な問題に対する最も効率的な解決策を見つける必要性の結果として、時間とともに発展し最適化されるようになります。

コンピューター サイエンスの領域で最も一般的な問題の 1 つは、コレクションを検索して、与えられたオブジェクトがコレクションに存在するかどうかを判断することです。

ほとんどすべてのプログラミング言語には、基本的な検索アルゴリズムの独自の実装があり、通常は、アイテムの与えられたコレクションでアイテムが見つかると Boolean 値 True または False を返す関数として実装されています。

Pythonでは、オブジェクトを検索する最も簡単な方法は、メンバーシップ演算子を使うことです – 与えられたオブジェクトがコレクション内のメンバーであるかどうかを判断することができるのでそのように名付けられました。

これらの演算子は、文字列、リスト、タプルなどPythonのあらゆる反復可能なデータ構造で使用することができます。

not in – 与えられた要素が構造の一部でなければ True を返します。

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

メンバシップ演算子は、与えられた文字列に部分文字列が存在するか、2つのString、List、Tupleがそれらが持つオブジェクトに関して交差するかどうかを判断するだけなら十分なものです。

ほとんどの場合、それが存在するかどうかを決定することに加えて、シーケンス内のアイテムの位置が必要で、メンバーシップ演算子はこの要件を満たしていません。 さらに、単にその存在を決定することができるだけでなく、コレクション内の要素の位置など、より多くの情報を得ることができます。

Linear Search

線形探索は最も単純な探索アルゴリズムの 1 つで、最も理解しやすいものです。 Python の in 演算子の私たち自身の実装を強化したものと考えることができます。

このアルゴリズムは、配列に対して反復処理を行い、項目が見つかったら最初に出現した項目のインデックスを返すというものです。

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

つまり、この関数を使って計算すると

>>> print(LinearSearch(, 2))

コードを実行すると、

1

これは、検索している項目の最初の出現のインデックスです。

線形探索の時間複雑度は O(n) で、入力リスト lys の項目数に応じて実行時間が増加することを意味します。

線形探索は、内蔵のメソッドや既存の演算子を使っても同じ効率が得られるため、実際にはあまり使用されませんし、他の探索アルゴリズムと比べても高速で効率的ではありません。

線形探索は、他のほとんどの探索アルゴリズムと異なり、探索を開始する前にコレクションをソートする必要がないため、ソートされていないコレクションで最初に出現するアイテムを見つける必要がある場合に適している。 線形探索よりも高速ですが、アルゴリズムを実行する前に配列がソートされている必要があります。

ソートされた配列の値 val を探していると仮定すると、アルゴリズムは val と配列の中間要素、ここでは mid と呼ぶことにします、を比較します。

そうでなければ、valがmidより小さいか大きいかによってmidのどちら側にある可能性が高いかを特定し、配列のもう一方を破棄します。

その後、再帰的または反復的に同じ手順を踏んで、mid の新しい値を選び、val と比較し、アルゴリズムの各反復で一致する可能性の半分を破棄します。

バイナリ検索アルゴリズムは再帰的または反復的に記述することができます。 再帰は新しいスタック フレームの割り当てを必要とするので、Python では一般に遅くなります。

優れた検索アルゴリズムはできるだけ高速かつ正確であるべきなので、バイナリ検索の繰り返し実装を考えてみましょう：

計算する関数を使用すると：

>>> BinarySearch(, 20)

我々は結果を得る：

1

これは我々が探している値のインデックスである。

• 現在の要素のインデックスを返す
• 配列の左半分を検索する
• 配列の右半分を検索する

我々は反復ごとに1つの可能性を選ぶことができるだけで、マッチの可能性が各反復で2分割されているプールがあります。 このため、バイナリサーチの時間複雑度は O(log n) となります。

バイナリサーチの欠点は、配列内に複数の要素が存在する場合、最初の要素のインデックスを返さず、中央に最も近い要素のインデックスを返すことです。

>>> print(BinarySearch(, 4))

このコードを実行すると、中央の要素のインデックスが返されます:

1

同じ配列で線形探索を実行すると、

0

これが最初の要素のインデックスとなります。 たとえば、配列 に対してバイナリ検索を実行し、4を検索すると、結果として 3 が得られます。 しかし、//演算子に依存しているなど、いくつかの欠点があります。

Jump Search

Jump Search は、ソートされた配列で動作し、同様の分割統治アプローチで検索を行う点で、バイナリサーチに類似しています。

値を検索するときに実際の比較を実行するために線形探索に依存するので、線形探索アルゴリズムの改良版として分類することができます。 つまり、入力リスト lys において、ジャンプのサイズがジャンプである場合、我々のアルゴリズムは lys, lys, lys, lys という順序で要素を検討する。

それぞれのジャンプで、我々が見た前の値とそのインデックスを保存する。 lys<要素<lysとなる値の集合を見つけたら、lysを検索集合の左端の要素、lysを右端の要素として線形探索を行う：

このアルゴリズムは複雑なので、この入力でジャンプ探索のステップごとの計算を考えてみよう：

>>> print(JumpSearch(, 5))

• ジャンプ探索ではまずmath.sqrt(len(lys))を計算してジャンプサイズを決定することになります。 要素が9個あるので、ジャンプサイズは√9＝3となります。
• 次に、配列の長さから1を引いた最小値、つまりleft+jumpの値、この場合は0＋3＝3となる変数rightの値を計算します。 3は8より小さいので、rightの値として3を使います。
• ここで、検索対象の要素である5がlysとlysの間にあるかどうかをチェックします。
• 次に、もう一度計算を行い、検索する要素がlysとlysの間（6が3+ジャンプ）であるかどうかを確認します。 5は4と7の間にあるので、lysとlysの間の要素で線形探索を行い、要素のインデックスを返します：

4

ジャンプ探索の時間複雑性はO（√n）、ここで√nはジャンプサイズ、nはリストの長さで、効率の点では線形探索と二項探索アルゴリズムの間に位置づけられます。

二元探索と比較した場合のジャンプ探索の最も重要な利点は、除算演算子（/）に依存しないことである。

ほとんどの CPU では、除算アルゴリズムの実装が反復的であるため、他の基本的な算術演算（加算、減算、乗算）と比較すると、除算演算子の使用にはコストがかかる。

それ自体のコストは非常に小さいが、探索する要素の数が非常に多く、実行しなければならない除算演算が増加すると、コストが段階的に積み重なる可能性がある。

フィボナッチ探索

フィボナッチ探索は、バイナリ探索とジャンプ探索の両方に類似した、別の分割統治アルゴリズムである。

フィボナッチ数はゼロから始まり、0、1、1、2、3、5、8、13、21・・・というパターンで、各要素はその直前にある2つの数字の足し算となる。 ここで、fibM_minus_1とfibM_minus_2は配列のfibMの直前にある2つの数字です。

fibM = fibM_minus_1 + fibM_minus_2

検索配列lysに非常に少ない数の項目がある場合にインデックスエラーを避けるために、値を0、1、1またはフィボナッチ配列の最初の3つに初期化しています。

次に、検索配列lysの要素数以上のフィボナッチ数列の最小の数をfibMの値として選び、その直前の2つのフィボナッチ数をfibM_minus_1とfibM_minus_2の値として選びます。 配列に要素が残っていて、fibMの値が1より大きい間は:

• valとfibM_minus_2までの範囲のブロックの値を比較し、一致したらその要素のインデックスを返します。
• 値が現在見ている要素より大きい場合、fibM、fibM_minus_1、fibM_minus_2の値をフィボナッチ数列で2段階下に移動し、インデックスを要素のインデックスにリセットします。
• 値が現在見ている要素より小さい場合、fibM、fibM_minus_1、fibM_minus_2の値をフィボナッチ数列で1段階下に移動します。

このアルゴリズムのPython実装を見てみましょう。

FibonacciSearch関数を使って計算した場合：

>>> print(FibonacciSearch(, 6))

この検索のステップバイステップの処理を見てみましょう。

• リストの長さをfibMとして、それ以上の最小のフィボナッチ数を決定します。この場合、条件を満たす最小のフィボナッチ数は13です。
• 値は次のように割り当てられる：
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • インデックス = -1
• 次に、4が-1+5の最小となる要素lysを確認します。 lysの値は5で、探している値より小さいので、フィボナッチ数を1段下げて、値を作る。
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• 次に、4+3の最小値7となる要素 lys をチェックします。 lysの値は8で、探している値より大きいので、フィボナッチ数を2段階下に移動させる。
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• ここで要素lysを調べると5が4+1の最小となるところです。 lys の値は 6 で、これが探している値です！

結果は予想通り、

5

フィボナッチ探索の時間複雑性は O(log n) で、二項探索と同じになります。 これは、このアルゴリズムがほとんどの場合、線形探索とジャンプ探索の両方よりも高速であることを意味します。

フィボナッチ探索は、探索する要素の数が非常に多く、除算演算子に依存するアルゴリズムの使用に伴う非効率を減らしたい場合に使用できます。

Exponential Search

Exponential search は、ジャンプ検索やフィボナッチ検索が少し複雑であるのに比べて、Python で非常に簡単に実装できるもう 1 つの検索アルゴリズムです。 ギャロッピング検索、ダブリング検索、ストルジーク検索という名前でも知られています。

指数探索は値の最終比較を実行するためにバイナリ検索に依存します。 このアルゴリズムは次のように動作します：

• 探している要素がありそうな範囲を決定する
• 項目の正確なインデックスを見つけるために範囲のバイナリ検索を使用する

指数探索アルゴリズムの Python の実装は次のとおりです。

>>> print(ExponentialSearch(,3))

の値を見つけるためにこの関数を使用する場合、アルゴリズムは次のように動作します：

• リストの最初の要素が探している値に一致するかどうかをチェックします – lys は 1、我々は 3 を探しているので、インデックスを 1 に設定して次に進みます。
• リスト内のすべての要素を調べ、インデックスの位置にある項目が目的の値以下である間、indexの値を2の倍数で指数関数的に増加させます。
  • index = 1, lysは2であり、3より小さいので、インデックスに2を掛けて2としています。
  • index = 2, lysは3であり、3と等しいので、インデックスに2を掛けて4としています。
  • index = 4, lysは5で、これは3より大きい。
• 次に、リストをスライスしてバイナリ検索を行う; arr。 Pythonでは、これはサブリストに4番目の要素までのすべての要素が含まれることを意味します。したがって、実際には:

>>> BinarySearch(, 3)

を呼び出し、:

2

これは元のリストと、バイナリ検索アルゴリズムに渡すスライスリストの両方で探している要素のインデックスになります。

指数探索は O(log i) 時間で実行され、ここで i は探索する項目のインデックスです。 最悪の場合、時間の複雑さは O(log n) で、最後の項目が検索している項目 (n は配列の長さ) である。

指数探索は、検索する要素が配列の先頭に近いほど、二項探索よりもうまくいく。

補間探索

補間探索はバイナリサーチに似た別の分割統治アルゴリズムである。 二項探索とは異なり、常に中央から探索を始めるとは限らない。 補間探索では、次の式を使用して、探している要素の推定位置を計算します。

index = low + )*(high-low) / (lys-lys)]

ここで、変数は次のとおりです：

• lys – 入力配列
• val – 探している要素
• index – 検索要素の推定インデックス。 これは、valが配列の末尾の要素に近い値（lys）の場合は高く、valが配列の先頭の要素に近い値（lys）の場合は低く計算されます
• low：配列の開始インデックス
• high：配列の最後のインデックス

アルゴリズムは、indexの値を計算して探索を行う。

• 一致するものが見つかった場合（lys == valの場合）、インデックスが返されます
• valの値がlysより小さい場合、インデックスの値は、左サブ配列の式を使用して再計算されます
• valの値がlysより大きい場合、その値は、次のようになります。 の式で再計算される

それでは、Pythonで補間検索を実装してみましょう。

>>> print(InterpolationSearch(, 6))

この関数を使って計算すると、初期値は次のようになります。

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

lysは6で探している値なので実行を止めて結果を返します。

5

要素数が多く、1回の繰り返しでインデックスが計算できない場合は、式中のhighとlowの値を調整した上でインデックスの値を再計算し続けます。

補間探索の時間計算量は、値が一様に分布している場合、O(log log n)である。 値が一様に分布していない場合、最悪の場合の時間複雑度はO(n)で、線形探索と同じである。

補間探索は一様に分布し、ソートされた配列で最もうまくいく。 バイナリ検索が中央から始まり常に 2 つに分割されるのに対し、補間検索は要素のありそうな位置を計算してインデックスをチェックするため、より少ない反復回数で要素を見つけられる可能性が高くなります。 Python で、私たちが議論した検索アルゴリズムのほとんどは、文字列を検索する場合にも同様に機能します。 補間検索アルゴリズムのように、数値計算のためにsearch要素を使用するアルゴリズムのコードに変更を加えなければならないことを覚えておいてください。

Pythonはまた、あなたのデータセットに対して異なる検索アルゴリズムのパフォーマンスを比較したい場合に開始するには良い場所です。

実装した検索アルゴリズムの性能をデータセットに対して比較するには、Python の time ライブラリを使用します：

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Conclusion

コレクション内の要素を検索するには、多くの可能な方法があります。 この記事では、いくつかの検索アルゴリズムとその Python での実装を説明しようとしました。

どのアルゴリズムを使うかは、検索するデータに基づいています。

• ソートされていない配列を検索したい場合、または検索変数の最初の出現を見つけたい場合、最良の選択肢は線形探索です。
• ソートされた配列を検索したい場合、多くの選択肢がありますが、最もシンプルで高速な方法はバイナリ探索です。
• 除算演算子を使用せずに検索したい並べ替えられた配列がある場合、ジャンプ検索またはフィボナッチ検索を使用できます。
• 検索する要素が配列の先頭に近いとわかっている場合、指数検索を使用できます。
• ソートされた配列も一様に分布している場合、使用する最も高速で効率的な検索アルゴリズムは補間検索になります。

ソートされた配列でどのアルゴリズムを使用するかわからない場合、Pythonの時間ライブラリと共にそれらのそれぞれを試し、データセットで最もうまくいくものを選択してください。