2024.07.05 2024.08.27

記事内に商品プロモーションを含む場合があります

リストと集合で大きく違う！”if A in B”の処理速度の罠｜Python

Aru

Pythonでよく見かける”if A in B”という構文ですが、このシンプルなコードがパフォーマンスに影響を与えるということをご存知でしょうか？特に、大量のデータを扱う場合、Bが集合かリストかによって処理速度に大きな違いが生じます。この記事では、一見単純なこの構文に潜む罠について解説したいと思います。

Contents

“if A in B”という記述の処理
データの種類による演算量の違い
時間を測定してみる
まとめ

“if A in B”という記述の処理

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

Pythonには一見シンプルに見えるのに、処理量が大きな記述が存在します。

それは、

if A in B: ...

という表記です。

これは、「Bの中にAが存在するかどうか」をチェックする処理です。

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

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

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

演算量について

この記事では、演算量をO(n)という形式で表現します。O(n)と書くと、データのサイズ(n)に比例して処理時間がかかることを意味します。また、O(1)と書くとデータのサイズに処理時間が依存しないことを意味します。例えば、２重ループはO($n^2$)などと表現します。これは、データサイズの二乗に処理時間が比例することを意味します。

リスト（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`の演算量
リスト	`O(n)`
タプル	`O(n)`
集合（set）	`O(1)`
辞書（dict）	`O(1)`

プログラム全体を把握していないと、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万個のデータ（B）を生成し、1000回異なる値（A）とマッチングを行っています。

実行結果
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倍）。

O(n)のリスト・タプルと、O(1)のset, dictの差はかなり大きいです。

具体的には、リスト（タプル）では処理に6秒以上かかっていますが、set（dict）は、その10万分の1くらいです。

ということで、なるべくsetやdictを使った方がよいということになります。

ちなみに、リストからsetへの変換は以下のコード１行で行うことができます。検索を大量に行う前に（ループの手前で）、リスト→setに変換しておけば処理速度を大幅にアップさせることが可能です。

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

まとめ

実務のコードでif A in BのコードでBがリストのパターンを結構見かけていたのを思い出して記事にしました。コードを記述した人は、あまり処理量を意識していない人だと思いますが、これが最内ループで、何百万回、何億回と実行される部分であれば処理が遅いといった原因になるかもしれません。

これは一例ですが、Pythonでは、重い処理を数行で書けるため、気づかないうちにとんでもない処理量のコードを仕込んでしまうことがありますので注意が必要です。演算量を意識したプログラミングを心がけましょう。

演算量を意識したプログラミングには競技プログラミングの問題を解くことをお勧めします。演算量を意識しないと正解できない問題が多いので、問題を解いていくうちに自然と演算量を意識したプログラミングが身につきます。

AtCoderで役立つ記事一覧（Python, Go言語）

#if文 #list #python #Set #処理量