Project euler 14

pe_14.clj

;; 去年最初に解いたときのやつ。
;; 「hotpo」というのは half or tripple plus one のアクロニムで、昔読んでいた(日経)サイエンス誌の連載で
;; これが紹介されたときの名前で、英語版Wikipediaには載っていました。

;; 今動かしてみたら、なぜかスタックオーバーフローになってしまう。
;; 1.2だと動くのかなぁ。と思ってやってみたら動く！！ 
;; なんでだろう。 スタックの深さが1.2の方が大きいのかなぁ。

;; 実行すると、 50秒くらいかかります。
;; "Elapsed time: 48273.476472 msecs"

;; 考えかた
;; 1から100万までの数それぞれについて、hotopoの数列の数を数えて、最大のものを選びます。 普通のやりかたです。
;; hotpoの数列を数えるときは、数列そのものは不要なので、値は捨てています。


;; hotpoの数列の流れを追って行きながら数を数えています。
;; この問題は数列の途中に合流がある(wikipedia参照)ので、メモ化で効率を上げることができると考えて、メモ化のため生の再帰で書いてるようです。
;; ★★ ところがclojureのメモ化は、再帰の中の関数には効果が無いので実はまったく機能していません。
(defn hotpo-count
  ([n] (hotpo-count n 0))
  ([n count]
     (cond (= n 1) (inc count)
     (even? n) (hotpo-count (/ n 2) (inc count))
     :else (hotpo-count (+ (* n 3) 1) (inc count)))))

;;メモ化しています。
(def hotpo-count (memoize hotpo-count))

;; 本体
(loop [n 1 max-list [0 0]]
  (if (> n 1000000)
    max-list
    (let [hotpo (hotpo-count n)]
      (if (< (nth max-list 1) hotpo)
        (recur (inc n) [n hotpo])
        (recur (inc n) max-list)))))

pe_14_2.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  hotpo-count をいじってみる
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; その1
;; 1.4で動くようにしてみます。
;; 単に loop と recurに変えただけ。これで動くようになりました。
;; これでも、だいたい50秒くらいかかった。

(defn hotpo-count [target]
  (loop [n target count 0]
    (cond (= n 1) (inc count)
          (even? n) (recur (/ n 2) (inc count))
          :else     (recur (+ (* n 3) 1) (inc count)))))

;;----------------------------------------------------------------------

;;その2
;; ちゃんとメモ化して動かしてみる。
;; 以前ブログで書いた(http://ypsilonbox.blogspot.jp/2011/09/clojure-memoize-11-12.html)んですが、
;; 1.2からmemoizeの効果が再帰の中に及ばなくなっています。なので、再帰の中でも効くよなマクロを自前で作りました。

;; メモ化した関数を作るマクロです。
;; 関数の中にメモを保持するようになっています。
(defmacro defn-memo 
  "Creates memoised function."
  [name arg-list & body]
  `(let [mem# (atom {})]
     (defn ~name ~arg-list
       (if-let [e# (find @mem# ~arg-list)]
         (val e#)
         (let [ret# ~@body]
           (swap! mem# assoc ~arg-list ret#)
           ret#)))))

;; そのマクロdefn-memoで定義します。 メモ化するので、普通に再帰させます。
;; (condは最近こういう風に書いてます。)
(defn-memo hotpo-count [n]
  (cond (= n 1)
        ,,1
        (even? n)
        ,,(inc (hotpo-count (/ n 2)))
        :t
        ,,(inc (hotpo-count (+ (* n 3) 1)))))

pe_14_3.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  答えの出しかたをいじってみる
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 最初のは再帰で解いてますが、reduceでやってみました。
;; もうちょっとすっきりできそうなんだけど...

;; 探索範囲は奇数だけにしてちょっと高速化。
;; 偶数は、1/2していって、奇数になるまで落ちるから。

(reduce (fn [[max-count max-val] tgt-val]
          (let [tgt-count (hotpo-count tgt-val)]
            (if (< tgt-count max-count)
              [max-count max-val]
              [tgt-count tgt-val])))
        [0 0]
        (range 1 1000000 2))

pe_14_4.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 現状の回答  12/13
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;"Elapsed time: 29273.12012 msecs"
(defmacro defn-memo 
  "Creates memoised function."
  [name arg-list & body]
  `(let [mem# (atom {})]
     (defn ~name ~arg-list
       (if-let [e# (find @mem# ~arg-list)]
         (val e#)
         (let [ret# ~@body]
           (swap! mem# assoc ~arg-list ret#)
           ret#)))))

(defn-memo hotpo-count [n]
  (cond (= n 1)
        ,,1
        (even? n)
        ,,(inc (hotpo-count (/ n 2)))
        :t
        ,,(inc (hotpo-count (+ (* n 3) 1)))))


(reduce (fn [[max-count max-val] tgt-val]
          (let [tgt-count (hotpo-count tgt-val)]
            (if (< tgt-count max-count)
              [max-count max-val]
              [tgt-count tgt-val])))
        [0 0]
        (range 1 1000000 2))

pe_14_5.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 現状の回答  12/20
;;  指摘いただいた内容でちょっとすっきり
;;  また、奇数だけにしていたのを、偶数込みに戻しました。そのせいで時間が掛っています。
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;"Elapsed time: 38715.909959 msecs"

(defmacro defn-memo 
  "Creates memoised function."
  [name arg-list & body]
  `(let [mem# (atom {})]
     (defn ~name ~arg-list
       (if-let [e# (find @mem# ~arg-list)]
         (val e#)
         (let [ret# ~@body]
           (swap! mem# assoc ~arg-list ret#)
           ret#)))))

(defn-memo hotpo-count [n]
  (cond (= n 1)
        ,,1
        (even? n)
        ,,(inc (hotpo-count (/ n 2)))
        :t
        ,,(inc (hotpo-count (+ (* n 3) 1)))))

;; メモ化で再計算のコストが無視できるので、カウントを持ち回らないようにしています。
(reduce (fn [max-val tgt-val]
          (if (> (hotpo-count tgt-val)
                 (hotpo-count max-val))
            tgt-val
            max-val))
        (range 1 1000000))

Problem 14 Collatz Sequence の問題
「与えられた正の整数 n を, 偶数なら n/2 , 奇数ならば 3n + 1 にするという変形を 1 になるまで繰り返した数列をコラッツ数列という. (必ず 1 に到達すると考えられているが証明はされていない). 1000000 未満の数で一番長いコラッツ数列を生成するのはどの数か？ (数列の途中で 1000000 以上になることはあり得る)」という奴ですね.

hotpo なんていう呼び方もあるんですね. 知らなかったです.

pe_14.clj
同じ名前を二度定義しており, 最初の関数の再帰呼び出しが先に定義した方の名前に飛ぶから memoize が効かないのではないでしょうか? (外してたらすみません.)

(def hotpo-count
  (memoize
    (fn [n]
      (cond (<= n 1)  n
            (even? n) (inc (hotpo-count (quot n 2)))
            :else     (inc (hotpo-count (inc (* 3 n))))))))

では如何でしょうか.
(pe_14_4.clj でそうされているように, カウントは引数で渡さず, 再帰回数分 inc が呼ばれることで長さが分かる書き方にしてあります.)

pe_14_2 ~ 4.clj

• メモ化関数生成マクロ素敵です. 👍
  memoize より使いやすそう....
• cond のインデント面白いですね.
  Common Lisp のアンクォートと勘違いして一瞬目が？になりました.
  Clojure ではカンマはスペースと同じ扱いでした.
• reduce 版でも同じようにカウントを渡さないようにできないでしょうか...

2, 6, 18, 54 などは, その数以下の数に対するコラッツ数列の長さの中で最大の長さを持ちます.
探索範囲を奇数に絞るのは適切でないかもしれません.

では如何でしょうか.

さっそくやってみました。 https://gist.github.com/4342882
だめですね。

実は、最初にこれに気づいたときに、いろいろ検索して調べておぼろげながら理解しています。ご想像に近く、問題は、clojureの関数の解決の動作に関連しています。
1.1から1.2へ移るときに、ネームスペースの扱いが変っていますが、そのときに、関数の呼び出し(管理？)がシンボル(var?)ベースからオブジェクトベースに変ったようで、再帰などで関数を探すときに、シンボルを経由しなくなっています。

varを経由させるために、以下のようなコードを書くと、期待通りの結果が得られます。
再帰呼び出しのところで、varをわたすために「#'」を関数名の前に付けています。

(defn fibo [n]
    (do
     (println "-->" n)
     (if (<= n 1)
        n
        (+ (#'fibo (dec n)) (#'fibo (- n 2))))))

(def fibo (memoize fibo))

user> (fibo 4)
--> 4
--> 3
--> 2
--> 1
--> 0
3
user> (fibo 5)
--> 5
5

この書きかたのほうが、defnの書式のすべてを使えるので、高機能なのですが、メモ化を効果的にするためには、ソースを変えないといけないのは自分のマクロを使うのと変らないので、意地になって自分のマクロを使ってます。(笑

2, 6, 18, 54 などは, その数以下の数に対するコラッツ数列の長さの中で最大の長さを持ちます.
探索範囲を奇数に絞るのは適切でないかもしれません.

するどい指摘ありがとうございます。
対応方法をちょっと考えて、修正します。

では如何でしょうか.

さっそくやってみました。 https://gist.github.com/4342882
だめですね。

リンク先の方でコメントしましたが, 一応 (def foo (meoize (fn [] ... (foo ...) ...))) の書き方で, 再帰に memoize を適用することはできるようです.

一応 memoize 擁護しましたが, いずれにせよ最初からメモ化関数として書く事しかできないので, であれば, 御 defn-memo マクロの方が分かりやすくて良いと思いますし,「用意された方法が気に入らなければ, 自分で書いてもいいんだよ」というのも嫌いじゃないです.

reduce 版でも同じようにカウントを渡さないようにできないでしょうか...

できるかなぁ...と3分考えたらできました。
メモ化しているので、再計算のコストは無しなので、カウント持ちまわる必要はありませんね。

本日版を追加します。

defn-memo マクロいいですね．tnoda-clojure • メモ化再帰関数 という記事の最後のところにも書いたのですが，memoize をトップレベルの関数に適用してしまうと，キャッシュした結果がいつまでたっても GC されないのでメモリリークのようになってしまいます．defn-memo は結果をキャッシュするのに map の atom を使っているのですが，これをたとえば LRU キャッシュで置き換えたものを用意すると便利だなと思いました．

これをたとえば LRU キャッシュで置き換えたものを用意すると便利だな

この件を調べていたときに、やはり、メモした内容が肥大化するのが問題だということで、解決策の提案がいくつかでてたりしました。
そのごどうなったろうかと、調べてみたら、ありました。 https://github.com/clojure/core.memoize
まだ中身は見ていないんですけど、名前を見るとたぶん実現されてますね。 いずれ使ってみます。

自分としては、defn-memoを作ったときにメモに入っているものを参照したり、消したりできたほうがいいので、普段使うときにはその機能を入れたものを使っています。

これ使うと勝手に xxx-data xxx-clear という関数も作ってしまうので、 公開しませんでした。
メタデータに入れることにすればその問題もなくなるな、とは思うのですが、自分用なら充分なので、このままにしています。

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; create memoised func
(defmacro defn-memo 
  "Creates memoised function.
   And also accessor of the memoized data which named <fname>-data."
  [name arg-list & body]
  `(let [mem# (atom {})]

     (defn ~(symbol (str (str name) "-data")) []
       @mem#)

     (defn ~(symbol (str (str name) "-clear")) []
       (reset! mem# {}))

     (defn ~name ~arg-list
       (if-let [e# (find @mem# ~arg-list)]
     (val e#)
     (let [ret# ~@body]
       (swap! mem# assoc ~arg-list ret#)
       ret#)))))