Pythonでアルゴリズムを学んでみる-線形探索

投稿日: 2021年3月5日更新日: 2021年3月5日

カテゴリ: Python Algorithm

概要

線形探索のコードをPythonで書いてみます。

ゴール

線形探索とは何か・どのように考えればコードを組み立てられるのか理解することを目指します。

方針決め

探索方法をどのようにコードで表現するかを考えることから始めます。頭の中のアルゴリズムをコードへ変換する場合、次の手順で書いていくと迷いづらくなるはずです。

アルゴリズムを単純な方法の集まりに分ける
母国語で擬似コードを書いてみる

これに従って考えてみましょう。

アルゴリズムの解釈

リストを一直線に走査するだけなので、これ以上分解する必要はなさそうです。一直線に調べるということは、ループで順に要素を探索することで実現できます。

擬似コード

いきなり実装コードを書いても良さそうですが、基礎の段階から流れを固めておくためにも、まずは擬似コードを書いてみます。

    def 線形探索(探すリスト, 探したい要素):
    for 要素 in 探すリスト:
        if 要素 == 探したい要素:
            return 今見ている探すリストのインデックス

    return None

forループで探索対象のリストを順に走査し、目的の要素が見つかれば対象のインデックスを・見つからなければNoneを返却します。

本当はインデックスをリストから得るために少し工夫が必要ですが、ここではコードの雰囲気をイメージすることが重要なので割愛しています。複雑な処理も骨組みを用意してから肉付けしていくと、少しずつ立ち向かえるようになるはずです。

実装

線形探索はシンプルでとっつきやすいアルゴリズムなので、早速実装へと進んでいきましょう。

コード

とはいえ命名や型ヒントなどが少し加わったぐらいですので、擬似コードと容易に対応付けられるかと思います。早速見てみましょう。

    # src/linear_search.py
from typing import Union


# Python3.10以降であれば、戻り値の型は`int | None`と表現することもできます
def search(search_list: list[int], target: int) -> Union[int, None]:
    """
    線形探索でリストから対象要素を探索

    :param search_list: 探索対象リスト
    :param target: 探索対象
    :return: 対象が存在->リスト内のインデックス 存在なし->None
    """

    for index, item in enumerate(search_list):
        if item == target:
            return index

    return None

さて、できあがったコードを眺めてみると、文法的には特に難しいところはないかと思います。しかし、なぜ探索処理を関数で分けたのか・なぜリストや探索要素を引数で受け取るのかなど、なぜそのような記述となったのかは、完成形だけでは見えづらくなってしまっています。

書いたコードの背景を言語化することができるようになれば、コードの理解もぐっと進むはずです。早速見てみましょう。

※ 以降の背景は探索やソート処理全般に言えることなので、アルゴリズムがとてもシンプルな線形探索で掘り下げておきます。

なぜ探索処理を関数で独立させたのか

まずは、線形探索をコードで実現するとき、関数で記述した理由から追っていきます。例えば、線形探索でリストに目的の要素が存在するか走査したいということであれば、

main処理にべた書き
結果をprintする処理も含めて関数化
探索処理だけを関数化
リスト・探索要素を属性に持ち、探索処理をメソッドに持つクラスを定義

などの実装方法が考えられます。多くの選択肢がある中、なぜ関数で書くことを選んだのでしょうか。これは、線形探索に必要な処理を最もシンプルに表現できると判断したからです。

main処理にすべてを書いていると、一度に頭に入れておくもの(変数のスコープ・処理の境界など)が増えて読みづらくなってしまいます。

クラスは線形探索に関わるものを集約させることができますが、関数に比べると記述量が増えてしまいます。探索処理を表現するには、やや大仰に見えるかもしれません。

※ クラス・関数どちらを選ぶかは状況によって変わりますし、好みによるところもあるので、今回は好きな方で書くのもよいと思います。

関数で線形探索を表現してみると、処理の範囲は短くまとまっていますし、変数の型・スコープも明確で読みやすい...はずです。

以上のことから、単純なアルゴリズムであれば、以降も関数で記述していくことにします。

なぜ関数はリスト・探索要素を引数に受け取り、探索結果(インデックス)を返すのか

さて、関数で線形探索を書くことに決めても、まだ書き方には検討の余地があります。特に関数を定義するときに考えるべきは、何を入力とし、何を出力とするかです。それぞれ考えてみましょう。

出力

まず関数を書くときは、こういう値を返してくれる関数が欲しいなー、といったところから始まります。ですので、関数の出力から見ていきます。

ここで注目すべきは、関数内部で結果をprint文で出力するのではなく、探索要素のインデックス/Noneを探索結果として返却していることです。

このように値を生成する処理・値をもとになんらかの命令を実行する処理を分けておくと、テストコードが書きやすくなります。

関数の戻り値のみをテストするのと、関数内部で線形探索の結果が○○になるから、print文でこういう文が出力されるはず、といったことをテストするのとでは、テストの労力が大きく異なります。

ひとまずは処理を、入力をもとに値を返す関数の単位に切り出せるとテストが書きやすくなるんだな、ということを覚えておきましょう。

テストコード以外の側面も見ておきましょう。出力を値としておけば、他の処理と容易に組み合わせることができます。コード例で見るとイメージしやすいでしょう。

    id_list = [1, 2, 3, 4, 5]
index = search(id_list, 3)
if index is not None:
    # IDをもとにユーザを探索的な処理
    print(get_uder_by_id(index))

処理をシンプルに保つとコードが読みやすくテストが書きやすくなるだけでなく、再利用性も高まるというメリットが得られます。

入力

関数の出力が決まったので、出力の元になる入力を見てみます。線形探索の関数では、探しにいくリスト・探したいものを指定していました。

ここでは入力を、呼び出し元や関数内部ではなく、引数で定義した理由を考えてみたいと思います。

一言で表現すると、再利用性を高め、テストコードを書きやすくするためです。関数というものが入力から対応する出力を得るためのものであることから、出力と似たような表現になりました。

これだけではイメージが掴みづらいので、簡単なコードも見ておきましょう。

    # 呼び出し元で固定
global_list = [3, 2, 1]
target = 1


# search関数は、global_list, target変数がグローバルスコープに無ければ使えない
def search():
    ...


# 関数内部で固定
# 関数の挙動を変えることができず、出力が固定されてしまう
def search():
    inner_list = [1, 2, 3]
    inner_target = 1
    ...


# 引数に定義
# 呼び出すときに考えることは、引数に探索リストと探索要素を指定するのみ
def search(search_list: list[int], target: int) -> Union[int, None]:
    ...

コードで並べて比べてみると、引数で入力を定義した、一見複雑そうな書き方が最もシンプルに扱えることが分かるはずです。

さて、入力と出力が決まることで、関数の完成形が見えてきました。

最初に見たときは色々なことが書かれていて難しそうでしたが、なぜそのような書き方を選んだのか背景が掴めれば、自分の手に馴染むようになってくるのではないかと思います。

まとめ

線形探索アルゴリズムについて見てきました。

出来上がったコードをただ眺めるだけではなく、背景まで考え自分の言葉で表現できるようになれば、1から自らの手でコードを組み上げる地力が身につくはずです。

記事はGitHubでも公開しています。間違い・よりよい書き方などございましたらIssueやPRを頂けるとうれしいです。

Author:

a-pompom:

GitHub, Bluesky

A.blog