DRY
皆さんご存知 DRY (Don't Repeat Yourself) 原則.
システムの維持や拡張を容易にするには, 沢山の「似たようなもの」が必要になったとき, それらの, 何が同じで何が違うかを分離し, 「違う」ところはその都度, 「同じ」ところは 1度だけ, 記述するようにすることが重要です.
この分離が, 仕様記述では容易であるにも関わらず, コードにすると難しいことが, ままあります.
でも Clojure なら大丈夫.
以下では, ある算数の問題を題材にしますが, 賢明な読者様におかれましては, この題材の背景にある抽象的な問題を, ご自身の具体的な問題に当て嵌めて検討いただけるものと思います.
動作の確認には Clojure 1.8.0 を用いました.
ある算数の問題
「3 つの異なる非負整数の集合で, 要素の総和が 5 になるものを列挙せよ.」
答えは
#{0 1 4}
#{0 2 3}
の二つ. それぞれの集合の要素は順不同です. (#{} は Clojure における集合のリテラル表現です.)
列挙の順序も問わないので, 全体を集合として回答すると,
#{#{0 1 4} #{0 2 3}}
となります.
3つの整数について順序の重複を除外するため
5 > a > b > c >= 0
の範囲で a, b, c を探索し, 和が 5 になるものを抜き出すとします.
これを計算する Clojure コードは, 以下のようになります.
(set
(for [a (range 5)
b (range a)
c (range b)
:when (= (+ a b c) 5)]
#{a b c}))
; => #{#{0 1 4} #{0 3 2}}
(c は (- 5 a b) として (< -1 c b) を条件とすると速くなりますが, 後の話を簡潔にするため, このままでご容赦願います.)
仕様拡張
元の仕様では「総和が 5」でしたが, 5 ではなく, 任意の自然数を指定できるよう, 仕様が拡張されました.
曰く「自然数 n が与えられた時, 異なる 3 つの非負整数の集合で, 要素の総和が n になるものを列挙せよ.」
これは簡単.
先のコードで 5 を n に置き換え n を引数にとる関数を作成すれば良いです.
(defn forn3 [n]
(set
(for [a (range n)
b (range a)
c (range b)
:when (= (+ a b c) n)]
#{a b c})))
動作を確認してみます.
(forn3 2) ; => #{}
(forn3 3) ; => #{#{0 1 2}}
(forn3 4) ; => #{#{0 1 3}}
(forn3 5) ; => #{#{0 1 4} #{0 3 2}}
(forn3 6) ; => #{#{0 1 5} #{1 3 2} #{0 4 2}}
(forn3 7) ; => #{#{0 4 3} #{0 2 5} #{0 1 6} #{1 4 2}}
良いようです.
前置きが長くなりました. ここから本題です.
もう一つ可変要素の追加
前の仕様では「3 つの非負整数」であったが, 3 ではなく, 任意の自然数を指定できるよう, 仕様が拡張されました.
曰く「自然数 n と m が与えられた時, 異なる m 個の非負整数の集合で, 要素の総和が n になるものを列挙せよ.」
(話を簡潔にするため m の範囲については言及しません.)
先の仕様拡張と今回の仕様拡張は問題文だけを読むと同程度の容易さに思えます.
では, コード中の 3 と書いてあるところを m で置き換えましょう.
ありません.
どういうことでしょうか. どうしたら良いでしょうか.
先を読む前に, 少し考えてみてください.
可変要素の分離が難しい理由
最初の「3 つの異なる非負整数の集合で, 要素の総和が 5 になるものを列挙」を計算するコードで 5 は数値として登場しましたが, 3 は「コードに並べられている構文要素の数」として登場しました.
これが仕様文言レベルでは同程度の難しさなのに, コードレベルでは可変要素の分離が容易だったり難しかったりする理由の一つです.
再帰
この問題で, 同じ構造を一度だけ記述するための一つの解法は, そもそも探索する要素数分の構文要素を並べて記述するのではなく, 可変深さの探索が可能なように, 再帰で記述し直すという方法です.
(defn ci-rec [n m]
(set
(filter #(= (apply + %) n)
((fn f [n m]
(if (zero? m) '(#{})
(mapcat
(fn [a] (map #(conj % a) (f a (dec m))))
(range n))))
n m))))
関数 f は, 与えられた n と m について, n > a >= 0 の範囲で ai を選び, ai を新しい n, m - 1 を新しい m として 自身を呼び出すことで a{i+1} ~ a{m-1} を 再帰的に計算します.
この f に元の n と m を与える ((fn f [n m] ...) n m) ことで, n > a0 > a1 > ... > a{m-1} >= 0 であるような {ai | 0 <= i < n} を列挙します.
(filter ...) は, 和の条件に合うものだけ抜き出し, (set ...) は, 回答の最後に全体を集合に変換します.
難しいですね.
一応, 動作確認をしてみましょう.
(ci-rec 3 3) ; => #{#{0 1 2}}
(ci-rec 4 3) ; => #{#{0 1 3}}
(ci-rec 5 3) ; => #{#{0 1 4} #{0 3 2}}
(ci-rec 6 3) ; => #{#{0 1 5} #{1 3 2} #{0 4 2}}
(ci-rec 5 4) ; => #{}
(ci-rec 6 4) ; => #{#{0 1 3 2}}
(ci-rec 7 4) ; => #{#{0 1 4 2}}
(ci-rec 8 4) ; => #{#{0 1 2 5} #{0 1 4 3}}
良さそうです.
マクロ
もう一つの解法は, マクロを使って「元の構造をそのまま抽象化」してしまうことです.
最初のコードでは, 三つの非負整数は a, b, c でしたが, 数学でよくやるように, 添え字をつけて a0, a1, a2 としてみましょう.
(set
(for [a0 (range n)
a1 (range a0)
a2 (range a1)
:when (= (+ a0 a1 a2) n)]
#{a0 a1 a2}))
こうすると, 数学でよく使う ... を用いてよければ, 非負整数の個数 m を変数として導入できることが分かります.
つまり,
(set
(for [a0 (range n)
a1 (range a0)
a2 (range a1)
...
a{m-1} (range a{m-2})
:when (= (+ a0 a1 a2 ... a{m-1}) n)]
#{a0 a1 a2 ... a{m-1}}))
のような具合です.
これで構造を抽象化できました.
これはコードで書けますか. 書けます. そう, マクロを使えば.
(defmacro ci-mac [n m]
(let [s (map #(symbol (str "a" %)) (range m))]
`(set
(for [~@(mapcat (fn [[i r]] [i `(range ~(if r r n))])
(reverse (partition-all 2 1 (reverse s))))
:when (= (+ ~@s) ~n)]
#{~@s}))))
再帰の場合に負けず劣らず難しいですね.
ただし, 再帰で書く場合に比べて, マクロ版はいくつか利点があり, その一つが, マクロを展開してみて, 想定した動作をするコードになっているか容易に確認できることです. macroexpand-1 で, n = 5, m = 3 を与えた場合に生成されるコードを確認します.
(macroexpand-1 '(ci-mac 5 3))
; => (clojure.core/set (clojure.core/for [a0 (clojure.core/range 5) a1 (clojure.core/range a0) a2 (clojure.core/range a1) :when (clojure.core/= (clojure.core/+ a0 a1 a2) 5)] #{a1 a0 a2}))
このままでは分かりにくいので, 名前空間を省略し, インデントを揃えます.
すると, 以下のようなコードになっていることが, わかります.
(set
(for [a0 (range 5)
a1 (range a0)
a2 (range a1)
:when (= (+ a0 a1 a2) 5)]
#{a1 a0 a2}))
想定通りですね.
興味を持たれた方は, なぜ上記のマクロで, このような展開結果が得られるのか, 検証してみてください. (ご要望あれば別途解説を投稿します.)
動作確認も省略しますので, 確認してみてください.
ベンチマーク
再帰版に対して, マクロ版のもう一つの利点は速度です.
ベンチマークを採ってみましょう.
criterium を使わせていただきました.
leiningen をお使いの場合, project.clj の :dependencies への追加行は
[criterium "0.4.4"]
です.
(require '[criterium.core :refer :all])
しておきます.
以下, 詳細は省き, 平均実行時間のみ掲載します.
n = 5, m = 3
(do
(bench (forn3 5)) ; => 16.610795 µs
(bench (ci-mac 5 3)) ; => 16.881435 µs
(bench (ci-rec 5 3)) ; => 61.688918 µs
)
マクロ版は, ハードコード版に肉迫.
再帰版は, ハードコード版やマクロ版の三倍以上の実行時間です.
実際に適用する具体的な問題において, この速度が絶対的な意味で問題にならないなら, 問題を本質的に記述できる再帰による実装を検討しても良いでしょう.
以下のように n や m が大きくなると速度の違いは深刻です.
n = 100, m = 3
(do
(bench (forn3 100)) ; => 40.187805 ms
(bench (ci-mac 100 3)) ; => 40.428353 ms
(bench (ci-rec 100 3)) ; => 611.090454 ms
)
再帰版は, マクロ版の 15 倍の実行時間.
n = 20, m = 5
ハードコード版は, m が可変ではないので, m = 5 のハードコード版を作ります.
(defn forn5 [n]
(set
(for [m0 (range n)
m1 (range m0)
m2 (range m1)
m3 (range m2)
m4 (range m3)
:when (= (+ m0 m1 m2 m3 m4) n)]
#{m0 m1 m2 m3 m4})))
ベンチマーク結果は
(do
(bench (forn5 20)) ; => 8.423173 ms
(bench (ci-mac 20 5)) ; => 8.612622 ms
(bench (ci-rec 20 5)) ; => 98.796860 ms
)
再帰版は, マクロ版の 11 倍の実行時間がかかりました.
マクロのもう一つの利点
今回の題材は本質的に再帰的な構造だったので, 再帰による記述ができましたが, いつでもそうできるとは限りません. マクロでは, 本質的に再帰構造でない場合でも, 似通った構造を抽象化できる可能性があります.
結論
「似たようなもの」があるとき, 「同じ」ところと「違う」ところを分離し, 同じところは1度だけ記述するようにしたい.
これは, 違うところが値として見えていれば変数として取り出すことは容易ですが, 違いが構造に埋め込まれている場合, 変数として取り出すことが難しくなります.
しかし, 再帰やマクロを使えば, 同じ構造を取り出し違うところを変数化できる, つまり構造を抽象化できる可能性があります.
それぞれ以下のような利点があります.
再帰による構造の抽象化は
- 本質的に再帰構造ならば本質的な構造をそのまま記述できる
マクロによる構造の抽象化は
- 元の構造をそのまま抽象化できる
- マクロを展開してみることで具体化した構造を確認できる
- 速度を担保できる
- 本質的に再帰構造でなくても構造を抽象化できる
掲載した再帰によるコードは十分練っておらず, 条件を組み込んでおくことで, もう少し速く動作させられると思います.
しかし, 私の腕では, ベンチマーク結果を覆すところまでは速くできませんでした.
どなたか, ベンチマーク結果を覆すか, マクロの速度に肉迫するところまで速くできた方はご教示いただければ幸いです.
さして分かり易くもない文章になってしまいましたが, 本投稿が, どなたかの何らかの気づきに少しでも寄与できれば幸いです.
それでは, 良いクリスマスを.