Python のセットがすごい

Pythonのセットを使ったほうが速いだろうとおもったんですけど、こんなに差がでると思わなかった。

~$ python -m timeit -n 1000 "[x for x in range(1000) if x in range(500, 1500)]"
1000 loops, best of 3: 28.2 msec per loop

~$ python -m timeit -n 1000 "set(range(1000)).intersection(range(500, 1500))"
1000 loops, best of 3: 120 usec per loop

リスト内包が約235倍時間かかりますね。リストをセットにするのも時間かからないので、合併や、交差は絶対set()を使ったほうがいいですね。

Update

range(500, 1500)を1000回くらいよばれてしまっているので、一回呼び出すようにすると、28.2msecが18.2msecになった。まだまだ150倍くらい違いますよね。

~$  python -m timeit -n 1000 "range1500=range(500, 1500);[x for x in range(1000) if x in range1500]"
1000 loops, best of 3: 18.2 msec per loop

Update 2

Twitter で言われたんですが、

何で時間かかっているというと、内包自体ではなくて、内包の中の if 文が 1000回 実行されるわけです。

まずは、range(1000)の時間をチェックする。

~$ python -m timeit -n 1000 "range(500, 1500)"
1000 loops, best of 3: 12.9 usec per loop

update したバージョンだと、 range() は2回しか呼ばれてないので、ここが遅いというわけではないですね。

一回 if で使っている in のチェックをします。

~$ python -m timeit -n 1000 "1 in range(1000)"
1000 loops, best of 3: 12.3 usec per loop

実際にこれは 1000 回実行されているので、 12.3 µsec * 1000 = 12.3 msec くらいかかりますね。

さらにこれはベストケースです。チェックしたい値が最後に入っている場合は

~$ python -m timeit -n 1000 "1000 in range(1000)"
1000 loops, best of 3: 35.2 usec per loop

このテストで結構、差が出る。ここが主にかかっているところと思われます。なので、結論として、「set()がすごい」よりも、「in list()が遅い」ということのほうが適切かもしれません。