新人女子の書いたコードを直すだけのお仕事におけるTips(Python編)

はじめに

こんにちは。ちきん(@mokemokechicken)です。
今回はネタです。

paizaさんがやっている POH! というイベントがあります。

paizaオンラインハッカソン(略してPOH!) Vol.1

Facebookなどで割りと拡散しているようなのでご存知の方も多いのではないかと思います。
最初は社内で、最後は個人的に盛り上がっていたのでそんな様子でもお伝えしようと思います。

事の始まり

私個人としては、最初は

私:「こんな安い釣りに乗ってたまるか(あ、野田さんかわいい)」

的な感じで見送っていたのですが、社内の誰かが社内コミュニティで

K氏:「弊社のエンジニアが萌えそうなネタが。(^^ ニヤニヤ

的な感じで煽ってきます。
そこに

T氏:「PHPでやったよ。S取ったよ」

的な投稿が。しょうがないので詳しく見てみると、各言語毎の競争みたいになっているじゃないですか。
さらによくよく見てみると、Pythonが一番遅いことになっているじゃないですか
私にとっては
Pythonは本妻、Rubyは楽しい浮気相手、CoffeeScriptは友達、Scalaは憧れの人」という感じなのでこれを見過ごすわけにはいきません。
コンパイル型の言語にはそもそも勝てる気はしませんし、LL内でいえばぶっちゃけPerlには勝てる気がしません。だがしかし、、「Rubyには負けたくない!ましてやPHPには…」というのがPython派の本音(?)ではないでしょうか。「なんとかRubyを超えたい」という決意を胸にして私のチャレンジが始まりました。

ちなみにRuby大好きです。PHPにはいつもお世話になっております。

これまでの経過

初回
あえなくCase3がTimeout。野田さんに「うちは中規模サイトなのでこのコードで乗り切れそうですね!」 と慰められる。いや、待って、、まだ実力の10%も出せてないんだよ。。

途中。 バグのあるコードをCommitしてしまい、「ある意味凄いコードですね。」とご褒美を頂く。ごめん、、次はちゃんとテストするから。。

というわけで、チューニングや 動作確認をするための
簡単な検証環境
を作りました。

そして更に社内・社外の実力派のエンジニアが参戦してきたり、一部の人間の間で盛大に盛り上がっておりました。

0.17秒 までは独力で行けたのですが、そこで一旦足踏み状態。
perlで頑張って新人女子を助けた。】 方のコードを参考に一気に0.14秒 へ。

最後ちまちまチューニングして、記念すべき30回目の投稿にして、遂に0.1秒の大台を切ることができました。

Python 0.10 / 0.09 / 0.09

Pythonの起動に0.08秒程度かかる状況なので(回避策あるのかなぁ)、だいぶやり切った感があります。

このコードは「Case3のような分布に速度は特化しているが、一応どんな問題でも正解を出力する(つもり)」という性質のもので完全にレース仕様であります。公開しても良いのですが、まだ企画も前半ですし細かい内容は伏せておきます。

そこで、Pythonで速度をチューニングする際の私なりのTipsを紹介します(やっと本題 ^^;)。

チューニングTips

アルゴリズム

まずは、アルゴリズム的な部分で作戦を考える必要があります。その言語の得意なデータ構造や速い処理を利用できるようにするのがLL系の取るべき戦法かなと思います。

アルゴリズムを定めたら、細かいチューニングで行けるところまで進んでみます。

Profiler

Profilerというのは、どの部分がどのくらいの時間を消費しているかを調べるツールです。
Pythonには簡単に使えるProfilerがあります。

% python -m cProfile <<PYTHON_PROGRAM>>

のようにして、関数ごとの呼び出し回数や所要時間がわかります。
基本はまずProfileして時間がかかっている部分から対応を考えると良いと思います。

Profiler2

1つの関数の中でもどこが時間がかかっているのか知りたい場合があります。
その場合、

    price_list = [int(x) for x in sys.stdin]

とかなっている部分を

    def z():
return [int(x) for x in sys.stdin]
price_list = z()

と書きなおして、Profileすると、そのz()の部分の所要時間がわかります。

不要なことはしない

アルゴリズムにも関係ありますが、多少コードが長くなったとしても、
やらなくていいことはやらないのも大事なことです。

スニペットレベルの処理時間の計測

Pythonには timeit というライブラリがあります。例えば インタラクティブモードで、

>>> import timeit
>>> timeit.timeit("int('88888')")
0.70660400390625

というように使います。
出力されているのはかかった時間です(defaultでは1000000回実行したときの時間)。
こんな風に int() の速度を簡単に知ることができます。

基本的に実行回数が多いところが一番対処すべき部分です。

例えば、文字列を整数に直すことは今回の問題では必要なことなので、
0.3秒台を切ってきた頃に「うおー int() おせー」 と最初は私も絶望していました。

しかしまあ、書き方次第でだいぶ変わるようで、

>>> timeit.timeit("int('88888', 10)")
0.34395909309387207
>>> timeit.timeit("int_('88888', 10)", setup="int_=int")
0.31864213943481445

と半分以下になったりします。こういうことを繰り返してネックな部分を改善していきます。

高速なライブラリの利用

例えば、Pythonには itertools というIteratorを高速に処理できるライブラリがあります。
大抵ループはネックな部分なので上手く使えると速くなります。

例えばこんな感じです。

>>> timeit.timeit("x = tuple(int_(x) for x in '123456789')", setup="import itertools as it; int_=int")
7.845993995666504
>>> timeit.timeit("x = tuple(it.imap(int_, '123456789'))", setup="import itertools as it; int_=int")
7.122924089431763

やっぱり、楽しむこと

愛というか執念というか「諦めたらそこで試合終了ですよ」というか。

結局チューニングには時間はかかるので、歩いている時とかお皿を洗っている時とか寝る前とかにぼーっと考えているうちにアイディアが浮かんできて、上記のように測定しながら試して見るのが良いのだと思います。パズルみたいに。

さいごに

100分の1秒の勝負になってしまっているので、起動に時間がかかっているPythonは少し分が悪いですね。
おそらく最後はPerlやRubyにTotalの実行時間は勝てないんだろうなぁ、と思います。

そしてもうおわかりのように
ゆめみではこのように苦手な部分については手厚いサポートが、ある、、、のかな? 少なくとも野田さんのように世渡り上手に聞いてくれれば皆優しく教えてくれます。というか、みんな教えたがりです。ほんと。

最後に、paizaさん、楽しい企画をありがとうございました。野田さんの引きが最高でした。



Fatal error: Allowed memory size of 268435456 bytes exhausted (tried to allocate 16271409 bytes) in /home/yumeco/www/prod/wp-includes/wp-db.php on line 1171