La partie concernant les connaissances de base des astuces à connaître lors de la programmation de la compétition avec Python2 a été divisée.
La version Python est ** 2.7.5 ** (En Python3, les spécifications telles que l'entrée et la sortie sont très différentes, il est donc recommandé de se référer à d'autres articles)
Dans la programmation concurrentielle, le temps d'exécution du programme, l'utilisation de la mémoire, l'utilisation de la zone de pile, etc. sont souvent limités.
Bien que cela dépende des règles du concours, cette limitation fonctionne souvent contre LL comme Python, et c'est facile pour des choses comme "AC a été fait en C ++, mais TLE en Python".
Par exemple, le service de juge en ligne AtCoder a de nombreux problèmes avec une limite de temps de 2 secondes et une limite de mémoire de 256 Mo. Cette fois, nous l'utiliserons comme référence pour étudier chaque valeur limite.
Le volume de calcul est un concept très important dans la programmation compétitive. Dans de nombreux cas, le temps de calcul approximatif est estimé en comptant le nombre de boucles.
[Livre du défi du concours de programmation](http://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%] célèbre dans le domaine de la programmation concurrentielle E3% 83% 9F% E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% A7 Selon% 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89 / dp / 4839931992) (Arimoto), dans le cas de C ++,
Si le délai d'exécution est de 1 seconde 10 $ ^ 7 $ seront probablement à temps. $ 10 ^ 8 $ est strict à moins qu'il ne s'agisse d'un processus très simple.
Il paraît que.
Ceci est utilisé comme référence pour la mesure.
Par exemple, considérons un code qui tourne une boucle $ 10 ^ 6 $ fois et la produit.
caltest.py
for i in xrange(1000000):
print i
Ce temps d'exécution est mesuré à l'aide de la commande time.
$ time python caltest.py
0
1
...
999999
python caltest.py 1.49s user 1.11s system 49% cpu 5.237 total
user est le temps d'exécution du programme.
C'est presque terminé, et si vous faites un peu de traitement lourd dans la boucle, vous mourrez bientôt.
Si cela est défini sur $ 2 * 10 ^ 6 $,
caltest2.py
for i in xrange(2000000):
print i
$ time python caltest2.py
0
1
...
1999999
python caltest2.py 3.00s user 2.26s system 50% cpu 10.475 total
Même si vous regardez simplement la boucle, vous pouvez voir que la sortie d'environ $ 2 * 10 ^ 6 $ fois est inutile. Je pense avoir entendu quelqu'un dire que "Python est serré même dans une boucle $ 10 ^ 6 $", mais c'est la forme qui le prend en charge.
Au fait, si vous faites la même chose en C ++,
caltest.cpp
#include <cstdio>
using namespace std;
int main() {
for(int i = 0; i < 2000000; i++) printf("%d\n", i);
return 0;
}
$ g++ caltest.cpp
$ time ./a.out
0
1
...
1999999
./a.out 1.27s user 2.10s system 34% cpu 9.714 total
devenir de cette façon. Puisque le code de sortie a été comparé cette fois, il n'y avait pas beaucoup de différence, mais c'était quand même plus de deux fois plus rapide.
En général, il semble qu'il y ait une différence de temps d'exécution d'environ 10 à 100 fois entre C ++ et Python. C++ vs. Python vs. Perl vs. PHP performance benchmark - /contrib/famzah
En Python, une certaine optimisation est effectuée pour la liste, et il est difficile d'estimer l'utilisation de la mémoire du tableau par type comme C ++.
Cette fois, pour quelques exemples, nous utiliserons memory_profiler pour mesurer l'utilisation de la mémoire.
$ pip install -U memory_profiler
$ pip install psutil
Par exemple, pour vérifier l'utilisation de la mémoire des variables entières
memtest.py
@profile
def main():
l = 0
if __name__ == '__main__':
main()
$ python -m memory_profiler memtest.py
Filename: memtest.py
Line # Mem usage Increment Line Contents
================================================
1 8.555 MiB 0.000 MiB @profile
2 def main():
3 8.559 MiB 0.004 MiB l = 0
Faire.
Notez que «@ profile» est ajouté au début de la fonction que vous souhaitez mesurer. «Incrément» est la quantité de mémoire utilisée sur cette ligne. Dans ce cas, on peut voir que «l = 0» consomme 0,004 Mib (≈4 Ko) de mémoire.
Essayez-le également sur la liste.
memtest2.py
@profile
def main():
l = [0] * 1000000
if __name__ == '__main__':
main()
$ python -m memory_profiler memtest2.py
Filename: memtest2.py
Line # Mem usage Increment Line Contents
================================================
1 8.781 MiB 0.000 MiB @profile
2 def main():
3 16.418 MiB 7.637 MiB l = [0] * 1000000
Il ne semble pas être simplement 1 000 000 fois le type entier.
Environ 8 octets par élément?
De plus, si vous essayez la liste bidimensionnelle,
memtest3.py
@profile
def main():
l = [[0] * 1000 for _ in xrange(1000)]
if __name__ == '__main__':
main()
$ python -m memory_profiler memtest3.py
Filename: memtest3.py
Line # Mem usage Increment Line Contents
================================================
1 8.742 MiB 0.000 MiB @profile
2 def main():
3 16.676 MiB 7.934 MiB l = [[0] * 1000 for _ in xrange(1000)]
devenir de cette façon.
Si le nombre d'éléments est le même que la liste unidimensionnelle, l'utilisation de la mémoire est à peu près la même ou la liste bidimensionnelle semble être un peu plus.
Essayez d'augmenter un peu le nombre d'éléments.
memtest4.py
@profile
def main():
l = [0] * 100000000
if __name__ == '__main__':
main()
$ python -m memory_profiler memtest4.py
Filename: memtest4.py
Line # Mem usage Increment Line Contents
================================================
1 8.398 MiB 0.000 MiB @profile
2 def main():
3 771.344 MiB 762.945 MiB l = [0] * 100000000
memtest5.py
@profile
def main():
l = [[0] * 10000 for _ in xrange(10000)]
if __name__ == '__main__':
main()
$ python -m memory_profiler memtest5.py
Filename: memtest5.py
Line # Mem usage Increment Line Contents
================================================
1 8.383 MiB 0.000 MiB @profile
2 def main():
3 779.613 MiB 771.230 MiB l = [[0] * 10000 for _ in xrange(10000)]
La limite est dépassée lorsque le nombre d'éléments est d'environ 10 $ ^ 7 $ à 10 $ ^ 8 $.
Cependant, si vous devez faire une liste aussi longue, il y a de fortes chances qu'il y ait un problème avec l'implémentation.
À propos de la profondeur de récurrence dans Python-Notes sur les calculs numériques (provisoire)
Lors de l'écriture de code récursif et de la saisie de données volumineuses, la profondeur récursive peut dépasser la valeur maximale par défaut.
Par exemple, pour le code suivant qui trouve la puissance de n par itération linéaire
rectest.py
# -*- coding: utf-8 -*-
def fact_iter(n, res):
if n == 0:
return res
else:
return fact_iter(n - 1, n * res)
if __name__ == '__main__':
print fact_iter(999, 1) # 999!Devrait être sortie
Quand tu fais ça,
...
File "rectest.py", line 8, in fact_iter
return fact_iter(n - 1, n * res)
File "rectest.py", line 8, in fact_iter
return fact_iter(n - 1, n * res)
File "rectest.py", line 8, in fact_iter
return fact_iter(n - 1, n * res)
RuntimeError: maximum recursion depth exceeded
J'obtiens une erreur comme celle-ci.
>>> import sys
>>> sys.getrecursionlimit()
1000
Comme mentionné ci-dessus, la profondeur récursive semble être limitée à 1000 par défaut. Dans ce cas, par exemple, même si un tableau bidimensionnel d'environ 100 * 100 est DFS (version récursive), une erreur se produit.
Si vous voulez changer cela, par exemple, 10000
import sys
sys.setrecursionlimit(10000)
Et c'est suffisant.
Il semble que la "profondeur récursive" ici ne corresponde pas nécessairement au nombre de récursifs (pensez au programmeur).
Par exemple, dans l'exemple ci-dessus, la valeur limite de la profondeur récursive est 1000, mais 999! (Dans ce cas, fact_iter () est appelé 1000 fois) ne peut pas être calculé.
En ce qui concerne la limite de récursivité, il semble préférable d'économiser un peu plus.