Y箱

Project Euler を解いているときに、素数生成とかの細かい関数を作っているのだけれど、10個以上になってきたので、まとめることにした。
あらためて見てみると、変だったり、もう少し汎用的にしたほうがよかったりするものが目について、直し始めちゃって泥沼化寸前。

そのなかで、同じような計算をたくさんしているところで気になっていたのが、CPUの使用率が50%を超えないこと。mapなんかは自動的に並列処理してくれるのだと思っていたからちょっと意外だった。黒猫本(と呼ばれているかどうかは知らない)にも、STMとかの機能の説明はあるけど、並列化するための方法については書かれていなかった。「自分でJavaのThreadを呼ばなければならんのかい!」と思っていたら、pmapというのを見つけた。

で、実際どうなのかを調べてみた。


なんか適当に時間のかかる処理ということで、適当に2のX乗をY個足す処理にした。

mapでやるとこんな感じ。

(let [nums 10000]
  (time 
   (reduce + (map (fn [x] (rem (expt 2 x) 100)) (repeat 10000 nums)))))

"Elapsed time: 5561.606014 msecs"

5.6秒くらい。 このときのCPUの使用率は50%。


mapをpmapに変えると、

(let [nums 10000]
  (time 
   (reduce + (pmap (fn [x] (rem (expt 2 x) 100)) (repeat 10000 nums)))))

"Elapsed time: 3480.631756 msecs"

お、速い。 3.5秒。 36%高速化。

タスクマネージャで見ると、ちゃんと100%使用率になる。
あと、そこでjavaを片方のCPUにだけ割りあてると、もとと同じく、5秒半ぐらいかかる。


さて、これで安心してはいけない。
ここの記事を見たりすると、ただ単に1つ1つ並列化すればいいというものではないらしい。
そりゃあ当然だ。細切れにすれば、その分Over headが増えるわけだからねぇ。
どんな風に分けたらいいのかなぁ。

僕のPCはデュアルコアだから、2つに分けてみると、

(let [nums 10000]
  (time 
   (reduce + (pmap #(reduce + (map (fn [x] (rem (expt 2 x) 100)) %))
                   (partition 5000 (repeat 10000 nums))))))

"Elapsed time: 3092.340227 msecs"

3.1秒。 44%高速化。 8ポイント向上。


ほかも適当にやってみると、
10分割 "Elapsed time: 3064.371031 msecs"
100分割 "Elapsed time: 3099.338324 msecs"
1000分割 "Elapsed time: 3255.111753 msecs"

今回は10分割が一番速いという結果。


並列化のための関数は、他にもfutureとかいろいろあるみたいなので、これからちょっとずつつついていこうと思っとります。