clojure"看 - 说"顺序

Question

研究一些2015年的AoC问题以学习clojure ......下面对于第40次迭代来说足够快,但在此之后又停止了很多.我与其他一些人的解决方案进行了比较,对我来说,为什么这么慢,这一点并不明显.我试图使用recur相信它与循环一样高效(并避免堆栈消耗).我不是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))

我对其进行基准测试的解决方案的一个例子是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对象,则该优化不可用.结果,整个过程是线性时间,而不是二次方.