clojure "look-and say"シーケンス

Question

作業中2015 AoC clojureを学ぶ上での問題...以下は40回目の反復では十分に速いですが、それ以降はほとんど停止します。私はいくつかの他の人々のソリューションと比較して、なぜこれがなぜとても遅いのかはすぐわかりません。私はそれがループほど効率的であると信じて再帰を使用しようとしました（スタック消費を避けるため）。私が100％明確にしていないことの1つは、反復を使用しているか、ループ反復を使用しているかの違いがあるかどうかです。私は両方の方法でそれをテストし、違いは見られませんでした。

(def data "3113322113") 

(defn encode-string [data results count] 
    (let [prev (first data) 
     curr (second data)] 
    (cond (empty? data) results 
      (not= prev curr) 
      (recur (rest data) (str results count prev) 1) 
      :else (recur (rest data) results (inc count))))) 

(count 
(nth (iterate #(encode-string % "" 1) data) 40 #_50)) 

本当にいいです、私はあるブルースHaumanさんをベンチマークソリューションの例：私は繰り返し、非常に大きな文字列を反復処理しています私の溶液中で実現

(defn count-encode [x] 
    (apply str 
     (mapcat 
      (juxt count first) 
      (partition-by identity x)))) 

が、私はしません彼が明示的に反復しているわけではありませんが、パーティションはたぶんシーンの裏で反復しているので、Bruceの方がはるかに高速です。

Answer 1

あなたのバージョンは、すべての2つの文字のためのブランドの新しいStringオブジェクトを構築している

(str "11" (str "22" (str "31" ...))) 

のようなものを計算しています。これは、各ステップで入力文字列と出力文字列のすべての文字を繰り返し処理するため、文字列の長さが2次の演算になります。

あなたが比較しようとしているソリューションは異なります。これは、遅延のある一連の整数を構築します。これは、線形時間プロセスです。次に、それは、

(str 1 1 2 2 3 1 ...) 

とstrと同じである

(apply str [1 1 2 2 3 1]) 

のようなものは、複数の引数で呼び出されたときに、効率的にインクリメンタル結果を構築するためのStringBuilderを使用しないで最適化を行いますすべての中間ステップで本格的なStringオブジェクトを要求する場合に使用できます。結果として、プロセス全体は二次的ではなく線形時間である。