GaucheでRubyのArray#product同等の関数
結論
Gaucheではcartesian-product
を使うと良い。
以下は、この関数を見落としていたことによる悪戦苦闘の記録。
背景
業務中にちょっとしたスクリプトで「複数の配列の直積」が必要になった。
例:
- 入力:
[[1, 2], [3, 4], [5]]
- 出力:
[[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]
2配列ぐらいなら2重ループでもいいのだけど、6配列ぐらい必要だったのでループはきつかった。
RubyのArray#product
業務中は作業速度優先で、さっさとRubyで対応した。Rubyならそのものproduct
というのがある。
irb(main):001:0> [1, 2].product([3, 4], [5]) => [[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]
Gaucheにproductがあるのか調べる
業務後にGaucheでどう書くか調べてみた。
冒頭に書いた通り標準ライブラリに存在するのだけど、この時点では見落としていた。
まず(apropos 'product)
で引っかからないので早とちりしたが、ドキュメントにちゃんと書いてあった。
Macro: apropos pattern :optional module 名前がpatternにマッチするような定義された変数のリストを表示します。 moduleにモジュールオブジェクトまたはモジュール名を与えた場合は、 そのモジュール内で定義されている変数のみが表示されます。moduleが 省略された場合は、カレントモジュールから「見える」変数が全て表示されます。
カレントモジュールから「見える」変数が全て表示されます。
cartesian-product
はutil.combinations
にあるので、useしないと見えなかった。
(どこにあるか分からない段階でuse出来るわけはないので、これは仕方ないが)
gosh> (use util.combinations) gosh> (apropos 'product) cartesian-product (util.combinations) cartesian-product-for-each (util.combinations) cartesian-product-right (util.combinations) cartesian-product-right-for-each (util.combinations)
とはいえDashでproduct
で引っ掛ければcartesian-product
が引っかかるので、これは単純に見落とした。
そんなわけでproduct関数がないと思い込み、練習ついでにGaucheで書いてみようと思った。
Rubyで仮実装
最初からGaucheで書けるほど慣れていないので、まずはRubyで書いてみた。
自己再帰で書いたりしたのだけど最終的にはinjectを使うようにした。
# 2要素の直積 def product_2dim(xs, ys) xs.inject([]) do |acc, x| acc + ys.map do |y| [x, y].flatten end end end # injectで畳み込み def product(*lists) lists.inject([[]]) {|acc, ls| product_2dim(acc, ls) } end
Gaucheで実装
(define (product . lis) (define (append-last a b) (if (null? a) (list b) (append a (cons b '())))) (define (product-2dim xs ys) (fold (^(y acc) (append acc (map (cut append-last y <>) xs))) '() ys)) (fold product-2dim '(()) lis))
期待通りには動いているように見える。でも…
ベンチマーク取ってみた
(let ((a (iota 100 1)) (b (iota 100 1)) (c (iota 100 1))) (time (product a b c))) ; (time (product a b c)) ; real 203.288 ; user 279.670 ; sys 16.460
遅い。非効率な実装なのは感じていたけど、ここまで遅いとは。
ちなみにもちろんcartesian-product
使えばちゃんと早い。
(use util.combinations) (let ((a (iota 100 1)) (b (iota 100 1)) (c (iota 100 1))) (time (cartesian-product (list a b c)))) ;(time (cartesian-product (list a b c))) ; real 0.347 ; user 0.330 ; sys 0.020
おわりに
自分で書いたproduct
実装は遅いのを抜きにしても可読性が悪い。これ絶対数日後に読んでも何がしたいか解読に時間がかかるパターン。
色々書いて読んで覚えていくしかない。
cartesian-product
自体Gaucheで書かれているので、とても参考になる。
(define (cartesian-product lol) (if (null? lol) (list '()) (let ((l (car lol)) (rest (cartesian-product (cdr lol)))) (append-map! (lambda (x) (map (lambda (sub-prod) (cons x sub-prod)) rest)) l))))