読者です 読者をやめる 読者になる 読者になる

自分のマシン上でpython走らせたときのパフォーマンス

kinabaさんのアルゴリズムコンテストの挑み方を真面目に読み直していると、こんな一文が。

自分の持っている計算機が、どのくらいのスピードで「計算」できるか、ご存じでしょうか?

感覚的には億のオーダー、つまり 10^8 超えたらGCJ Largeでは黄色信号かなあ(制限時間8分のため)、というぐらいには理解しているのですが、確かに正確な性能はわかりません。

というわけで測ってみることにしました。

測定環境

マシン
HW Thinkpad X61
CPU Intel Core2 Duo T7500 2.20GHz
Disk SSD 80GB
Memory 2GB
ソフトウェア
OS Fedora 12
kernel 2.6.32-12-115.fc12.i686.PAE
python 2.6.2
使用言語

python

測定結果

大体表の通り。
時間はほぼ全てリニアに伸びてます。
ループ回数が10倍になったら単純に10倍すればいいです。

測定内容 ループ回数 時間[sec]
1〜Nまでの和 10^7 4.55
1/N〜N/Nまでの和(全てfloat) 10^7 12.24
乱数生成 10^7 22.92
ランダムな配列のソート 10^6 1.29
配列へのappend 10^7 4.33
[0]*nによる配列の生成 10^8 0.85

他に測定したい項目があれば随時追加。

考察

はっきりとわかったのは、「一問題で 10^8 は黄信号ではなくアウト」ということです。
テストケースで 10^1〜10^2 とられる以上、一つの問題を解くには 10^6〜10^7 以上の計算量をかけちゃいけないということです。
つまり、n=10^3 だったらO(n^2) が計算量の限界ですし、n=10^2 だったら O(n^3) が限界です。
せっかく解いた Large でタイムアウトとか目も当てられないので、このあたりの計算量だけは常に頭に叩き込んでおきたいところです。
あと、メモリ空間の限界も忘れちゃいけません。
配列の生成は 10^8 で限界で、 10^9 ではダメでした(搭載メモリ量からすれば当たり前)。
何でもかんでもメモリ上に確保しないよう気をつけなければなりません。