clojure - 为什么我的 Clojure 代码运行这么慢？

Question

以下是我对 4clojure Problem 108 的回答

我能够通过前三个测试，但最后一个测试超时。在最后一个测试中，代码运行得非常非常慢。到底是什么原因造成的？

((fn [& coll] (loop [coll coll m {}]
    (do
        (let [ct (count coll)
                ns (mapv first coll)
                m' (reduce #(update-in %1 [%2] (fnil inc 0)) m ns)]
            (println m')
            (if (some #(<= ct %) (mapv m' ns))
                (apply min (map first (filter #(>= (val %) ct) m')))
                (recur (mapv rest coll) m'))))))
 (map #(* % % %) (range)) ;; perfect cubes
 (filter #(zero? (bit-and % (dec %))) (range)) ;; powers of 2
 (iterate inc 20))

Answer 1

您正在从每次迭代的每个输入中收集下一个值(recur (mapv rest coll) m')

您的其中一个输入生成值的速度非常慢，并且很快就会加速到非常高的值:(filter #(zero? (bit-and % (dec %))) (range))。

您的代码大部分时间都花在通过加一并测试位来发现 2 的幂。

您不需要包含出现次数的所有输入的映射。对于不是目前找到的最低值的项目，您无需查找下一个值。我不会发布解决方案，因为它是一个练习，但消除每次迭代中最低的不匹配值应该是一个开始。