Pythonのin演算子を高速化するには？リストからセット・辞書への切り替えが鍵

Pythonのin演算子がリストで遅い理由

Pythonのin演算子をリスト（list）に対して使用すると、計算量はO(n)になります。これは、指定した要素が見つかるまでリストの先頭から順番にすべての要素を走査していくためです。そのため、リストのサイズが大きくなるほど、存在判定にかかる時間は線形に増加してしまいます。

セットや辞書なら約O(1)で高速検索が可能

同じ「要素が含まれているか」の判定でも、セット（set）や辞書（dict）といったハッシュベースのデータ構造を使えば、平均的にO(1)——つまりほぼ一定の時間——で検索できます。内部でハッシュテーブルが採用されているおかげで、データ量が増えても検索速度がほとんど低下しないのが大きな強みです。

# リストの場合：遅い O(n)
items = [1, 2, 3, ..., 1000000]
if 999999 in items:
    ...

# セットの場合：速い 約O(1)
item_set = set(items)
if 999999 in item_set:
    ...

注意点：データ構造ごとの特性を理解しよう

ただし、単純に置き換えれば必ず速くなるというわけではありません。セットや辞書は「検索」こそ非常に高速ですが、要素の挿入（追加）にはハッシュ値の計算などのオーバーヘッドが発生し、リストのappend()よりも時間がかかるケースがあります。

したがって、どのデータ構造を選ぶべきかは、実際の使い方のパターンによって判断するのが賢明です。

• 存在判定（メンバーシップ検索）が多い場合 → セットや辞書が圧倒的に有利
• 要素の追加・削除が頻繁で検索が少ない場合 → リストの方が適していることもある
• 同じデータ集合に対して繰り返し検索する場合 → 最初にセットへ変換しておくと、全体の処理時間を大幅に短縮できる

まとめ

Pythonでin演算子による存在判定を高速化したいなら、リストではなくセットや辞書を使うのが基本戦略です。ただし、挿入コストとのトレードオフが存在するため、データの追加・更新・検索それぞれの頻度バランスを見極め、状況に応じて最適なデータ構造を選択することが、パフォーマンス改善成功のカギとなります。