如何优化我的递归Lisp函数

Question

我试图创建一个prime-factors返回数字素数的函数。为此，我创建了is-prime函数，并将prime-factors-helper对主要因素进行递归检查。

(defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
          (and (/= (rem n d) 0)
               (is-prime  n (- d 1)))) ()))

(defun prime-factors-helper (x n)
   (if (is-prime x) 
       (list x) 
       (if (is-prime n) 
            (if (AND (= (mod x n) 0) (<= n (/ x 2)))
                (cons n (prime-factors-helper (/ x n) n))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

(defun prime-factors (x)
    (prime-factors-helper x 2)) 

题

我有一个优化的问题。当我有大量诸如此类的123456789消息时，我会收到此错误消息Stack overflow (stack size 261120)。我相信，因为正确的答案是(3 3 3607 3803)，所以我的程序一旦使用两个前一个元素构造了列表，(3 3)查找下一个主要因素将花费很长时间。如何优化代码？

 CL-USER 53 > (prime-factors 512)
 (2 2 2 2 2 2 2 2 2)

 CL-USER 54 > (prime-factors 123456789)

 Stack overflow (stack size 261120).
   1 (abort) Return to level 0.
   2 Return to top loop level 0.

 Type :b for backtrace or :c <option number> to proceed.
 Type :bug-form "<subject>" for a bug report template or :? for other options

Answer 1

从https://codereview.stackexchange.com/a/189932/20936复制：

您的代码有几个问题。

样式

1. is-prime是C / Java风格。使用者使用primep或prime-number-p。
2. zerop比清楚(= 0 ...)。
3. Lispers使用缩进而不是括号计数来读取代码。因此，您的代码实际上是不可读的。如果不确定如何正确格式化Lisp，请使用Emacs。

堆栈溢出

is-prime 是尾递归的，因此，如果您对其进行编译，它将变成一个简单的循环，并且不应出现堆栈问题。

但是，请不要着急。

算法

迭代次数

让我们用trace来看问题：

> (prime-factors 17)
1. Trace: (IS-PRIME '17)
2. Trace: (IS-PRIME '17 '15)
3. Trace: (IS-PRIME '17 '14)
4. Trace: (IS-PRIME '17 '13)
5. Trace: (IS-PRIME '17 '12)
6. Trace: (IS-PRIME '17 '11)
7. Trace: (IS-PRIME '17 '10)
8. Trace: (IS-PRIME '17 '9)
9. Trace: (IS-PRIME '17 '8)
10. Trace: (IS-PRIME '17 '7)
11. Trace: (IS-PRIME '17 '6)
12. Trace: (IS-PRIME '17 '5)
13. Trace: (IS-PRIME '17 '4)
14. Trace: (IS-PRIME '17 '3)
15. Trace: (IS-PRIME '17 '2)
16. Trace: (IS-PRIME '17 '1)
16. Trace: IS-PRIME ==> T
15. Trace: IS-PRIME ==> T
14. Trace: IS-PRIME ==> T
13. Trace: IS-PRIME ==> T
12. Trace: IS-PRIME ==> T
11. Trace: IS-PRIME ==> T
10. Trace: IS-PRIME ==> T
9. Trace: IS-PRIME ==> T
8. Trace: IS-PRIME ==> T
7. Trace: IS-PRIME ==> T
6. Trace: IS-PRIME ==> T
5. Trace: IS-PRIME ==> T
4. Trace: IS-PRIME ==> T
3. Trace: IS-PRIME ==> T
2. Trace: IS-PRIME ==> T
1. Trace: IS-PRIME ==> T
(17)

当仅(isqrt 17) = 4需要迭代时，可以执行17次迭代。

重新计算

现在编译is-prime以将递归转换为循环，请参见：

> (prime-factors 12345)
1. Trace: (IS-PRIME '12345)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '2)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '12345)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '3)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '3)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '4)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '4115)
1. Trace: IS-PRIME ==> NIL
1. Trace: (IS-PRIME '5)
1. Trace: IS-PRIME ==> T
1. Trace: (IS-PRIME '823)
1. Trace: IS-PRIME ==> T
(3 5 823)

您正在多次检查相同数字的素数！

额外的优化

primep 可以找到除数，而不仅仅是检查素数。

优化算法

(defun compositep (n &optional (d (isqrt n)))
  "If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
  (and (> n 1)
       (> d 1)
       (if (zerop (rem n d))
           d
           (compositep n (- d 1)))))

(defun prime-decomposition (n)
  "Return the prime decomposition of n."
  (let ((f (compositep n)))
    (if f
        (nconc (prime-decomposition (/ n f))
               (prime-decomposition f))
        (list n))))

需要注意的是一个最终的优化是可能的- 记忆化的 compositep：

(let ((known-composites (make-hash-table)))
  (defun compositep (n &optional (d (isqrt n)))
    "If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
    (multiple-value-bind (value found-p) (gethash n known-composites)
      (if found-p
          value
          (setf (gethash n known-composites)
                (and (> n 1)
                     (> d 1)
                     (if (zerop (rem n d))
                         d
                         (compositep n (- d 1)))))))))

或更好的是prime-decomposition：

(let ((known-decompositions (make-hash-table)))
  (defun prime-decomposition (n)
    "Return the prime decomposition of n."
    (or (gethash n known-decompositions)
        (setf (gethash n known-decompositions)
              (let ((f (compositep n)))
                (if f
                    (append (prime-decomposition (/ n f))
                            (prime-decomposition f))
                    (list n)))))))

请注意使用或append代替 nconc。

另一个有趣的优化是将迭代compositep从降序更改 为升序。这会大大加快速度，因为它会更早地终止：

(let ((known-composites (make-hash-table)))
  (defun compositep (n)
    "If n is composite, return a divisor.
Assumes n is not divisible by anything over d."
    (multiple-value-bind (value found-p) (gethash n known-composites)
      (if found-p
          value
          (setf (gethash n known-composites)
                (loop for d from 2 to (isqrt n)
                  when (zerop (rem n d))
                  return d))))))