PythonAlgorithm

Python リストに一番近い値を探索する方法

更新日:2022-11-03 公開日:2022-10-23

今回は小ネタでPythonでリストから一番近い値を探索する方法です。
さいきん、paizaのスキルチェックだったり、AtCoderをはじめてみたんですが、この手の知識が必要な問題がありました。
備忘として残しておきます。

内容

例えば以下のようなリストがあるとして、指定された値に一番近い値を返すような場合です。

[1, 5, 10, 15, 20]


例えば7を指定したら513を指定したら15を返したい、というような要件です。

標準のbisectモジュール

調べたところnumpyを使ったりといろいろ方法はありそうですが、今回は標準のbisectモジュールを使う方法を紹介します。
詳細は公式の解説に詳しいです。
bisect --- 配列二分法アルゴリズム

このモジュールは、挿入の度にリストをソートすることなく、リストをソートされた順序に保つことをサポートします。大量の比較操作を伴うような、アイテムがたくさんあるリストでは、より一般的なアプローチに比べて、パフォーマンスが向上します。動作に基本的な二分法アルゴリズムを使っているので、 bisect と呼ばれています。ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界条件はすでに正しいです!)。


bisect_left


このbisectモジュールのbisect_leftを使用します。
配列と値を指定すると、挿入されるべきインデックスを返してくれる…という便利な関数です。
簡単に動作を確認してみましょう。

from bisect import bisect_left

an_iterable = [1, 5, 10, 15, 20]
print(bisect_left(an_iterable, 7))
>>>
2


指定した7は、渡した配列an_iterableのインデックス1の5の次に入るので、2が返ってきます。

両端の値を指定すると最初と最後のインデックスが返ります。

print(bisect_left(an_iterable, 0))
print(bisect_left(an_iterable, 25))
>>>
0
5


余談ですが、文字列のリストでも同じように動作します。

singers = ['Akiko yano', 'Minako Yoshida', 'Taeko Onuki']
print(bisect_left(singers, 'Eichi Otaki'))
>>>
1


リストの一番近い値を見つける

以下のような関数を書きます。

from bisect import bisect_left


def get_nearest_value_in_list(an_iterable: list, target: int) -> int:
    """リストの中から最も近い値を探索して返す"""
    # 最初にソートする
    an_iterable.sort()
    # ターゲットから挿入されるべきインデックスを取得
    index = bisect_left(an_iterable, target)

    # indexが先頭の場合は先頭の要素
    if index == 0:
        return an_iterable[0]
    # indexが末尾の場合は末尾の要素
    if index == len(an_iterable):
        return an_iterable[-1]
    # 前後を比較してtargetに近い方を返す
    a = target - an_iterable[index - 1]
    b = an_iterable[index] - target
    if a <= b:
        return an_iterable[index - 1]
    else:
        return an_iterable[index]


まず配列を昇順でソートをします。
そうして、bisect_left関数で与えられたtargetの挿入されるべきインデックスを取得します。
あとは返り値に応じて、要素を返している、という感じです。

a_list = [1, 5, 10, 15, 20]
print(get_nearest_value_in_list(a_list, 13))
>>>
15


パフォーマンスも悪くなく、100万の要素があるリストから探索しても0.2秒ほどでした。

import random
import time

a_list = [random.randint(0, 100000000) for _ in range(1000000)]
start = time.time()
get_nearest_value_in_list(a_list, 5287)
print(time.time() - start)
>>>
0.265625