Engineer in Tokyo

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 usec * 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() が遅い」ということのほうが適切かもしれません。