performance - 如何着手编写核心功能，而不是使用命令式风格？

Question

我已将这段代码(下面的代码片段)从 Python 翻译成 Clojure。我在这里用 Clojure 的 loop-recur 替换了 Python 的 while 结构。但这看起来并不符合习惯。

(loop [d 2 [n & more] (list 256)]
      (if (> n 1)
        (recur (inc d)
               (loop [x n sublist more]
                 (if (= (rem x d) 0)
                   (recur (/ x d) (conj sublist d))
                   (conj sublist x))))
        (sort more)))

这个例程给我 (3 3 31)，这是 279 的质因数。对于 256，它给出 (2 2 2 2 2 2 2 2)，这意味着 2^8。

此外，对于较大的值，它的性能更差，比如 987654123987546 而不是 279；而 Python 的对应物就像魅力一样。

如何开始编写核心函数，而不是按原样翻译命令式代码？具体来说，如何改进这一点？

谢谢。

[已编辑]

这是我上面提到的python代码，

def prime_factors(n):
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
    return factors

Answer 1

Clojure 中 Python 代码的直接翻译是:

(defn prime-factors [n]
  (let [n       (atom n)  ;; The Python code makes use of mutability which
        factors (atom []) ;; isn't idiomatic in Clojure, but can be emulated
        d       (atom 2)] ;; using atoms
    (loop []
      (when (< 1 @n)
        (loop []
          (when (== (rem @n @d) 0)
            (swap! factors conj @d)
            (swap! n quot @d)
            (recur)))
        (swap! d inc)
        (recur)))
    @factors))

(prime-factors 279)                    ;; => [3 3 31]
(prime-factors 987654123987546)        ;; => [2 3 41 14389 279022459]
(time (prime-factors 987654123987546)) ;; "Elapsed time: 13993.984 msecs"
                                       ;; same performance on my machine
                                       ;; as the Rosetta Code solution

---

您可以改进这段代码，使其更加地道:

• 从嵌套循环到单个循环:

    (loop []
      (cond
        (<= @n 1)            @factors
        (not= (rem @n @d) 0) (do (swap! d inc)
                                 (recur))
        :else                (do (swap! factors conj @d)
                                 (swap! n quot @d)
                                 (recur))))))

• 摆脱原子:

    (defn prime-factors [n]
      (loop [n       n
             factors []
             d       2]
        (cond
          (<= n 1)           factors
          (not= (rem n d) 0) (recur n factors (inc d))
          :else              (recur (quot n d) (conj factors d) d))))

• 将 == 0 替换为 zero?:

          (not (zero? (rem n d))) (recur n factors (inc d))

你也可以彻底修改它来制作一个懒惰的版本:

(defn prime-factors [n]
  ((fn step [n d]
     (lazy-seq 
       (when (< 1 n)
         (cond
           (zero? (rem n d)) (cons d (step (quot n d) d))
           :else             (recur n (inc d)))))
   n 2))

---

我计划在这里有一个关于优化的部分，但我不是专家。我唯一能说的是，当 d 大于 n 的平方根时，您可以通过中断循环来简单地使这段代码更快:

    (defn prime-factors [n]
      (if (< 1 n)
        (loop [n       n
               factors []
               d       2]
          (let [q (quot n d)]
            (cond
              (< q d)           (conj factors n)
              (zero? (rem n d)) (recur q (conj factors d) d)
              :else             (recur n factors (inc d)))))
        []))

    (time (prime-factors 987654123987546)) ;; "Elapsed time: 7.124 msecs"