Python簡単実験：集合も内包の方が速い

Pythonには複数のデータを扱うのに、リストだけでなく集合(set)もある。
今回は、集合にいっぱい要素を突っ込んだり消したりしたときの速度を調べてみる。
空集合を作り、自然数を1から10,000,000まで1000万個を突っ込んでみた。

>>> import time,os,psutil,sys
>>> pid = psutil.Process(os.getpid())
>>>
>>> b = set()
>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> for i in range(1,10000001):
...     b.add(i)
...
>>> time.time() - t0, pid.memory_info().rss-sz0
(2.310807466506958, 592703488)

2.3秒/1000万個=0.23マイクロ秒／個のペースで追加できている。 そして、メモリは592MB消費したようだ。

同じことを内包を使って実行してみる。

>>> b = set()
>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> b = {i for i in range(1,10000001)}
>>> time.time() - t0, pid.memory_info().rss-sz0
(0.6817171573638916, 592707584)

0.60秒/1000万個=0.06マイクロ秒／個で、4倍近く高速になっている。
でも1000万個追加するのに、前回のリストのときには0.36秒だったので、集合への追加はリストのアペンドに比べて倍近く時間が掛かっていることが分かる。
集合は、もし同じものがあったら追加されないので、そのあたりの判定も必要になる。

さて、追加だけでなく、削除もやっておこう。
集合の削除メソッドには、remove(x)とdiscard(x)がある。
discardは要素xが存在しなくてもエラーにはならず無視されるだけだが、removeではKeyErrorが発生してしまうので気をつけよう。

>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> for i in range(10000000,0,-1):
...     b.discard(i)
...
>>> time.time() - t0, pid.memory_info().rss-sz0
(2.336066484451294, -324263936)
>>> b
set()

消すのは、内包を使わないadd()とほぼ同じ時間かかることが分かった。

ということで、予想通り、集合でも内包を使った方が遥かに高速になるのであった。