今回は小ネタでPythonでリストから一番近い値を探索する方法です。
さいきん、paizaのスキルチェックだったり、AtCoderをはじめてみたんですが、この手の知識が必要な問題がありました。
備忘として残しておきます。
内容
例えば以下のようなリストがあるとして、指定された値に一番近い値を返すような場合です。
[1, 5, 10, 15, 20]例えば7を指定したら5、13を指定したら15を返したい、というような要件です。
標準のbisectモジュール
調べたところnumpyを使ったりといろいろ方法はありそうですが、今回は標準の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のインデックス１の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
Share