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))

では如何でしょうか.

さっそくやってみました。 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#)))))