Der Teil über Grundkenntnisse von Tipps, die Sie beim Programmieren von Wettbewerben mit Python2 kennen sollten wurde geteilt.
Die Python-Version ist ** 2.7.5 ** (In Python3 unterscheiden sich Spezifikationen wie Eingabe und Ausgabe erheblich, daher wird empfohlen, auf andere Artikel zu verweisen).
Bei der Konkurrenzprogrammierung sind die Programmausführungszeit, die Speichernutzung, die Stapelbereichsnutzung usw. häufig begrenzt.
Obwohl dies von den Regeln des Wettbewerbs abhängt, funktioniert diese Einschränkung häufig gegen LL wie Python, und es ist einfach für Dinge wie "AC wurde in C ++ ausgeführt, TLE in Python".
Beispielsweise hat der Online-Richterservice AtCoder viele Probleme mit einem Zeitlimit von 2 Sekunden und einem Speicherlimit von 256 MB. Dieses Mal werden wir dies als Referenz verwenden, um jeden Grenzwert zu untersuchen.
Computational Volume ist ein sehr wichtiges Konzept in der Wettbewerbsprogrammierung. In vielen Fällen wird die grobe Berechnungszeit durch Zählen der Anzahl der Schleifen geschätzt.
[Programmierwettbewerb Challenge Book](http://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%] berühmt im Bereich der wettbewerbsorientierten Programmierung 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 Nach% 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89 / dp / 4839931992) (Arimoto) im Fall von C ++,
Wenn das Ausführungszeitlimit 1 Sekunde beträgt $ 10 ^ 7 $ wird wahrscheinlich pünktlich sein. $ 10 ^ 8 $ ist streng, es sei denn, es ist ein sehr einfacher Prozess.
Es scheint, dass.
Dies wird als Basis für die Messung verwendet.
Stellen Sie sich zum Beispiel einen Code vor, der eine Schleife $ 10 ^ 6 $ mal dreht und ausgibt.
caltest.py
for i in xrange(1000000):
print i
Diese Ausführungszeit wird mit dem Befehl time gemessen.
$ time python caltest.py
0
1
...
999999
python caltest.py 1.49s user 1.11s system 49% cpu 5.237 total
Benutzer ist die Ausführungszeit des Programms.
Es ist fast vorbei, und wenn Sie ein wenig schwere Verarbeitung in der Schleife durchführen, werden Sie bald sterben.
Wenn dies auf $ 2 * 10 ^ 6 $ eingestellt ist,
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
Selbst wenn Sie sich nur die Schleife ansehen, können Sie sehen, dass die Ausgabe von ungefähr $ 2 * 10 ^ 6 $ mal nutzlos ist. Ich glaube, ich habe von jemandem gehört, dass "Python selbst in einer $ 10 ^ 6 $ -Schleife eng ist", aber das ist die Form, die es unterstützt.
Übrigens, wenn Sie dasselbe in C ++ tun,
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
so werden. Da der Ausgabecode diesmal verglichen wurde, gab es keinen großen Unterschied, aber er war immer noch mehr als doppelt so schnell.
Im Allgemeinen scheint es zwischen C ++ und Python einen 10- bis 100-fachen Unterschied in der Ausführungszeit zu geben. C++ vs. Python vs. Perl vs. PHP performance benchmark - /contrib/famzah
In Python werden einige Optimierungen für die Liste vorgenommen, und es ist schwierig, die Speichernutzung des Arrays nach Typ wie C ++ abzuschätzen.
Dieses Mal verwenden wir für einige Beispiele memory_profiler, um die Speichernutzung zu messen.
$ pip install -U memory_profiler
$ pip install psutil
Zum Beispiel, um die Speichernutzung von Ganzzahlvariablen zu überprüfen
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
Machen.
Beachten Sie, dass "@ profile" am Anfang der Funktion, die Sie messen möchten, hinzugefügt wird. "Inkrement" ist die in dieser Zeile verwendete Speichermenge. In diesem Fall ist ersichtlich, dass "l = 0" 0,004 Mib (~ 4 KB) Speicher verbraucht.
Versuchen Sie es auch auf der 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
Es scheint nicht einfach das 1.000.000-fache des Integer-Typs zu sein.
Über 8 Bytes pro Element?
Wenn Sie die zweidimensionale Liste ausprobieren,
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)]
so werden.
Wenn die Anzahl der Elemente mit der eindimensionalen Liste übereinstimmt, ist die Speichernutzung ungefähr gleich, oder die zweidimensionale Liste scheint etwas größer zu sein.
Versuchen Sie, die Anzahl der Elemente ein wenig zu erhöhen.
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)]
Das Limit wird überschritten, wenn die Anzahl der Elemente zwischen $ 10 ^ 7 $ und $ 10 ^ 8 $ liegt.
Wenn Sie jedoch eine so große Liste erstellen müssen, besteht eine hohe Wahrscheinlichkeit, dass ein Problem mit der Implementierung vorliegt.
Über die Tiefe der Wiederholung im Python-A-Memorandum für numerische Berechnungen (vorläufig)
Beim Schreiben von rekursivem Code und der Eingabe großer Datenmengen kann die rekursive Tiefe den Standardmaximalwert überschreiten.
Zum Beispiel für den folgenden Code, der die Potenz von n durch lineare Iteration ermittelt
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!Sollte ausgegeben werden
Wenn Sie dies tun,
...
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
Ich bekomme so einen Fehler.
>>> import sys
>>> sys.getrecursionlimit()
1000
Wie oben erwähnt, scheint die rekursive Tiefe standardmäßig auf 1000 begrenzt zu sein. In diesem Fall tritt beispielsweise ein Fehler auf, selbst wenn ein zweidimensionales Array von ungefähr 100 * 100 DFS (rekursive Version) ist.
Wenn Sie dies beispielsweise auf 10000 ändern möchten
import sys
sys.setrecursionlimit(10000)
Und es ist ausreichend.
Es scheint, dass die "rekursive Tiefe" hier nicht unbedingt mit der Anzahl der rekursiven übereinstimmt (denken Sie an den Programmierer).
Im obigen Beispiel beträgt der Grenzwert der rekursiven Tiefe beispielsweise 1000, aber 999! (In diesem Fall wird fact_iter () 1000-mal aufgerufen) kann nicht berechnet werden.
In Bezug auf das Rekursionslimit scheint es besser, etwas mehr zu sparen.
Recommended Posts