スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Paiza Online Hackathonに挑む

Paizaさんが、昨年末からこの1月8日まで、Paiza Online Hackathon 1 (略してPOH1)というイベントを行っていた。

要はそれぞれが自分の得意なプログラム言語でチャレンジできるプログラミングコンテストのようなものである。設定としては、野田さんなるかわいい新入女子社員が自分の担当するプログラムがうまくできなくて困っているので、それを助けてあげるというストーリーになっている。この野田さんの書きかけのコードが、見ると目がやられるようなものがわざと載せてあり、世のエンジニア諸氏がこれを見ると、ああ、なっちゃおらん、これなら俺の方が…とつい思って手を出すようになっているのかなかなかあざとい仕掛けではある。

問題自体は、仕様に沿って標準入力からデータを受け取り、答えを計算して標準出力に出力するプログラムを作成し、その実行時間を競う形式である。テストデータセットはデータの個数によりcase 1、2、3とあり、Paizaの仮想マシンにコードをアップロードすると自動的にこれらのテストデータに対して実行が行われる。正しい結果であることがもちろん必要である。その上で、より速いものが望ましいということになる。データの個数は、C、C++だけがコンパイル言語ということで他の言語より多くなっている。他の言語については、独自調査によるとcase 1、2、3のデータ数はそれぞれ700、13000、200000(仕様上の上限でもある)だった。

面白いので、私もC、C++、Pythonの3つでエントリした。
日頃Pythonでは速度を意識したプログラムはしたことがないため、かなり勉強になった。

期間内に到達できた結果は以下の通り。

C
C++
Python

時間の分解能が0.01秒なので、C、C++についてはこれ以上最適化しても数字の上では意味はない。苦労したのはPythonで、問題サイトでの他の人の途中経過を見ると、case 1、case 2、case 3でそれぞれ0.08、0.08、0.09(秒)となっている。
試しに何もしないプログラムを投稿してみても、それだけで0.07秒かかるので、ほとんどデータが増えても処理時間が増えていないことになる。私ははcase 3でどうしても0.5秒近くはかかっていた。これはいったいどうやっているんだろうと不思議に思い、いろいろと考え試みたのであるが、case 3のようにデータが多い場合に対処するための、この問題に関して言えば一番本質的なアルゴリズムに気がついたのはなんと締切り当日の夜8時頃である。それでなんとか0.15秒まで短縮できたのであるが、この段階で出遅れてしまい、それより先の無駄を削ぎ落とすステップにはもはや間に合わず、時間切れと相成った。というわけでPython case 2、3での最速タイは達成できなかったが、辛うじてアルゴリズムに関しては締切り間際に気がついたということで、一応自分に及第点は出しておく。

この私が取り組む余裕のなかったギリギリのチューニングに関しては、ゆめ技さんを始めいくつかのサイトですでに公開されているようであるから、今後、Paizaさんからのまとめ、講評も含めて勉強させてもらおうと思っている。

正解、模範解答といったものはPaizaさんのまとめを見ればよいことになると思うので、その劣化版に過ぎない私のコードをここで挙げるのはやめておこう。そのかわり、途中検討し、自分の環境では動作もしたが、Paizaさんの仮想マシン環境では動作させられず没になった方法をいくつか紹介しておく。

1. pyCUDA経由でCUDAを使う
これはお分かりと思うが、仮想マシンにCUDAの使えるGPUが備わっていないと話にならない。通常仮想マシン環境では意図的に選択しない限りGPUは使えないので、当然無理であると想像できる。実際、POH1の環境ではimport pycudaだけでランタイムエラーになる。

2. CPUでマルチスレッド化する
threadingモジュールをimportすることによって、JavaのThreadクラス等と似たような使い勝手でアプリケーションをマルチスレッド化できる。POH1のプログラムは、並列化できるポイントはいろいろあるが、たとえば問題文中の「キャンペーン期間中日ごとに変わるキャンペーン価格」に関しては、各日独立に計算できるのでまず第一の並列化候補となる。実際、マルチスレッド化したものを動かしてみると、自分のデスクトップマシンでは4コアCPUなのでスレッド数を4から8あたりにすると速くなったのであるが、POH1の仮想環境は、シングルコアi686である。マルチスレッド版にしても、動作はするが残念ながらほとんど効果はなかった。

3. PythonといいつつCで動かす
たいがいのスクリプト言語には、外部プログラムを呼び出す仕組みが備わっている。Pythonにもそのための機構がいくつかあり、Cython、Ctypes、Boost-pythonといったあたりを使うと、自分で作成したCのプログラムをモジュールとしてPythonから呼び出すことができる。なるほど、すばらしい。自分のマシンで、既に作成済みのCで提出したプログラムをライブラリ化してPythonから呼び出してみると、見事に動く。だが、残念ながらこれはPOH1の環境では動作させることができなかった。なぜかというと、まず、提出できるのは単体のソースファイルなので、ライブラリを別ファイルとして添付するわけにはいかない。したがって、この方法をとるためには、あらかじめコンパイル済みのバイナリを文字列にエンコードしてソース内に持ち、それをデコードして一時ファイルに書き出し、それをライブラリとしてロードする、というステップを踏む必要がある。ところが、POH1の実行環境は、調べてみると、プログラムが実行されるときのホームディレクトリはユーザーではなくrootの所有であり、ユーザはファイルを書き込むことができない。そうなると、ユーザがこのような一時ファイルを置くことができるのは、あとは/tmpディレクトリということになる。tempfileモジュールなどを利用してみるとたしかに一時ファイルを作成できるので、ここに、あらかじめi686環境用にコンパイルしたバイナリを書き出し、ロードする…ということを試みたのだが、するとなにやらランタイムエラーが。調べてみると、/tmpディレクトリがnoexecオプションでマウントされているため、そこにあるものを実行ファイルやライブラリとしてロードすることはできないよいうだ。なるほど、セキュリティ上はもっともな配慮である。残念ながら、これで自作のCプログラムを呼び出すという道は閉ざされた。

3b それでもCのライブラリを使う
「自作の」Cプログラムは/tmpにしか解凍できないのでnoexecオプションに引っかかって実行できないが、システムにあらかじめ備わっているライブラリならば、Ctypes経由で呼び出すことができる。

import ctypes
libc = ctypes.CDLL('libc.so.6')

としてやって、たとえばPythonのint()で

s = '123'
i = int(s)

とするかわりに、

s = '123'
i = libc.atoi(s)

などとすることができる。この方法は、POH1の環境でも実際に使うことができる。私はこれを使って、Pythonで時間のかかる、リストを100万個の0で初期化するなどの部分をmemsetやmemcpyを使って高速化できないか試してみたのであるが、結論から言うとあまり速くはならなかった。Cの標準関数はあまり高度な機能のものがそろっているわけではなく、汎用性はあるが低レベルなものが多い。したがって、これらを使おうとすると勢いプログラムのループの深い部分で使うことになり、呼び出し回数が多くなりがちである。そうなると、呼び出しのオーバーヘッドが大きくて、結局Cライブラリのメリットを生かせていないのではないかと思う。


以上のように、POH1の問題設定自体は比較的簡単なものなのだが、その中であれこれと試すことにより大いに楽しむことができたし、勉強にもなった。POH2以降もなるべく参加して楽しみたいと思っている。

追記 2014/01/14: その後も実はまだ仮想マシンが使えるとのことで、もう少しあがいてなんとか 0.11秒まで来たが、どうやらそろそろタイムリミットらしい。締切りがあるおかげで無限にこの問題を考え続けることが避けられるので助かるとも言える。
スポンサーサイト
プロフィール

GM3D

Author:GM3D
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
FC2カウンター
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。