AtCoder ABC151 Problem D Geschwindigkeitsvergleich in C ++ / Python / PyPy

Überblick

Teilnahme an AtCoder ABC151. Lösen Sie Problem D in C ++ / Python3 / PyPy3 mit einer Methode, die für dieses Problem wahrscheinlich nicht optimal ist (Warshall-Floyd-Methode). Ich habe gemessen und verglichen.

Das Ergebnis war, dass C ++ stabiler und 60-70-mal schneller war, wenn die Problemgröße in gewissem Maße zunahm. Wenn Sie Bedenken bezüglich TLE haben, ist es besser, die Übermittlung von ~~ Implement ~~ in Python zu beenden.

Als ich später einen Kommentar erhielt und ihn mit PyPy3 (2.4.0) einreichte, stellte ich fest, dass TLE behoben wurde. Die Ausführungszeit betrug jedoch 1191 ms, was erheblich langsamer war als die von C ++ mit 71 ms.

Wenn Sie sich also Sorgen um TLE machen, ist es besser, 1. die Implementierung in C ++ einzureichen, 2. in Python PyPy zu implementieren.

Hintergrund

Teilnahme am AtCode ABC151. Als ich Problem D sah, dachte ich wie folgt.

"Es kann durch die Methode im Ameisenbuch (Warshall-Floyd-Methode) gelöst werden. Die Knoten (Masse) sind jedoch nur mit oben, unten, links und rechts verbunden, und der Abstand zwischen benachbarten Knoten beträgt immer 1, sodass es eine effizientere Methode gibt. damit.

Aber O (N ^ 3) und N = 400, also 400 ^ 3 = 64.000.000, nicht wahr? Es ist mühsam, an andere Methoden zu denken, und ich weiß, dass dies das Problem lösen wird. Verwenden wir also die Worshall-Floyd-Methode. ""

In Python implementiert, ohne zu viel nachzudenken. Ich habe bis zum Zeitlimit (vor 3 Minuten) debuggt und eingereicht # 9476488 (20-01-12 22:37:01), aber das Ergebnis Ist TLE. Ich war traurig.

Später, als ich es in C ++ implementierte und eingereicht # 9484896, betrug die Ausführungszeit 71 ms, was eine Marge war. Ich möchte in Zukunft darauf verweisen.

1/15 Nachschrift

In dem Kommentar: "Ich habe TLE nicht bekommen, als ich es mit PyPy 3 veröffentlicht habe. Ich habe 3 WAs." Als ich es mit PyPy implementierte, verschwand TLE und WA kam aus dem heraus, was nicht TLE war. WA wurde AC, nachdem INF auf 10 ** 3 geändert wurde. (Submission # 9513468) Die Ausführungszeit betrug jedoch 1191 ms, was nicht TLE war, aber es gab einen großen Unterschied zu 71 ms von C ++.

Als Reaktion darauf habe ich die Geschwindigkeit mit Python / PyPy mit INF = 10 ** 3 auf meinem Computer neu gemessen.

Ergebnis des Geschwindigkeitsvergleichs

** Geschwindigkeitsverhältnis **

(Erweiterte vertikale Achse)

Die obige Abbildung ist

• Führen Sie einen Ubuntu-KVM-Knoten auf Ihrem Heim-NUC (CentOS) aus.
• Ändern Sie die Problemgröße von 1 auf 20.
• Wiederholen Sie eine Größe jeweils fünfmal mit C ++ / Python / PyPy. --Messen Sie die verstrichene Ausführungszeit mit dem Befehl time. --Berechnen Sie den Durchschnitt von 5 Läufen.
• Zeichnen Sie die vertikale Achse als (durchschnittliche Ausführungszeit in Python oder PyPy) / (durchschnittliche Ausführungszeit in C ++) und die horizontale Achse als Problemgröße (H, W (H = W)).

Es ist das Ergebnis von.

C ++: In Python lautet der Python-Code INF = 100. (Wenn Sie diesen Code mit PyPy3 an AtCoder senden, erhalten Sie WA) In C ++: Python (# 2) und C ++: PyPy lautet der Python-Code INF = 1000.

• Es ist ersichtlich, dass es keinen großen Unterschied in der Ausführungszeit zwischen INF = 100 und INF = 1000 gibt.
• In Python und C ++ beträgt das Verhältnis der Ausführungsgeschwindigkeit bei großen Problemen das 60-fache oder mehr.
• In PyPy und C ++ ist bei großen Problemen zu erkennen, dass das Verhältnis der Ausführungsgeschwindigkeit etwa doppelt so hoch ist.
• Nach den von AtCoder übermittelten Ergebnissen beträgt die Ausführungszeit von C ++ 71 ms und die Ausführungszeit von PyPy3 1191 ms, was mehr als dem Zehnfachen des Geschwindigkeitsunterschieds entspricht. Es ist jedoch seltsam, dass der Unterschied auf meinem Server nur etwa zweimal beträgt. Möglicherweise hängt es damit zusammen, dass die PyPy-Version von AtCoder 2.4.0 ist, während der Heimserver 7.3.0 ist.

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$`

Der verwendete Problemfall wird später beschrieben.

** Verstrichene Ausführungszeit ** Verstrichene Ausführungszeit C ++

Verstrichene Ausführungszeit Python (INF = 100)

Verstrichene Ausführungszeit PyPy (INF = 1000)

Die Grafik zeigt den Maximalwert (MAX), den Durchschnittswert (AV) und den Minimalwert (MIN) der verstrichenen Zeit, als sie fünfmal durchgeführt wurde.

Beispielfall (Referenz)

Der Beispielfall, in dem die Problemgröße geändert wurde, wurde durch Ändern von H (= W) von 1 auf 20 mit H = W wie folgt erstellt.

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$