clojure「look-and say」序列

Question

處理一些2015 AoC問題以學習clojure ...下面是第40次迭代的足夠快，但在此之後爬得很快。我和其他幾個人的解決辦法相比，我不明白爲什麼這麼慢。我試圖用反覆認爲它和循環一樣高效（並避免堆棧消耗）。有一件事我沒有100％清楚，就是在使用復發和使用循環復發之間存在顯着差異。我對它進行了兩種測試，沒有看到任何區別。

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

我在我的解決方案意識到我正在反覆迭代非常大的字符串，但我不知道看看布魯斯的速度如此之快，因爲雖然他沒有明確地迭代，但分區可能在幕後迭代。

Answer 1

你的版本是計算像

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

這是建立對每兩個字符一個全新的String對象。由於這涉及在每一步中迭代輸入和輸出字符串中的每個字符，因此您的操作在字符串的長度上是二次方的。

你比較的解決方案是不同的：它建立一個惰性的整數序列，這是一個線性時間過程。然後，它像

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

這是一樣的

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

和str，當有多個參數調用，使用一個StringBuilder有效地逐步建立起來的結果，優化不是如果您在每個中間步驟都需要一個完整的String對象，則可用。結果，整個過程是線性時間的，而不是二次的。