2015/03/24

Clojureのdefun, パターンマッチ付きの関数定義

 defunというと, Common LispやEmacs Lispの関数定義を連想しますが, Clojureでもdefunを使って関数定義ができるようです. さっき, 偶然発見したのですが.

 このdefun, Clojureの普通の関数定義であるdefnとの違いは, パターンマッチ付きの関数定義ができることです. GitHub中の説明には,
A macro to define clojure functions with parameter pattern matching just like erlang or elixir.
 とあります.

 Clojureのパターンマッチングといえば, core.matchかdefmulti/defmethodのマルチディスパッチですが, 関数の引数に対して, そのままパターンを記述できるので, defn+matchの組み合わせよりもシンプルになります.

 .lein/profile.clj (or project.clj)の:pluginsに[defun "0.2.0-RC"]を追加してとりあえず, quicksortもどきを書いてみると,
 core.match版
(use '[clojure.core.match :refer [match]])

(defn quicksort1 [ls]
  (match ls
   ([] :seq) []
   ([x & xs] :seq)
   (concat (quicksort1 (filter #(< % x) xs))
           [x] (quicksort1 (filter #(>= % x) xs)))))
 と, defun版
(use '[defun :only [defun]])

(defun quicksort2
  ([([] :seq)] [])
  ([([x & xs] :seq)]
   (concat (quicksort2 (filter #(< % x) xs))
           [x] (quicksort2 (filter #(>= % x) xs)))))
 余分なシンボルが減り, 括弧だけになってすっきりした印象になりました. matchの一旦変数を定義して, それをそのままmatchマクロに渡すという処理がなくなり1行分減り, 変数名が一つ減っています. しかし, 括弧は, 条件一つにつき, 2ペア増えてしまいました. どうやら, この括弧は(大括弧, 小括弧ともに)外せないようです.
(defun sum
  ([0 m] m)
  ([n m] (recur (dec n) (+ n m))))
こんな感じで, recurが内臓させることも可能なようで, loop-recurの省略にも使えます.

 パターンやガードの記述は, core.matchと同じ(というかcore.matchそのもの)なので, core.matchを使う要領で定義できます.

2015/03/05

doallで遅くなる(Clojure)

 mapなどリスト処理の間に, doallを間に挟むと, その分遅くなっているような気がしたので, 調べてみると, 確かにdoallを挟むことで実行時間が伸びています.

 副作用を考えない場合, 意味的にはidentityと同じなので, 忘れがちですが, しっかり計算コストとメモリ確保のためのコストがかかっているようです.

 以下がその証拠. (Linux Mint 17 Cinnamon 64-bit, Intel Core i7-4790, メモリ : 31.4GB)
user> (defn dub [n] (* n 2))
#'user/dub
user> (time (reduce + (map inc (map dub (range 10000000)))))
"Elapsed time: 1661.92639 msecs"
100000000000000
user> (time (reduce + (map (comp inc dub) (range 10000000))))
"Elapsed time: 1388.861015 msecs"
100000000000000
user> (time (reduce + (map inc (doall (map dub (range 10000000))))))
"Elapsed time: 1892.659523 msecs"
100000000000000
user> (time (reduce + (map inc (map dub (range 1000000000)))))
user> (time (reduce + (map inc (map dub (range 100000000)))))
"Elapsed time: 15394.220163 msecs"
10000000000000000
user> (time (reduce + (map (comp inc dub) (range 100000000))))
"Elapsed time: 13912.628054 msecs"
10000000000000000
user> (time (reduce + (map inc (doall (map dub (range 100000000))))))
"Elapsed time: 54838.803745 msecs"
10000000000000000
 一回目のトライは, 普通にmapを2回リストに適用した場合で1.6秒程度.

 次にmap分配則を用いて2回分のmapを1回に縮めてみた場合. 若干, 早くなりました. Haskellだとこの最適化は, 効果的なのですが, Clojureではおそらくリストの実装上の違いによりあまり効果がないようです.

 三行目が, 問題のdoallを挟んだリスト処理です. 通常のリスト操作と比べて0.2秒ほど, 遅くなっています. 遅くはなっていますが, 1.1倍程度です.

 下三行の入力は, リストのサイズを大きくした(1ケタ上げた)場合. map分配則による変換の効果の割合はリストサイズが10分の1以下の時と変わらないようです.

 一方で, doallを挟んだ場合は, 3倍以上の時間がかかっています. 与えられたリストのサイズに対して実行時間が線形に増加していないのは, メモリ確保に時間がかかっていることが原因だと思われます.

 ちなみに, 上記のreplのプロセスが終了すると約5.5GiBのメモリ領域が開放されました. というわけで, メモリサイズがシビアなノートPCとかだと, (GCなどに)よりその影響が顕著に出てくるかもしれません.