Python2で競技プログラミングする時に知っておきたいtipsの，基礎知識についての部分を分割しました．
Pythonのバージョンは2.7.5（Python3では，入出力などの仕様が大きく異なるので，他の記事を参照することをおすすめします）．
競技プログラミングでは，多くの場合，プログラムの実行時間，メモリ使用量，スタック領域の使用量などが制限される．
コンテストのルールにもよるが，このあたりの制限は，PythonなどのLLには不利に働くことが多く，「C++ならACされたけど，PythonだとTLEだった」といったようなことが起こりやすい．
例えば，オンラインジャッジサービスのAtCoderでは，時間制限2sec，メモリ制限256MBの問題が多い．
今回はこれを基準とし，それぞれの限界値を調べることとする．
計算量
計算量は，競技プログラミングにおいて非常に重要な概念．
多くの場合，ループの回数を数えることで大まかな計算時間を見積もる．
競技プログラミング界隈で有名なプログラミングコンテストチャレンジブック(蟻本)によると，C++の場合，
実行制限時間が1秒の場合，
$10^7$ならおそらく間に合う．
$10^8$だと非常にシンプルな処理でない限り厳しい．
とのことらしい．
これをベースラインにして計測を行う．
計測
例えば，$10^6$回ループを回して出力させるようなコードを考える．
for i in xrange(1000000):
print i
この実行時間を，timeコマンドを使って計測する．
$ time python caltest.py
0
1
...
999999
python caltest.py 1.49s user 1.11s system 49% cpu 5.237 total
userがプログラムの実行時間になる．
もう結構ぎりぎりで，ループ中でちょっと重い処理させるとすぐ死にそう．
これを，$2*10^6$にすると，
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
単純にループだけみても，$2*10^6$回程度の出力でダメになることがわかる．
「Pythonは$10^6$ループでもきつい」と誰かから聞いたような気がするが，それが裏付けられた形だ．
ちなみに，C++で同じことをさせると，
#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
のようになる．
今回比較したのは出力のコードなのでそこまでの差は出なかったが，それでも2倍以上早い．
一般的には，C++とPythonだと，10〜100倍程度の実行時間の違いがあるらしい．
C++ vs. Python vs. Perl vs. PHP performance benchmark - /contrib/famzah
メモリ使用量
Pythonでは，リストに何らかの最適化がなされており，C++のように型によって配列のメモリ使用量を見積もるようなことが難しい．
今回は，いくつかの例について，memory_profilerを使ってメモリ使用量を計測することとする．
インストール
Python で実行時メモリを計測する場合 memory_profiler を利用すると便利 - 紹介マニアどらふと版
$ pip install -U memory_profiler
$ pip install psutil
計測
例えば，整数型変数のメモリ使用量を確認するには，
@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
のようにする．
計測したい関数の頭に@profileをつけることに注意．
"Increment" が，その行で使用したメモリ量．
この場合，l = 0は0.004Mib(≒4KB)のメモリを食うことがわかる．
リストでも試してみる．
@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
単純に整数型の1,000,000倍にはならないみたい．
だいたい，1要素につき8Byte程度？
また，2次元リストについても試してみると，
@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)]
のようになる．
1次元リストと要素数が同じなら，メモリ使用量はだいたい同じか，2次元リストの方が少し多くなるみたい．
少し要素数を増やしてみる．
@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
@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)]
要素数$10^7$〜$10^8$ぐらいで制限を超えてしまう．
もっとも，これぐらい大きなリストを作らないといけない場合，実装に問題がある可能性が高い．
再帰深度
Pythonの再帰の深さについてあれこれ - 数値計算とかの備忘録（仮）
再帰のコードを書いて大きいデータを入力した時，再帰深度がデフォルトの最大値を超える可能性がある．
例えば，以下のような，nの階乗を線形反復で求めるコードについて，
# -*- 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!が出力されるはず
これを実行すると，
...
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
のようなエラーが出る．
再帰深度の変更
>>> import sys
>>> sys.getrecursionlimit()
1000
上記のように，再帰深度はデフォルトで1000が限界らしい．
これだと，例えば，100*100程度の2次元配列をDFS(再帰版)するぐらいでもエラーになってしまう．
これを，例えば10000に変更したいなら，
import sys
sys.setrecursionlimit(10000)
とすればよい．
ここで言う「再帰深度」は必ずしも(プログラマの考える)再帰の回数と一致しないみたい．
例えば，上の例だと，再帰深度の限界値は1000なのに対し，999!(この場合，1000回fact_iter()が呼び出される)が計算できていない．
recursionlimitについては，少し多めに取っておく方が良さそう．