AtCoder ABC151 Problème D Comparaison de la vitesse en C ++ / Python / PyPy

Aperçu

Participation à AtCoder ABC151. Résolvez le problème D en C ++ / Python3 / PyPy3 avec une méthode qui n'est probablement pas optimale pour ce problème ([Méthode Warshall-Floyd](https://ja.wikipedia.org/wiki/Warshall-Floyd Method)) J'ai mesuré et comparé.

Le résultat était que C ++ était plus stable et 60 à 70 fois plus rapide lorsque la taille du problème augmentait dans une certaine mesure. Si vous avez des inquiétudes concernant TLE, il semble préférable d'arrêter de soumettre ~~ Implement ~~ en Python.

Plus tard, quand j'ai reçu un commentaire et l'ai soumis avec PyPy3 (2.4.0), j'ai trouvé que TLE était résolu. Cependant, le temps d'exécution était de 1191 ms, ce qui était considérablement plus lent que celui des 71 ms de C ++.

Donc, si vous êtes inquiet pour TLE, il semble préférable de 1. Soumettre l'implémentation en C ++ 2. Implémenter en Python PyPy.

Contexte

Participé à AtCode ABC151. Quand j'ai vu le problème D, j'ai pensé comme suit.

"Il peut être résolu par la méthode (méthode Warshall-Floyd) sur le livre des fourmis. Mais les nœuds (masse) sont connectés uniquement en haut, en bas, à gauche et à droite, et la distance entre les nœuds adjacents est toujours de 1, il existe donc une méthode plus efficace. alors.

Mais O (N ^ 3) et N = 400, donc 400 ^ 3 = 64 000 000, n'est-ce pas? Il est difficile de penser à d'autres méthodes, et je sais que cela résoudra le problème, alors utilisons la méthode Worshall-Floyd. "

Implémenté en Python sans trop réfléchir. J'ai débogué jusqu'à la limite de temps (il y a 3 minutes) et soumis # 9476488 (20-01-12 22:37:01), mais le résultat Est-ce que TLE. J'étais triste.

Plus tard, quand je l'ai implémenté en C ++ et soumis # 9484896, le temps d'exécution était de 71 ms, ce qui était une marge. Je veux y faire référence à l'avenir.

1/15 post-scriptum

Dans le commentaire, "Je n'ai pas eu TLE quand je l'ai sorti avec PyPy 3. J'ai eu 3 WA." Certes, quand je l'ai implémenté avec PyPy, TLE a disparu et WA est sorti de ce qui n'était pas TLE. WA est devenu AC après avoir changé INF en 10 ** 3. (Soumission # 9513468) Cependant, le temps d'exécution était de 1191 ms, ce qui n'était pas TLE, mais il y avait une grande différence par rapport à 71 ms de C ++.

En réponse à ce qui précède, j'ai remesuré la vitesse avec Python / PyPy avec INF = 10 ** 3 sur ma machine.

Résultat de la comparaison de vitesse

** Rapport de vitesse **

(Axe vertical étendu)

La figure ci-dessus est

• Exécutez sur un nœud KVM ubuntu sur votre NUC domestique (CentOS).
• Modifiez la taille du problème de 1 à 20.
• Répétez une taille 5 fois chacun avec C ++ / Python / PyPy. --Mesurez le temps d'exécution écoulé avec la commande time.
• Calculez la moyenne de 5 courses.
• Tracez l'axe vertical comme (temps d'exécution moyen en Python ou PyPy) / (temps d'exécution moyen en C ++) et l'axe horizontal comme taille du problème (H, W (H = W)).

C'est le résultat obtenu par.

C ++: En Python, le code Python est INF = 100. (Si vous soumettez ce code à AtCoder avec PyPy3, vous obtiendrez WA) En C ++: Python (# 2) et C ++: PyPy, le code Python est INF = 1000.

• On peut voir qu'il n'y a pas de grande différence de temps d'exécution entre quand INF = 100 et quand INF = 1000.
• En Python et C ++, lorsque la taille du problème est grande, le rapport de vitesse d'exécution est de 60 fois ou plus.
• Dans PyPy et C ++, lorsque la taille du problème est grande, on peut voir que le rapport de vitesse d'exécution est environ deux fois. --Selon les résultats soumis par AtCoder, le temps d'exécution de C ++ est de 71 ms et le temps d'exécution de PyPy3 est de 1191 ms, ce qui est plus de 10 fois la différence de vitesse, mais il est étrange que la différence ne soit qu'environ deux fois sur mon serveur. Cela est peut-être lié au fait que la version PyPy d'AtCoder est 2.4.0, tandis que le serveur domestique est 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$`

Le cas problématique utilisé sera décrit plus loin.

** Temps d'exécution écoulé ** Temps d'exécution écoulé C ++

Temps d'exécution écoulé Python (INF = 100)

Temps d'exécution écoulé PyPy (INF = 1000)

Le graphique montre la valeur maximale (MAX), la valeur moyenne (AV) et la valeur minimale (MIN) du temps écoulé lorsqu'il a été effectué 5 fois.

Exemple de cas (référence)

Le cas d'échantillon où la taille du problème a été modifiée a été créé en changeant H (= W) de 1 à 20 avec H = W comme suit.

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$