「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#9

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

第3章 探索

いよいよ探す関係の話題になりましたね。これがマスターできるといろいろできそうですね。

3-1探索アルゴリズム

住所録を例に探索を考えると、国籍、範囲内の年齢、発音が似た名前、などの項目が挙げられます。
この着目する項目のことをキー(key)と呼びます。
キーはデータの一部であることが多いそうです。
また探索には、一致、区間、近接などを単一もしくは複数指定します。
プログラミングっぽさが出てきましたね。

配列からの探索

配列のから探索をする場合に次のアルゴリズムが挙げられます。
・線形探索：ランダムに並んだデータを探索
・2分探索：一定の規則で並んだデータの集まりから高速な探索をする。
・ハッシュ法：追加削除が高速に行えるデータの集まりからの高速な探索を行う。
-チェイン法：同一ハッシュ値のデータを線形リストでつなぐ手法。
-オープンアドレス法：衝突時に再ハッシュを行う手法。
目的に応じて使い分けや、組み合わせが必要です。

3-2 線形探索

直線に並んだ配列は先頭から順になぞるように探索をすることで実現できます。
これは線形探索(逐次探索)と呼ばれるアルゴリズムです。

list3-1

#線形探索
from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    '''シーケンスaからkeyと等価な要素を線形探索（while文）'''
    
    i = 0
    
    while True:
        if i ==len(a): #配列内のインデックス数とiが一致したとき
            return -1 #探索失敗（-1を返す）
        if a [i] == key: #配列aのi番にある数字とkeyが一致したとき
            return i #探索成功(添字を返却)
        i += 1 #iに1を加えた数字を参照する
        
if __name__ == '__main__':
    num = int(input('要素数：'))
    x = [None] * num #要素数num個の配列を生成
    
    for i in range(num): #入力した数字(num)の回数まで繰り返す
        x[i] = int(input(f'x[{i}]')) #要素内の数字を入力(リストを作成)
        
    ky=int(input('探す値：'))#キーkyの読み込み
        
    idx = seq_search(x, ky)#kyと等価な要素をxから探索
        
    if idx == -1: #関数seq_searchから-1が返ってきたと時に成立する
        print('その値の要素は存在しません。')
    else:#それ以外の場合
        print(f'それはx[{idx}]にあります。')#関数seq_search内のkeyがidxに代入される

while文をfor文に変えたものが次のプログラムになります。

list3-2ssearch_while.py

#コードを保存する際はファイル名からlist3-2を消してください。
#線形探索
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
    '''シーケンスaからkeyと等価な要素を線形探索（for文）'''
    for i in range(len(a)):
        if a[i] == key:
            return i # 探索成功(添字を返却)
    return -1 #探索失敗(-1を返却)
        
        
if __name__ == '__main__':
    num = int(input('要素数：'))
    x = [None] * num #要素numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]'))
        
    ky=int(input('探す値：'))#キーkyの読み込み
        
    idx = seq_search(x, ky)#kyと等価な要素をxから探索
        
    if idx == -1:
        print('その値の要素は存在しません。')
    else:
        print(f'それはx[{idx}]にあります。')

コラム3-1　色々な型のシークエンスからの探索

任意の型のシーケンスから探索を行えるようなプログラムを書きます。

list3C-1

#線形探索を行う関数seq_searchの利用例(その1)

from ssearch_while import seq_search

print('実数の探索を行います。')
print('注：Endで入力終了。')

number = 0
x = [] #空リスト

while True:
    s = input(f'x[{number}]：')
    if s == 'End':
        break
    x.append(float(s))
    number += 1
    
ky = float(input('探す値：'))

idx = seq_search(x, ky)
if idx == -1:
    print('その値の要素は存在しません。')
else:
    print(f'それはx[{idx}]にあります。')

これで、float型の不動小数点数(実数)の配列から探索が可能になりました。

list3C-2

#線形探索を行う関数seq_searchの利用例(その2)

from ssearch_while import seq_search

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

print(f'{t}中の5.6の添字は{seq_search(t, 5.6)}です。')
print(f'{s}中の"n"の添字は{seq_search(s, "n")}です。')
print(f'{a}中の"DTS"の添字は{seq_search(a, "DTS")}です。')

番兵法

先のプログラムは繰返しのたびに二つの終了条件をチェックしていました。
このコストを半分に抑えるのが、番兵法だそうです。
本来のデータの末尾に探索するデータを追加し、発見されなかった場合の条件付けをする必要がなくなるというものです。

list3-3

#ssearch_sentinel.py
#線形探索(番兵法)

from typing import Any, Sequence
import copy

def seq_search(seq:Sequence, key: Any) -> int:
    """シーケンスseqからkeyと一致する要素を線形探索(番兵法)"""
    a = copy.deepcopy(seq)#aはseqを深くコピーして参照する(aの参照先をリストxの深いデータをコピーして参照）
    a.append(key)#リストaにkeyを追加(kyをリストの末尾に追加するためリストはxではなくxの末尾にkyを追加したリストを参照する)
    
    i = 0
    while True:#Trueの間
        if a[i] == key:#aのi番とkeyが一致したら
            break #処理を終了
        i += 1 #iに1を加えて参照
    return -1 if i == len(seq) else i #while文の繰り返しが終了したとき本体のデータか番兵かを判定する

if __name__ == '__main__':
    num = int(input('要素数：'))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]:'))
        
    ky=int(input('探す値：'))#キーkyの読み込み
        
    idx = seq_search(x, ky)#kyと等価な要素をxから探索
        
    if idx == -1:
        print('その値の要素は存在しません。')
    else:
        print(f'それはx[{idx}]にあります。')

ファイル名を付けたものでif文を省略してない形のコードも貼っておきます。

ssearch_sentinel.py

#線形探索(番兵法)(list3-3の return -1 if i == len(seq) else iを省略せずに書いた形)

from typing import Any, Sequence
import copy

def seq_search(seq:Sequence, key: Any) -> int:
    """シーケンスseqからkeyと一致する要素を線形探索(番兵法)"""
    a = copy.deepcopy(seq)#aはseqを深くコピーして参照する(aの参照先をリストxの深いデータをコピーして参照）
    a.append(key)#リストaにkeyを追加(kyをリストの末尾に追加するためリストはxではなくxの末尾にkyを追加したリストを参照する)
    
    i = 0
    while True:#Trueの間
        if a[i] == key:#aのi番とkeyが一致したら
            break #処理を終了
        i += 1 #iに1を加えて参照
    if i == len(seq):
        return -1
    else:
        i#while文の繰り返しが終了したとき本体のデータか番兵かを判定する

if __name__ == '__main__':
    num = int(input('要素数：'))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]:'))
        
    ky=int(input('探す値：'))#キーkyの読み込み
        
    idx = seq_search(x, ky)#kyと等価な要素をxから探索
        
    if idx == -1:
        print('その値の要素は存在しません。')
    else:
        print(f'それはx[{idx}]にあります。')

書き換えシリーズ
コードを書いていて気になったのでメモ程度に書いておきます

if i == len(seq):
        return -1
else:
    i

の部分を

return -1 if i == len(seq) else i

に短縮して書けるというのを初めて知りました。ルールがわかると簡潔にコーディングできそうですね。

これで、ループが抜けたときにだけ条件分岐されるようになりました。
最後に文字を追加することで、省略できるとは…なかなか思いつかない発想です。
（高校数学の授業を思い出す）
Excelとかやっていると活用イメージが湧く気がします。
読破したときに、データの活用がどれくらい効率的にできるか楽しみです。

本日は以上です。ありがとうございました。