Pythonのin演算子は遅い? リストとセット/辞書の計算量比較

# 基本的なinの使い方

# リスト(list)
fruits = ["apple", "banana", "cherry"]
print("banana" in fruits)   # True
print("grape" not in fruits)  # True

# セット(set)
colors = {"red", "green", "blue"}
print("green" in colors)    # True
print("yellow" in colors)   # False

# 辞書(dict) - 注意: inは「キー」に対して判定します
person = {"name": "Alice", "age": 20}
print("name" in person)     # True (キー"name"がある)
print("Alice" in person)    # False (値は直接は対象外)

# dictで値や(キー, 値)の存在を調べる
person = {"name": "Alice", "age": 20}

print("Alice" in person.values())   # 値に"Alice"があるか → True
print(("age", 20) in person.items())  # ("age", 20)というペアがあるか → True

# リストのinが先頭から順に比較していることを可視化するサンプル

class Counter:
    comparisons = 0  # 比較回数を数えるためのクラス変数

class Probe:
    """何と比較してもFalseを返すオブジェクト。比較回数だけ数える。"""
    def __eq__(self, other):
        Counter.comparisons += 1
        return False

# ケース1: どれとも一致しない(最後まで探索する)
lst = [Probe() for _ in range(5)]
print(object() in lst)  # 常にFalse
print("比較回数:", Counter.comparisons)  # 5回に等しい

# ケース2: 途中で一致したことにするオブジェクト
class MatchFirst:
    def __eq__(self, other):
        Counter.comparisons += 1
        return True  # 最初の比較で一致したとみなす

Counter.comparisons = 0
lst2 = [MatchFirst(), Probe(), Probe()]
print(object() in lst2)  # 最初でTrueになり探索が止まる
print("比較回数:", Counter.comparisons)  # 1回に等しい

# リストとセット/辞書でinの速度をざっくり比べる簡易ベンチマーク
# 実行環境で差は出ますが、増加傾向の違いを感じられます。

import time

def bench(n=100_000, trials=10_000):
    data = list(range(n))
    s = set(data)
    d = {x: None for x in data}

    hit = n - 1   # 末尾(リストの「見つかるが遅い」例)
    miss = -1     # 存在しない(リストの最悪側)

    def run(label, container, needle):
        start = time.perf_counter()
        for _ in range(trials):
            needle in container
        end = time.perf_counter()
        return f"{label}: {(end - start)*1e3/trials:.6f} ms/回"

    print(f"N={n}, trials={trials}")
    print(run("list hit ", data, hit))
    print(run("list miss", data, miss))
    print(run("set  hit ", s, hit))
    print(run("set  miss", s, miss))
    print(run("dict hit ", d, hit))
    print(run("dict miss", d, miss))

bench(100_000, trials=5_000)

d = {"id": 123, "name": "Alice"}
print("name" in d)             # True: キーの存在
print("Alice" in d)            # False: 値は対象外
print("Alice" in d.values())   # True: 値の存在チェック

# 大量データでの存在チェックはsetに変換してから
users = [f"user{i}" for i in range(200_000)]

# 検索を繰り返すなら、最初にsetへ変換しておく
user_set = set(users)

targets = ["user199999", "userX", "user1000"]
for t in targets:
    print(t, t in user_set)  # 平均O(1)で高速

# IDからユーザー名を引く
name_by_id = {100: "Alice", 200: "Bob", 300: "Carol"}

uid = 200
if uid in name_by_id:          # キーの存在チェック
    print(name_by_id[uid])     # 値を取り出す(平均O(1))

# ハッシュ不可の例: listはsetに入れられない
try:
    s = set()
    s.add([1, 2, 3])  # TypeError
except TypeError as e:
    print("エラー:", e)

# ハッシュ可能な代替: tupleやfrozensetを使う
s = set()
s.add((1, 2, 3))            # OK: tupleはimmutable
s.add(frozenset({1, 2, 3})) # OK: frozensetはimmutable
print("要素数:", len(s))

# 文字列の存在チェックを、大小文字とUnicode正規化をそろえて行う
import unicodedata

raw = ["Cafe", "café", "CAFE"]
# 正規化＋casefoldで基準化してからset化
normalized = {unicodedata.normalize("NFC", s).casefold() for s in raw}

query = "CAFÉ"  # 表記が異なるが同じ概念
key = unicodedata.normalize("NFC", query).casefold()
print(key in normalized)  # True

# ざっくりしたメモリ比較(コンテナ本体のみ)
# 実際の総メモリは要素分も加わるため、あくまで目安です。
import sys

n = 10_000
lst = list(range(n))
st = set(lst)
dc = {x: None for x in lst}

print("list容器サイズ:", sys.getsizeof(lst), "bytes")
print("set 容器サイズ:", sys.getsizeof(st), "bytes")
print("dict容器サイズ:", sys.getsizeof(dc), "bytes")