PyPy 7.3.1 でリスト内包表記が遅くなくなった件について
タイトルでもう言いたいことは概ね終わっているのですが…….
Python 競技プログラミング高速化tips (PythonでAtcoderをやる際に個人的に気を付けてること) で言及されているように、PyPy のリスト内包表記は遅いという事実がありました.
ところで https://morepypy.blogspot.com/2020/04/pypy-731-released.html に以下のような文があります.
improved JIT code generation for generators (and generator expressions in particular) when passing them to functions like sum, map, and map that consume them.
リスト内包表記って、ジェネレータ式を list 関数に渡しているだけなような!?
$ cat 1.py
n = 10**7
a = [0]*n
for i in range(n):
a[i] = i*2
$ cat 2.py
n = 10**7
a = [i*2 for i in range(n)]
$ ./pypy3 --version
Python 3.6.9 (2ad108f17bdb, Apr 07 2020, 03:05:35)
[PyPy 7.3.1 with MSC v.1912 32 bit]
$ time ./pypy3.exe 1.py
real 0m0.149s
user 0m0.000s
sys 0m0.000s
$ time ./pypy3.exe 2.py
real 0m0.136s
user 0m0.015s
sys 0m0.000s
リスト内包表記のほうが速い!!
$ ./pypy3 --version
Python 3.6.9 (1608da62bfc7, Dec 23 2019, 12:38:24)
[PyPy 7.3.0 with MSC v.1911 32 bit]
$ time ./pypy3.exe 1.py
real 0m0.146s
user 0m0.000s
sys 0m0.015s
$ time ./pypy3.exe 2.py
real 0m0.440s
user 0m0.000s
sys 0m0.015s
PyPy 7.3.0 ではリスト内包表記が3倍くらい遅い.
AtCoder の言語アップデートは残念ながら PyPy 7.3.0 なんですよね. 悲しみが止まりません.
追記: なお文字列の加算が絶望的に遅いのは健在です.
$ cat 3.py
n = 10**5
res = 'a'
for _ in [0]*n:
res += 'a'
$ time ./pypy3 3.py
real 0m1.476s
user 0m0.000s
sys 0m0.015s
$ time python3 3.py
real 0m0.082s
user 0m0.015s
sys 0m0.062s