正在处理一些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 的速度如何快得多,因为尽管他没有明确迭代,但分区可能在幕后迭代。
最佳答案
您的版本正在计算类似的内容
(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 对象,则这种优化不可用。因此,整个过程是线性时间的,而不是二次的。
关于Clojure "look-and say"序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44899205/