lisp - Lisp代码没有响应

扰流器警报：这是欧拉计划第7条的答案。
我正在学习Lisp，我正在使用compileonline.com来运行我的代码但是一个简单的程序内存不足，所以我换成了桌面版本然而，即使是这样，内存也快用完了有人能告诉我为什么这么糟吗？
以当前形式，它不会挂起，但如果我将其更改为：

(if (= primecount 10001)

它挂着即使是小到1000的东西也挂着。

(setq current 3)
(setq primecount 1)
(setq primes (list 2))
(setq isprime "yes")

(loop for x from current do
  (list
    (setq isprime "yes")
    (loop
      for prime in primes do
        (if (= (mod current prime) 0)
          (list (setq isprime nil) (return))
          nil
        )
    )
    (if isprime
      (list
        (setq primecount (+ primecount 1))
        (setq primes (cons current primes))
        (if (= primecount 100)
          (return)
          nil
        )
      )
      (setq current (+ current 1))
    )
  )
)

(write-line (write-to-string primes))

最佳答案

问题不在于记忆，而在于速度。
你在克服知识不足方面很有创造力：）实际上，我们在Common Lisp中有progn，它将要求值的几个表达式分组如下：

(defun myprimes-to (n &aux          ;; &aux vars may have init values
                      (current 3)
                      (primecount 1)
                      (isprime t) ; "yes"   ;; t is better
                      (primes (list 2))
    (loop  ;for x from current do   ;; for a bare loop, just `loop` is enough
      (progn  ;list                 ;; `progn` groups expressions together to be
        (setq isprime t) ; "yes"    ;;    evaluated in order, one after another
        (loop                       ;;      (not even needed here, see comments below)
          for prime in primes do
            (if (= (mod current prime) 0)
                (progn  ;list
                  (setq isprime nil)
                  (return))         ;; exit the loop
                nil))               ;; don't have to have alternative clause
        (if isprime
            (progn  ;list
              (incf primecount)  ; (setq primecount (+ primecount 1)) ;; same but shorter
              (setq primes (cons current primes))
              (if (= primecount n)  ;; abstract the n as function's argument
                  (return)          ;; exit the loop
                  nil))
            ;; What?? increment your loop var _only_ if it's not prime?
            (setq current (+ current 1)))))
    ;; (write-line (write-to-string primes))
    primes)                         ;; just return them

因此，如果current是素数，则重试由于它最后一次被添加到primes中，现在它将把自己视为非素数，迭代将继续进行结果是正确的，但逻辑混乱。
更重要的是，在算法方面存在两个主要的低效性：到目前为止，所有的测试都是primes测试，反之亦然但是，任何一个给定的数都比一个大的数有更小的除数；所以我们应该按升序用素数来测试。而且，当素数p是p*p > current时，我们可以停止，因为如果current == a*b和a <= b，那么a*a <= b*a == current提前停止会带来巨大的加速，它将运行时复杂度从n到2变为粗略的，约为1.5（n个素数）。
请注意：从算法上讲，您的代码比~n^2差。如果用素数按升序测试的话，它将是~n^2--为什么这很重要它为你的问题提供了部分答案：你的问题不是记忆力，而是速度无论代码完成n=100所需的时间是多少，要达到n=1000所需的时间将超过100倍（因为1000/100==10，和10^2=100）而要达到n=10000，则需要100倍以上的时间因此，如果n=100问题占用了运行时间的一秒钟，n=1000将占用100秒（~2分钟）和n=10001-200分钟（超过3小时）。
我们总是可以根据经验来估计运行时的增长顺序；请参见this WP article。
所以你需要保持primes的升序，并在O（1）时间内将每个新素数保持到它们的末尾您需要获得与代码行append所获得的结果相同的结果；但是您不能使用此代码行，因为它在时间上是O（n），并且会大大降低整个程序的速度与(setq primes (append primes (list current)))相同我们不能把(setq primes (reverse (cons current (reverse primes))))保持在相反的顺序，因为我们必须按升序进行测试，而为每个新的primes调用(reverse primes)也是一个O（n）时间操作。
解决方法是使用current：rplacd即使这仍然是不对的，因为(rplacd (last primes) (list current))也是一个O（n）操作相反，您必须维护一个额外的变量，指向prime s列表的最后一个cons单元格，每次在那里添加一个新的prime:。
当您运行固定代码时，您会发现它在大约0.1秒内完成10000个作业，并在该范围内以大约~n^1.4run-time orders of growth的速度运行。

关于lisp - Lisp代码没有响应，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20776389/