Y箱

前に書いたreduceのポストのトラフィックが意外に高くて気をよくしたのでもうちょっと書いてみる。


reduceの使いかたは

その1 (reduce f coll)
その2 (reduce f val coll)

fは2つの引数を採って1番目の引数と同じ形の値を返す関数。どちらの場合でも、collの要素を一つずつ2番目の引数にしながら、collが無くなるまで、fを呼び出していくけれど、一番最初に違いがある。

その1の書式では、最初の引数は、collの1番目と2番目の要素になる。ということは、reduceの結果は要素と同じ形のものしか作れないことになる。

しかし、その2では、最初の引数はvalと1番目の引数になる。これはreduceの結果がvalと同じ形になることを意味しているので、好きな結果を得ることができるのだ。


さて、こんなデータがあるとする。

(def sample-data [:a :b 11 22 :c :d 33 :e :f])

まずは、この中の数字の数を数える関数を作ってみる。

(reduce f val coll)
collはsample-dataですね。
欲しいデータは数字の個数で、その初期値だからvalに入れるのは0にします。
fは2つの引数(count tgt)を受け取って、tgtが数字ならcountを1増やした値を返す関数ということになります。
こんな感じ

(reduce <数字だったら1増やす> 0 sample-data)

作るとこうなります。

(defn count-num [lst]

  (reduce (fn [count tgt]              ;; 2つの引数を採って

	    (if (number? tgt)          ;; 数字だったら

	      (inc count)              ;; 1増やしたもの

	      count))                  ;; そうでなかったら、そのまま

	  0 lst))



(count-num sample-data)

3

この例は、filter と countを使えば簡単にできてしまうけれど、数字だけじゃなくて、それ以外のものの個数も数えたかったらちょっと面倒じゃないかな。 でも、reduceを使うと簡単。

(reduce f val coll)

valに入れるのは、やっぱり欲しいデータの初期値。こんどは2つの値が必要です。それをまとめるのであれば、ベクタを使うのがいいですね。数字もそれ以外のものも0個なので、0が2つだから[0 0] とします。

関数はこう。

(reduce <数字だったら左を+1、そうでなかったら右を+1> [0 0] sample-data)

作ると、

(defn count-num-other [lst]

  (reduce (fn [count tgt]

	    (if (number? tgt)

	      [(inc (first count)) (last count)]     ;; 数字だったら左を+1

	      [(first count) (inc (last count))]))   ;; そうでなかったら右を+1

	  [0 0] lst))



(count-num-other sample-data)

[3 6]

ここまでは、使ったデータを全部捨てていましたが、当然、使うこともできます。こんどは分類してみます。
結果として、数字とそれ意外のものそれぞれリストが欲しい。、初期値はからなので、valは [[] []].

関数はこう。

(reduce <数字だったら左に入れる、そうでなかったら右に入れる> [[] []] sample-data)

(defn num-or-other [lst]

  (reduce (fn [[nlist olist] tgt]

	    (if (number? tgt)

	      [(conj nlist tgt) olist]        ;;数字だったら左に追加

	      [nlist (conj olist tgt)]))      ;;それでなかったら右に追加

	  [[] []] lst))



 (num-or-other sample-data)

[[11 22 33] [:a :b :c :d :e :f]]

さて、最後は、ちょっと毛色を替えて、数字を出現順の番号に入れかえてみる。google groupのclojure-jaにあった問題。

[:a :b 11 22 :c :d 33 :e :f] を [:a :b 1 2 :c :d 3 :e :f]) のようにしたい。
数字は、11 22 33 の順に出てくるので、11 を 1、22 を 2、33 を 3に置き替えるということ。

カウンターとしてmutableな変数を使ってしまう手もあるけれど、それはだめ。つまらない。でも、カウンターが無いと、番号を振れない。そこで、最初にやった個数を数える問題を改めて見てみると、立派にカウントしているではないですか。リストを順に処理して、33が来たときにちゃんと3を生成していて、これが最終的な答えになっている。今回、このカウンターは最終結果には不要だけれども、途中では必要。最後に捨ててしまうことにする。

(reduce f val coll)
valは、カウンターと結果の初期値 [] を入れるので、 [1 []] になる。 1じゃなくて0でもOKだけれども、処理がちょっと変わる。
関数はこう。

(reduce

   <数字だったらカウンタを+1して、リストにカウンタを入れる、

    そうでなかったら、データをリストに入れる>

   [1 []] sample-data)

(defn seq-num [lst]

  (second                                           ;; 結果のリストだけ抜きだす。

   (reduce (fn [[counter lst] tgt]

	     (if (number? tgt)

	       [(inc counter) (conj lst counter)]   ;; 数字だったら、カウンタを+1して、

	                                            ;; カウンタをリストに入れる

	       [counter (conj lst tgt)]))           ;; そうでなかったら、カウンタはそのまま

	                                            ;; データをリストに入れる

	   [1 []] data)))





(seq-num data)

[:a :b 1 2 :c :d 3 :e :f]

このときの second に入る前のデータは、

[3 [:a :b 1 2 :c :d 3 :e :f]]

のようになっています。

自宅のパソコンが壊れちゃったので、新しいノートPCを買った。
最近はいいやつが安く買えるので、思いきってCore i7のを買ってしまった。
で、前に仕事パソコンでやった並列処理の速度を測ってみた。

新PC
  Core i7 2630
  クロック 2.00GHz
  コア数 4
  MEM: 4GB

旧PC
  Core?2 Duo SL9300
  クロック 1.60GHz
  コア数 2
  MEM: 2GB

さらにi7はハイパースレッディングで仮想コアがあるのでOSからは8つのコアに見える。

処理は 2の10000乗を10000個計算して、下2桁の合計を求めるもの。
コードはこれ。

(let [nums 10000]

  (time 

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

結果は
旧 5562 msecs
新 4251 msecs

クロックを比較すると、2.0GHzは1.6GHzの1.25倍なので所用時間が反比例するとしたら、 5562 / 1.25 = 4449 になる。 実際はもうちょっと速いけど、まあ、コア単体ではそれほど性能が上っているわけではないことがわかる。


次に、pmapを使って10000個をそれぞれ並列に処理してみる。

コード

(let [nums 10000]

  (time 

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

結果
旧 3480 msecs
新 1150 msecs

半分以下の時間になった。単一スレッドとの時間で比較しても、旧では36%減だけど、新では、73%減。

タスクマネージャの表示をキャプチャしたのが下の画像。



また、前にも書いたとおり、上の並列処理は10000個を全部別のスレッドに割りあてていて、オーバーヘッドが大きくなってしまっている。適当なサイズに分割することで、もう少し速度が向上するはず。
以下のようにいくつかずつに分割して割り当てて実行してみた。

2分割の場合の処理がこれ。

(let [nums 10000]

  (time 

   (reduce + (pmap #(reduce + (map (fn [x] (rem (expt 2 x) 100)) %))

                   (partition 5000 (repeat 10000 nums))))))

全部の結果をまとめてみた。
単位はmsec。

            旧     新

1分割      5562   4251

2分割      3092   2157

10分割     3064   1132

100分割    3099   1106

1000分割   3255   1129

10000分割  3480   1150

2コアに比べて、分割数を大くしても性能の低下が少ない感じです。
スレッド(タスク)の切りかえが高速なのかもしれませんね。