Pythonの”if A in B”の演算量（処理量）に注意しよう|リストと集合の処理速度の違いについて

Pythonのコードを見ていて”if A in B”というコードを見かけたことはないでしょうか。実は、このコードの処理時間に注意する必要があります。気づかずに多様すると思わぬ速度低下につながります。

if A in Bの処理について

コンピュータがある操作を実行するのに必要な「時間」や「計算のステップ数」のことを「演算量（or 計算量）」といいます。演算量を知ることは、プログラムの効率性を測るために非常に重要です。演算量が少ないほど、プログラムは速く動作します。

Pythonで注意しなければならないのは

if A in B: ...

という表記です。

これは、Bの中にAが存在するかどうかをチェックする操作になります。

実はこの操作、Bのデータの種類によって演算量が大幅に変化します。

この記事では、リスト、タプル、集合（set）、辞書（dict）についてそれぞれの演算量を説明します。

データの種類による演算量の違い

リスト（List）の場合

リストは、要素を順番に並べたデータ構造です。

if A in Bで検索を行う場合、1番目の要素から順番にAと一致しているかチェックしていきます。このため、演算量は平均してO(n)となります。つまり、リストの要素数nに比例して検索処理が増加します。

タプル（Tuple）の場合

タプルはリストと似ていますが、値が変更ができない（不変）データ構造です。

if A in Bで検索を行う場合、リストと同様に1番目の要素から順番にAと一致しているかチェックしていきます。このため、演算量は平均してO(n)となります。つまり、リストの要素数nに比例して検索処理が増加します。

集合（set）の場合

set型（集合型）は、リスト型と似ていますが重複したデータを格納できず、インデックス（添え字）でデータにアクセスできないデータ構造です。

if A in Bで検索を行う場合は、要素数に関係なく一定の処理量で要素を見つけることができるので、演算量はO(1)となります。

具体的には、ハッシュテーブルという仕組みを利用しています

辞書（dict）の場合

辞書は、キーと値のペアで構成されているデータ構造です。

集合と同じく、平均してO(1)です。キーを使って値を高速に見つけることができます。

データの種類による演算量の違いについて

以上をまとめると以下のようになります。

これを見てわかるように、リスト・タプルは要素数が増えるほど演算量が増加することがわかります。

例えば、Bの要素数が100万個だとすると、リストやタプルでif A in Bと書くと、100万回ループさせるのと同じ処理量がかかるわけです。

実際に、業務で利用するコードでif A in Bという形でBがリストというケースを結構見かけました。

おそらく、if A in Bと１行で欠けてしまうので、演算量に対するケアが抜け落ちてしまっていたのだと思います。

これがボトルネックになって、プログラムが遅いとかなりますので、複雑な処理を短いコードで書けるPythonの怖いところだと思います。

時間を測定してみる

リスト、タプル、集合、辞書の演算量は上の通りです。では、実際にどれほどの違いがあるのかを計測してみます。

以下は計測プログラムです。

import time
import random

# データセットのサイズを定義
size = 1000000
search_elements = 1000

# ランダムな整数リストを生成
data_list = random.sample(range(size), size)
# 各データ構造にデータをコピー
data_set = set(data_list)
data_dict = {key: None for key in data_list}
data_tuple = tuple(data_list)

# 検索する要素を生成
search_list = random.sample(range(size), search_elements)

print(f"list size = {len(data_list)}")
print(f"search_list size = {len(search_list)}")

# 時間計測のヘルパー関数
def measure_time(structure, search_list):
    start_time = time.time()
    for item in search_list:
        if item in structure:
            pass
    end_time = time.time()
    return end_time - start_time

# リストの検索時間
print("LIST SEARCH TIME")
list_time = measure_time(data_list, search_list)
print(f"List search time: {list_time:.6f} seconds")

# タプルの検索時間
print("TUPLE SEARCH TIME")
tuple_time = measure_time(data_tuple, search_list)
print(f"Tuple search time: {tuple_time:.6f} seconds")

# 集合の検索時間
print("SET SEARCH TIME")
set_time = measure_time(data_set, search_list)
print(f"Set search time: {set_time:.6f} seconds")

# 辞書の検索時間
print("DICT SEARCH TIME")
dict_time = measure_time(data_dict, search_list)
print(f"Dictionary search time: {dict_time:.6f} seconds")

計測では、100万個のデータを生成し、1000回異なる値の検索を行っています。

実行結果
list size = 1000000
search_list size = 1000
LIST SEARCH TIME
List search time: 6.785294 seconds
TUPLE SEARCH TIME
Tuple search time: 6.417983 seconds
SET SEARCH TIME
Set search time: 0.000117 seconds
DICT SEARCH TIME
Dictionary search time: 0.000577 seconds

リストとタプルの処理時間の差はそれほどないです。setとdictの差は思ったよりありました（5倍くらい）。

ただ、リスト・タプルとset・dictの差は大きいです。

リスト（タプル）では、6秒以上かかっていますが、set（dict）は、その10万分の1くらいです。リストを集合にするのは、以下のコードを書くだけです。

s = set(l) # リストlを集合sに変換

検索を大量に行う前に、リスト→setに変換しておけば処理速度が大幅アップします。

まとめ

実務のコードにもif A in BのコードでBがリストのパターンをよく見かけていたので記事にしました。さすがに、100万個の要素があるということはないですが、何万回、何百万回もifを行うコードの場合、要素数が100個でもかなりの処理量になります。

Pythonはコードが手軽に書けて便利ですが、演算量は気にかけないととんでもなく遅いコードになることがありますので注意が必要です。