pypy bool type is slow

Fix

Initially, it was published with the title "python bool type is slow", but the content of the article applies only when using pypy, which was an error. I'm sorry I gave you incorrect information.

What i want to say

When using pypy in competitive programming, it is slow to handle True / False as a bool type. Let's use the int type.

Overview

I think it's common to have some flags and branch the process accordingly.

f = 1

Some people

f = True

I'm sure there are people who say that, but I expect the same thing to happen in both cases.

However, in reality, there is a difference in execution speed.

To be precise, there is no difference in the judgment of the truth value, and there is a difference in rewriting. I will talk about this later.

Experiment

Let's compare with the following code. The execution environment is PyPy3 (3.7.0) in the code test of atcoder.

int.py


f = 1
for i in range(10**9):
    if f:
        f = 0
    else:
        f = 1

bool.py


f = True
for i in range(10**9):
    if f:
        f = False
    else:
        f = True

The result looks like this. (Even if you do it multiple times, it looks like this)

code Execution time memory
int.py 2423 ms 25640 KB
bool.py 7439 ms 25612 KB

Isn't the difference bigger than I expected? ?? This alone increases the risk of TLE if it is a problem with severe execution speed. (Actually, I was addicted to ABC182 E)

Consideration

So, it's just a case of using pypy in competitive programming, but if you want to use flags, use int type instead of bool type.

I tried various experiments, but it seemed that it was not the true / false judgment but the rewriting of the value that affected the speed difference.

Please note that rewriting is a prerequisite for using it as a flag. For example, if you set a flag in the middle and keep it up after that, there should be no difference in speed. If you stand or fold it, you may TLE for such a trivial reason.

Unless you are particular about it, we recommend using the int type.

bonus

I also tried str.

str.py


a = "True"
for i in range(10**9):
  if a == "True":
    a = "False"
  else:
    a = "True"

The results are as follows. It's the slowest, isn't it?

Execution time memory
8183 ms 25612 KB

Postscript

When I ran it with python3, it was within the margin of error. Thank you @shiracums for pointing this out.

Recommended Posts

pypy bool type is slow
pandas idxmax is slow
PyTorch DataLoader is slow
Pipenv locking is too slow
Python Boolean operation return value is not always bool type
Which is better, PyPy or Python?