Clojure入門 - Project Eulerを解いてみる 問２６

第二十六問

1/nを小数として表した時に、循環小数となるものの中で循環部分が一番長いnを求める。

一桁ずつ割っていって、同じ余が二回出てきた時点で循環する。

まずは余のヴェクタを作成する関数。

(defn decimal-remains [n]
  (loop [col [1]]
    (let [remain (-> (last col) (* 10) (rem n))
          new-col (conj col remain)
          element-recurring? (some #(= % remain) col)]
      (if element-recurring?
        new-col
        (recur new-col))))) 

末尾再帰で、同じ余が二回出た時点で返り値が出る。割り切れる場合は余0が二回連続で出るので、そのケースも大丈夫。

その余のヴェクタを引数に、ループの長さ（つまり同じ余同士の距離）を算出する関数：

(defn cycle-length [col]
  (let [col-length (count col)
        cycle-elem (last col)
        cycle-start (.indexOf col cycle-elem)]
    (dec (- col-length cycle-start))))

これらを組み合わせて、任意の数字nに対して、1/nが小数で表された時のループの長さを測る関数ができる。

(defn decimal-cycle [n]
  (cycle-length (decimal-remains n)))

あとは組み合わせるだけ・・・

(apply max-key decimal-cycle (range 1 1000))

と思ったらこれが１７秒かかる。なんとかならんかと思い、pmapで並列化してみようと構文を少しいじって試してみた。

(->> (range 1 1000)
     (pmap (juxt decimal-cycle identity))
     (apply max-key first)
     second)

これは今度は500msかかる。わーいやったー、と単純に喜んでしまってもいいのだが、さすがに私のパソコンで並列化しただけで30倍も早くなるわけがない。

試しにpmapではなくmapでやってみる：

(->> (range 1 1000)
     (map (juxt decimal-cycle identity))
     (apply max-key first)
     second)

これも1500msということで、元のコードに比べて10倍近く早い。そこから並列化で3倍のスピードアップ、というのは理にかなっているが、問題は何故mapとmax-keyでここまで違いが出るか、だ。

まだ要調査だが、max-keyは一旦key関数で評価したものを記憶しておいて比較に使うのではなく、比較する必要があるたびに何回もkey関数で評価しているようだ。

試しにmemoizeを使ってみる：

(def mdc (memoize decimal-cycle))
(apply max-key mdc (range 1 1000))

これだけで一気に1500msまで下がった。

とりあえずmax-keyやmin-keyを使う場合はkey関数はmemoizeしておいたほうがよさそう。

ただ、pmapを使いたいなら上記のようなmap形式の構文にしてしまったほうがさらによさそう。