我试图创建一个函数prime-factors来返回一个数的素数因子为此，我创建了is-prime函数，并将对素数进行递归检查。
(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))
问题
我有一个优化的问题当我有一个大数字，比如
prime-factors-helper时，我会得到这个错误消息123456789我相信，因为正确答案是Stack overflow (stack size 261120)，所以我的程序一旦用前两个元素构造了列表，就需要很长时间才能找到下一个素因子如何优化代码？ 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
最佳答案
从https://codereview.stackexchange.com/a/189932/20936复制：
你的代码有几个问题。
风格is-prime是C/Java风格Lispers使用primep或prime-number-p。zerop比(= 0 ...)更清晰。
Lispers使用缩进而不是paren计数来读取代码你的
因此代码实际上是不可读的如果是，请使用Emacs
不确定如何正确格式化lisp。
堆栈溢出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))))
注意最后一个优化是可能的-
memoization的
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)))))))))
或者，更好的是：
(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)))))))
注意使用或
prime-decomposition instead ofappend。另一个有趣的优化是在
nconc从下降到上升。这将大大加快它的速度，因为它将提前终止
经常：
(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))))))
关于optimization - 如何优化我的递归Lisp函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49352407/