I've almost finished what I want to say in the title ...
[Python Competitive Programming Acceleration Tips (Personally Be careful when doing Atcoder in Python)](https://juppy.hatenablog.com/entry/2019/06/14/Python_%E7%AB% B6% E6% 8A% 80% E3% 83% 97% E3% 83% AD% E3% 82% B0% E3% 83% A9% E3% 83% 9F% E3% 83% B3% E3% 82% B0% E9% AB% 98% E9% 80% 9F% E5% 8C% 96tips_% 28 Python% E3% 81% A7Atcoder% E3% 82% 92% E3% 82% 84% E3% 82% 8B% E9% 9A% 9B% E3% 81% AB% E5% 80% 8B # Pypy% E3% 81% 98% E3% 82% 83% E3% 81% A0% E3% 82% 81% E3% 81% AA% E3% 82% 82% As mentioned in E3% 81% AE), there was the fact that PyPy's list comprehensions were slow.
By the way, [https://morepypy.blogspot.com/2020/04/pypy-731-released.html](PyPy 7.3.1 released) has the following sentence.
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 comprehension is just like passing a generator expression to the list function !?
$ 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
List comprehension is faster !!
$ ./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
List comprehensions are about three times slower in PyPy 7.3.0.
Unfortunately, the language update for AtCoder is PyPy 7.3.0, isn't it? Sadness doesn't stop.
Postscript: It is alive and well that the addition of strings is hopelessly slow.
$ 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
Recommended Posts