概要
集合の演算をするとき、得られる結果の要素数を小さくすることで実行速度を改善できる。
演算結果は新しい set オブジェクトで返されるため、要素数が大きいとオブジェクトの生成に時間がかかる。
背景
ABC157 D Friend Suggestions にて、ある集合の要素数を計算するために len(X-Y-Z) としたら TLE になったが len(X)-len(X&(Y|Z)) で AC できた。
なぜ速度が違うのか検証してみた。
|X| が大きいとき
問題の前提では $|X|,|Y|,|Z| \leq 10^5$ だが、今回は実際に遭遇した $|X| \gg |Y|,|Z|$ の条件を測定してみる。
from timeit import timeit
xyz = 'X=set(range(10**5)); Y=set(range(10)); Z=set(range(5,15))'
timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.3884289239649661
timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 0.0001103340182453394
結果は同じなのに、実行時間には実に3520倍の開きがある。
X, Y, Z の内容が同じとき
次に、 X, Y, Z すべてを $10^5$ 個の同じ要素にしてみる。
from timeit import timeit
xyz = 'X=set(range(10**5)); Y=set(range(10**5)); Z=set(range(10**5))'
timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.28364974400028586
timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 1.1718004010035656
今度は len(X)-len(X&(Y|Z)) の方が遅くなった。 X&(Y|Z) は元の集合と同じであり、結果の要素数が大きくなったためと考えられる。
一方、 len(X-Y-Z) は X-Y の段階で空集合が得られるためか、 1/3 程度に短縮した。
差集合 vs 積集合
問題を単純化して、差と積の演算だけを比較してみる。演算の他方を空集合として、それぞれ左右を入れ替えてみた。
from timeit import timeit
xy = 'X=set(range(10**5)); Y=set()'
timeit('X-Y', setup=xy, number=100)
# 0.16930873499950394
timeit('Y-X', setup=xy, number=100)
# 1.7047044821083546e-05
timeit('X&Y', setup=xy, number=100)
# 1.0746996849775314e-05
timeit('Y&X', setup=xy, number=100)
# 1.502997474744916e-05
差集合でも結果の要素数が小さいときは早い。どうやら、速度の差は演算の内容ではなさそうだ。
set の生成
Python ドキュメント set.differenceを参照すると、
set に含まれて、かつ、全ての other に含まれない要素を持つ、新しい集合を返します。
とある。そこで、要素数が大きい set の生成時間を測定してみる。
from timeit import timeit
timeit('set(X)', setup='X=set(range(10**5))', number=100)
# 0.16229172004386783
結局、結果の要素数が大きいとき、返す集合の生成に時間がかかっているだけだった。