为什么Clojure比Python慢10倍呢？

Question

我最近开始学习Clojure，并决定练习Euler问题，以获得可用数据结构的窍门，并练习递归和循环。在

我尝试了各种方法来处理Problem 50，但是不管我做了什么，找到1000000的解决方案都没有完成。在我查看了其他人做了什么之后，我猜我正在做的事情也不应该永远持续下去，所以我在Python中输入了等价的算法，看看问题是否在于我对Clojure的东西或Java设置缺乏理解。Python在10秒内完成。对于100000以下的素数，Python版本在0.5秒内完成，Clojure在5秒内完成。在

我发布的Clojure版本是专门为匹配Python代码而创建的。你能帮我理解为什么在性能上有这么大的差别吗？我应该使用未检查的add，type hints，primitives（但是在哪里？）或者什么？在

下面是Clojure：

(defn prime? [n]
  (let [r (int (Math/sqrt n))]
    (loop [d 2]
      (cond
        (= n 1) false
        (> d r) true
        (zero? (rem n d)) false
        :other (recur (inc d))))))

(defn primes []
  (filter prime? (iterate inc 2)))


(defn cumulative-sum [s]
  (reduce 
    (fn [v, x] (conj v (+ (last v) x))) 
    [(first s)] 
    (rest s)))


(defn longest-seq-under [n]
  "Longest prime seq with sum under n"
  (let [ps (vec (take-while #(< % n) (primes))) ; prime numbers up to n
        prime-set (set ps)  ; set for testing of inclusion
        cs (cumulative-sum ps)
        cnt (count ps)
        max-len (count (take-while #(< % n) cs)) ; cannot have longer sequences
        sub-sum (fn [i j] ; sum of primes between the i-th and j-th      
                  (- (cs j) (get cs (dec i) 0)))
        seq-with-len (fn [m] ; try m length prime sequences and return the first where the sum is prime
                       (loop [i 0] ; try with the lowest sum
                         (if (> i (- cnt m)) ; there are no more elements for and m length sequence
                           nil ; could not find any
                           (let [j (+ i (dec m)) ; fix length
                                 s (sub-sum i j)]
                             (if (>= s n) ; overshoot
                               nil
                               (if (prime-set s) ; sum is prime
                                 [i (inc j)] ; we just looked for the first
                                 (recur (inc i))))))))] ; shift window
        (loop [m max-len] ; try with the longest sequence
          (if (not (zero? m))
            (let [[i j] (seq-with-len m) ]
              (if j 
                (subvec ps i j)
                (recur (dec m))))))))                    



(assert (= [2 3 5 7 11 13] (longest-seq-under 100)))

(let [s1000  (longest-seq-under 1000)]
  (assert (= 21 (count s1000)))
  (assert (= 953 (reduce + s1000))))

; (time (reduce + (longest-seq-under 100000))) ; "Elapsed time: 5707.784369 msecs"

在Python中也是这样：

^{pr2}$

谢谢

Answer 1

我认为速度减慢是因为您迭代longest-seq-under中的序列的次数；每一次迭代都会付出代价。这是一个快速的版本，基于您的代码和发布的答案here的组合。请注意，primes是惰性的，因此我们可以将其与defvsdefn绑定：

(defn prime? [n]
  (let [r (int (Math/sqrt n))]
    (loop [d 2]
      (cond (= n 1) false
            (> d r) true
            (zero? (rem n d)) false
            :else (recur (inc d))))))

(def primes (filter prime? (iterate inc 2)))

(defn make-seq-accumulator
  [[x & xs]]
  (map first (iterate
              (fn [[sum [s & more]]]
                [(+ sum s) more])
              [x xs])))

(def prime-sums
  (conj (make-seq-accumulator primes) 0))

(defn euler-50 [goal]
  (loop [c 1]
    (let [bots (reverse (take c prime-sums))
          tops (take c (reverse (take-while #(> goal (- % (last bots)))
                                            (rest prime-sums))))]
      (or (some #(when (prime? %) %)
                (map - tops bots))
          (recur (inc c))))))

在我的机器上大约6毫秒就完成了：

^{pr2}$

Answer 2

对于Python为什么工作而Clojure不起作用的问题，我将接受我自己的评论：使用向量的last是一种线性操作，它阻止了累积和按我预期的方式计算。在

更新函数以使用如下瞬态矢量：

(defn cumulative-sum-2 [s]
  (loop [[x & xs] s
         ss 0
         acc (transient [])]
    (if x      
      (let [ssx (+ ss x)]
        (recur xs ssx (conj! acc ssx)))
      (persistent! acc))))

结果Clojure版本的运行时间仅为Python的两倍，且一致。对于相同的操作，我有点希望Clojure比Python快，不知道我是否还漏掉了什么。顺便说一下，我用的是1.2。在

谢谢