Python の集合演算のパフォーマンス比較

集合演算のパフォーマンスは、要素数や操作の種類によって大きく変わる。ここでは各演算の計算量と実測値を比較する。

基本操作の計算量

まず、基本操作の計算量を整理する。

操作	平均	最悪
x in s	O(1)	O(n)
s.add(x)	O(1)	O(n)
s.remove(x)	O(1)	O(n)
len(s)	O(1)	O(1)

最悪ケースは極端なハッシュ衝突が発生した場合で、通常は発生しない。

集合演算の計算量

2 つの集合 A と B に対する演算の計算量は以下のとおりだ。

演算	計算量
A \| B	O(len(A) + len(B))
A & B	O(min(len(A), len(B)))
A - B	O(len(A))
A ^ B	O(len(A) + len(B))

積集合が効率的なのは、小さいほうの集合の要素だけを調べればよいためだ。

# 積集合の内部実装（概念）
def intersection(a, b):
    if len(a) > len(b):
        a, b = b, a  # 小さいほうを基準に
    return {x for x in a if x in b}

実測による比較

実際に計測して確認する。

import time

def measure(name, func, iterations=1000):
    start = time.perf_counter()
    for _ in range(iterations):
        func()
    elapsed = time.perf_counter() - start
    print(f"{name}: {elapsed:.4f}s")

a = set(range(10000))
b = set(range(5000, 15000))

measure("union      ", lambda: a | b)
measure("intersection", lambda: a & b)
measure("difference ", lambda: a - b)
measure("symmetric  ", lambda: a ^ b)

積集合が最も高速で、和集合と対称差は同程度、差集合はその中間になる。

部分集合判定のパフォーマンス

部分集合判定 <= の計算量は O(len(小さいほう)) だ。

small = set(range(100))
large = set(range(10000))

# small が large の部分集合か
# small の全要素が large に含まれるか確認
# O(len(small)) = O(100)
print(small <= large)  # True

逆方向の判定も同じだが、実際に調べる要素数は異なる。

import time

small = set(range(100))
large = set(range(10000))

# small <= large: small の 100 要素を確認
start = time.perf_counter()
for _ in range(10000):
    small <= large
print(f"small <= large: {time.perf_counter() - start:.4f}s")

# large <= small: large の 10000 要素を確認、すぐに False
start = time.perf_counter()
for _ in range(10000):
    large <= small
print(f"large <= small: {time.perf_counter() - start:.4f}s")

large <= small は False になるが、最初の要素（large にあって small にない要素）を見つけた時点で終了するため、実際には高速だ。

リストとの比較

リストで同様の操作を行うとどうなるか。

import time

a_list = list(range(10000))
b_list = list(range(5000, 15000))

a_set = set(a_list)
b_set = set(b_list)

# リストでの和集合相当
start = time.perf_counter()
for _ in range(100):
    result = list(set(a_list) | set(b_list))
print(f"list union: {time.perf_counter() - start:.4f}s")

# set での和集合
start = time.perf_counter()
for _ in range(100):
    result = a_set | b_set
print(f"set union: {time.perf_counter() - start:.4f}s")

リストから一度 set に変換するオーバーヘッドがあるため、set をそのまま使うほうが圧倒的に高速だ。

リストで集合演算

毎回 set への変換が必要。O(n) の変換コストが発生。

set をそのまま使用

変換不要。純粋な集合演算のみ。

要素数による影響

要素数が増えると、計算時間も比例して増加する。

import time

for n in [1000, 10000, 100000]:
    a = set(range(n))
    b = set(range(n // 2, n + n // 2))
    
    start = time.perf_counter()
    for _ in range(100):
        a & b
    elapsed = time.perf_counter() - start
    print(f"n={n:>6}: {elapsed:.4f}s")

積集合の場合、小さいほうの要素数に依存するため、非対称な集合では注意が必要だ。

破壊的操作 vs 非破壊的操作

破壊的メソッド（update() など）は新しい集合を作らないため、わずかに高速だ。

import time

# 非破壊的
start = time.perf_counter()
for _ in range(10000):
    a = {1, 2, 3}
    b = a | {4, 5, 6}
print(f"union: {time.perf_counter() - start:.4f}s")

# 破壊的
start = time.perf_counter()
for _ in range(10000):
    a = {1, 2, 3}
    a.update({4, 5, 6})
print(f"update: {time.perf_counter() - start:.4f}s")

差は小さいが、大量のデータを処理する場合は破壊的操作のほうがメモリ効率もよい。

isdisjoint の最適化

isdisjoint() は共通要素がないかを調べるが、見つかった時点で即座に False を返す。

import time

a = set(range(10000))
b = set(range(10000, 20000))  # 共通要素なし
c = set(range(9999, 20000))    # 1 つだけ共通

# 共通要素なし: 全要素を調べる
start = time.perf_counter()
for _ in range(1000):
    a.isdisjoint(b)
print(f"disjoint (no common): {time.perf_counter() - start:.4f}s")

# 共通要素あり: すぐに False
start = time.perf_counter()
for _ in range(1000):
    a.isdisjoint(c)
print(f"disjoint (has common): {time.perf_counter() - start:.4f}s")

共通要素がある場合のほうが高速になる。最初に見つけた共通要素で判定が終わるためだ。

まとめ

集合演算を効率的に行うには、データを最初から set として保持しておくことが重要だ。リストから毎回変換するのは非効率的である。また、積集合は小さいほうの集合サイズに依存するため、非対称な集合を扱う際はこの特性を意識するとよい。