Pythonで検索アルゴリズムを実装する方法を教えます

[[439902]]

この記事では、次の検索アルゴリズムについて説明します。

線形探索

バイナリ検索

補間検索

それぞれを詳しく見てみましょう。

1. 線形探索

データを見つけるための最も単純な戦略は線形検索です。線形検索では、各要素を走査してターゲットを見つけ、各データ ポイントにアクセスして一致を見つけ、一致が見つかったときに結果を返し、アルゴリズムはループを終了します。一致が見つからない場合、アルゴリズムはデータの最後まで検索を続けます。線形検索の明らかな欠点は、本質的に網羅的な検索であるため、非常に遅いことです。その利点は、他のアルゴリズムのようにデータをソートする必要がないことです。

線形探索のコードを見てみましょう。

定義LinearSearch(リスト、項目):
インデックス= 0
    見つかった = False   
 
 #各データ要素の値を一致させる
    インデックス<len(list)で見つかったのは 間違い：
        リスト[インデックス] == 項目の場合:
            見つかった =真 
それ以外：
インデックス=インデックス+ 1
戻りが見つかりました

ここで、このコードの出力を見てみましょう (図 3-15 を参照)。

リスト = [12, 33, 11, 99, 22, 55, 90] 
 
 print(LinearSearch(リスト、12)) 
 
 print(LinearSearch(リスト、91))

▲図3-15

データが正常に見つかった場合、LinearSearch 関数を実行すると True が返されることに注意してください。

• 線形探索のパフォーマンス: 前述のように、線形探索は、最悪の場合の時間複雑度が O(N) で網羅的な探索を実行する単純なアルゴリズムです。

2. 二分探索

バイナリ検索アルゴリズムの前提条件は、データが順序どおりになっていることです。アルゴリズムは、探している値が見つかるまで、現在のリストを繰り返し 2 つに分割し、最小インデックスと最大インデックスを追跡します。

 def BinarySearch(リスト、項目):
最初= 0
最後= len(リスト)-1
    見つかった = False   
 
    最初<=最後 そして 見つかりません：
        中間点 = (最初+最後) // 2
        リスト[中間点] == ​​項目の場合:
            見つかった =真 
それ以外：
            項目 < リスト[中間点]の場合:
最後= 中間点-1
それ以外：
最初= 中間点+1
戻りが見つかりました

出力結果を図3-16に示します。

リスト = [12, 33, 11, 99, 22, 55, 90] 
 
 sorted_list = BubbleSort(リスト) 
 
 print(BinarySearch(リスト、12)) 
 
 print(BinarySearch(リスト、91))

▲図3-16

BinarySearch 関数を呼び出すと、入力リスト内に値が見つかった場合に True が返されることに注意してください。

• バイナリ検索のパフォーマンス: バイナリ検索は、各反復でアルゴリズムがデータを 2 つの部分に分割するため、このように呼ばれています。データに N 個の項目がある場合、反復を完了するには最大 O(log N) ステップかかります。つまり、アルゴリズムの実行時間は O(log N) になります。

3. 補間検索

バイナリ検索の基本的なロジックは、データの中央部分に焦点を当てることです。補間は、ターゲット値を使用してソートされた配列内の要素のおおよその位置を推定する、より複雑な検索です。

例を使って理解してみましょう。英語の辞書で river などの単語を検索する場合、辞書の真ん中までめくって検索を開始するのではなく、この情報を使用して補間し、文字 r で始まる単語の検索を開始します。より一般的な補間ファインダーは次のようになります。

 def IntPolsearch(リスト,x):
    idx0 = 0
    idxn = (len(リスト) - 1)
    見つかった = False  
    idx0 <= idxnかつx >= list[idx0]かつx <= list[idxn] の場合: 
 
 # 中間点を見つける
        mid = idx0 + int ((( float (idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0]))) 
 
 #中間点の値と検索値を比較する
        リスト[mid] == xの場合:
            見つかった =真 
戻りが見つかりました
 
        リスト[mid] < xの場合:
            idx0 = 中間 + 1
戻りが見つかりました

出力結果を図3-17に示します。

リスト = [12, 33, 11, 99, 22, 55, 90] 
 
 sorted_list = BubbleSort(リスト) 
 
 print(IntPolsearch(リスト、12)) 
 
 print(IntPolsearch(リスト,91))

▲図3-17

IntPolsearch 関数を使用する前に、まずソート アルゴリズムを使用して配列をソートする必要があることに注意してください。

• 補間検索のパフォーマンス: データが不均一に分散されている場合、補間検索アルゴリズムのパフォーマンスは低下し、アルゴリズムの最悪の時間計算量は O(N) になります。データがほぼ均等に分散されている場合、最適な時間計算量は O(log(log N)) です。

著者について: Imran Ahmad は、Google 認定インストラクターであり、長年にわたり Google と Learning Tree で Python、機械学習、アルゴリズム、ビッグデータ、ディープラーニングを専門に教えています。彼は博士号取得を目指しながら、クラウド コンピューティング環境でのリソース割り当てを最適化するための線形計画法に基づいた ATSRA という新しいアルゴリズムを提案しました。彼はほぼ 4 年間、カナダ連邦政府の高度分析研究所で注目を集める機械学習プロジェクトに取り組んできました。

この記事は「すべてのプログラマが知っておくべき 40 のアルゴリズム」から抜粋したもので、出版社の許可を得て公開されています。