Clojure "look-and say"序列

Question

正在处理一些2015 AoC学习 clojure 的问题...下面的代码对于第 40 次迭代来说足够快，但在那之后很长时间就陷入了停滞。我与其他一些人的解决方案进行了比较，但我并不清楚为什么这么慢。我尝试使用 recur，相信它与循环一样高效(并避免堆栈消耗)。我不是 100% 清楚的一件事是，仅使用 recur 与使用循环 recur 之间是否存在显着差异。我测试了两种方法，没有发现任何区别。

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

我进行基准测试的解决方案的一个例子是 Bruce Hauman 的解决方案，它非常好:

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

我意识到在我的解决方案中，我反复迭代非常大的字符串，但我不明白 Bruce 的速度如何快得多，因为尽管他没有明确迭代，但分区可能在幕后迭代。

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 对象，则这种优化不可用。因此，整个过程是线性时间的，而不是二次的。