2010-04-25[n年前へ]
■Ruby で書いた計算プログラムの実行速度
「入門レベルの問題ですが」と前置きをされた上で、プログラミングの「問題」を出された。「5分間でコーディングして下さい。あと、プログラムの実行時間が2秒を超えるなら誤答です」と言う、厳しいオマケの言葉付きで、そんなお題を出された。
とりあえず、頭を雑巾のように振りしぼり、単純そうな解法のRubyコードを書いてみた。…しかし、2秒で計算を終えることはどうしてもできそうにない。少なくとも、その100倍以上の計算時間がかかる。
「これは見当違いの解法アルゴリズムだったか…」と思いながら、出題者におそるおそる提出してみると、「アルゴリズムは合っている」という。とりあえず、「解法を思いつかない」という最悪の自体は避けられたが、それにしても、もう少し高速化して提出したかった。
Rubyで書いたのは、こんなコードだ。このRubyコードを高速化しようと思うなら、どのようにすれば計算時間を短くすることができるだろうか。また、同じ解法を他言語で実装した場合、Rubyコードとどのくらい計算速度が違ってくるものなのだろうか。
def makeRect(n) data=[] n.times{ data<<[rand(),rand(),rand(),rand()] } return data end def makeMesh(rects) xg=[] yg=[] rects.each do |xt,xb,yt,yb| xg<<xt<<xb yg<<yt<<xb end xg.sort! yg.sort! mesh=[] (xg.length-1).times do |x| (yg.length-1).times do |y| cx=(xg[x]+xg[x+1])/2 cy=(yg[y]+yg[y+1])/2 area=(xg[x+1]-xg[x])*(yg[y+1]-yg[y]) mesh<<[cx,cy,area] if area>0 end end return mesh end rects=makeRect(1000) mesh=makeMesh(rects) area=0 mesh.each do |x,y,a| rects.each do |xt,xb,yt,yb| if xt<x&&x<xb&&yt<y&&y<yb area+=a break end end end puts area
「お題」を書け、と言われそうですが、どこぞのプログラミング・コンテストで出題されるかもしれないということもあり、「お題」自体は書かないでおきます。また、「お題」がわかりづらいように、コメントを削除してあります(といっても関数名・変数名から、ある程度は想像できそうにも思いますが)。というわけで、回答コードをもとに、「お題」の内容を逆に想像してみると、そしてより良い解法を考えてみたりするのも、面白いかもしれません。ちなみに、上記コードで、makeRect(1000) としている部分は、問題が訂正され、数百程度になりそう、ですね。