AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy

Overview

Participated in AtCoder ABC151. Solve Problem D in C ++ / Python3 / PyPy3 with a method that is probably not optimal for this problem ([Warshall-Floyd Method](https://ja.wikipedia.org/wiki/Warshall-Floyd Method)) I measured and compared it.

The result was that C ++ was more stable and 60-70 times faster when the problem size increased to some extent. If you have any concerns about TLE, it seems better to stop submitting ~~ Implement ~~ in Python.

Later, when I received a comment and submitted it in PyPy3 (2.4.0), I found that TLE was resolved. However, the execution time was 1191 msec, which was considerably slower than C ++'s 71 msec.

So, if you are worried about TLE, it seems better to 1. Submit implementation in C ++ 2. Implement in Python PyPy.

Background

Participated in AtCode ABC151. When I saw Problem D, I thought as follows.

"It can be solved by the method on the ant book (Warshall-Floyd method). But the nodes (mass) are connected only to the top, bottom, left and right, and the distance between adjacent nodes is always 1, so there is a more efficient method. so.

But O (N ^ 3) and N = 400, so 400 ^ 3 = 64,000,000, isn't it? It's a hassle to think of other methods, and I know that this will solve the problem, so let's use the Worshall-Floyd method. "

Implemented in Python without thinking too much. I debugged until the time limit (3 minutes ago) and submitted # 9476488 (20-01-12 22:37:01), but the result Is TLE. I was sad.

Later, I implemented it in C ++ and submitted # 9484896, and the execution time was 71msec, which was a margin. I want to refer to it in the future.

1/15 postscript

In the comment, "I did not get TLE when I put it out with PyPy 3. I got 3 WAs." Certainly, when I implemented it with PyPy, TLE disappeared and WA came out from what was not TLE. WA became AC after changing INF to 10 ** 3. (Submission # 9513468) However, the execution time was 1191msec, which was not TLE, but there was a big difference from 71msec in C ++.

In response to the above, I remeasured the speed with Python / PyPy with INF = 10 ** 3 on my machine.

Speed comparison result

** Speed ratio **

image.png

(Extended vertical axis) image.png

The figure above is

--Run on ubuntu KVM node on your home NUC (CentOS). --Change the question size from 1 to 20. --Repeat one size 5 times each in C ++ / Python / PyPy. --Measure the elapsed execution time with the time command. --Calculate the average of 5 runs. --Plot the vertical axis as (average execution time in Python or PyPy) / (average execution time in C ++) and the horizontal axis as the problem size (H, W (H = W)).

It is the result obtained by.

C ++: In Python, the Python code is INF = 100. (If you submit this code to AtCoder with PyPy3, you will get a WA) In C ++: Python (# 2) and C ++: PyPy, the Python code is INF = 1000.

--It can be seen that there is no big difference in execution time between when INF = 100 and when INF = 1000. --In Python and C ++, when the problem size is large, the ratio of execution speed is 60 times or more. --In PyPy and C ++, when the problem size is large, it can be seen that the ratio of execution speed is about twice. --According to the results submitted by AtCoder, the execution time of C ++ is 71msec and the execution time of PyPy3 is 1191msec, which is more than 10 times the speed difference, but it is strange that the difference is only about 2 times on my server. Perhaps it's related to the PyPy version of AtCoder being 2.4.0, while the home server is 7.3.0.

myoden@ubuntu002:~/AtCoder/ABC151/D$ pypy3 -V 
Python 3.6.9 (1608da62bfc7, Dec 23 2019, 10:50:04)
[PyPy 7.3.0 with GCC 7.3.1 20180303 (Red Hat 7.3.1-5)]
myoden@ubuntu002:~/AtCoder/ABC151/D$`

The problem case used will be described later.

** Elapsed execution time ** Elapsed execution time C ++ image.png

Elapsed execution time Python (INF = 100) image.png

Elapsed execution time PyPy (INF = 1000) image.png

The graph shows the maximum value (MAX), average value (AV), and minimum value (MIN) of the elapsed time when the test was performed 5 times.

Sample case (reference)

The sample case when the problem size was changed was created by changing H (= W) from 1 to 20 with H = W as follows.

sampleSquare-10.in


myoden@ubuntu002:~/AtCoder/ABC151/D$ cat sampleSquare-10.in 
10 10
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........

sampleSquare-20.in


myoden@ubuntu002:~/AtCoder/ABC151/D$ cat sampleSquare-20.in 
20 20
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
myoden@ubuntu002:~/AtCoder/ABC151/D$ 

Recommended Posts

AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
ABC166 in Python A ~ C problem
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
ABC163 C problem with python3
Python, Java, C ++ speed comparison
Atcoder ABC164 A-C in Python
Atcoder ABC167 A-D in Python
Solve ABC175 D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
ABC188 C problem with python3
ABC187 C problem with python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
Solve Atcoder ABC176 (A, B, C, E) in Python
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy and Python
Solve Atcoder ABC169 A-D in Python
Solve ABC036 A ~ C in Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC037 A ~ C in Python
AtCoder Beginner Contest 174 C Problem (Python)
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solve ABC175 A, B, C in Python
ABC 157 D --Solve Friend Suggestions in Python!
Algorithm in Python (ABC 146 C Binary Search
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
[AtCoder] Solve ABC1 ~ 100 A problem with Python
AtCoder ABC155 Problem D Pairs Review Note 1
Solve AtCoder ABC168 with python (A ~ D)
Solve ABC165 A, B, D in Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 37 in Python
Daily AtCoder # 8 in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 10 in Python
Next Python in C
Daily AtCoder # 28 in Python
Daily AtCoder # 20 in Python