通用Lisp SBCL循环性能调优

Question

我正在使用 Project Euler 问题 5 的暴力方法来测试性能调整 CL 代码。我对这门语言很新，想知道如何做到这一点。我编写了一个 C 实现，大约运行时间为 1.3 秒。我的初始、天真的 CL 实现大约需要 15 秒。

这是我的初始 CL 代码：

(defpackage :problem-5
  (:use #:cl)
  (:export :divides-even-p
           :has-all-divisors
           :smallest-multiple)
  )

(in-package :problem-5)

(defun divides-even-p (num divisor)
  (= 0 (rem num divisor))
  )

(defun has-all-divisors (num start stop)
  (loop for divisor from start to stop do
       (cond
         ((not (divides-even-p num divisor)) (return-from has-all-divisors nil))
         )
       (+ divisor 1)
       )
  t
  )

(defun smallest-multiple (n)
  (do ((multiple 1 (+ multiple 1)))
      ((has-all-divisors multiple 1 n) (format t "~A" multiple))
    ))

(time (smallest-multiple 20))

目前我了解的技巧包括：1) 优化速度和安全性，2) 内联函数和3) 明确设置变量类型。应用这些技巧，我得到以下代码：

(defpackage :problem-5
  (:use #:cl)
  (:export :divides-even-p
           :has-all-divisors
           :smallest-multiple)
  )

(in-package :problem-5)

(declaim (optimize (speed 3) (safety 0))
         (inline divides-even-p)
         (inline has-all-divisors)
         )

(defun divides-even-p (num divisor)
  (declare (type integer num divisor))

  (zerop (rem num divisor))
  )

(defun has-all-divisors (num start stop)
  (declare (type integer num start stop))

  (loop for divisor of-type integer from start to stop do
       (cond
         ((not (divides-even-p num divisor)) (return-from has-all-divisors nil))
         )
       )
  t
  )

(defun smallest-multiple ()
  (do ((multiple 1 (+ multiple 1)))
      ((has-all-divisors multiple 2 20) (format t "~A" multiple))
    ))

(time (smallest-multiple))

现在我运行那个版本时，只需要7秒而不是15秒。速度提高了两倍，走在正确的方向上。还有什么可以做来加快速度？对我来说最明显的是 smallest-multiple 中的 do 循环。首先，我无法弄清楚如何为 multiple 变量指定类型。你怎么做？有没有更好的方法来做开放式循环以减少代码量？你会如何尝试从这里提高性能？C 代码大约需要1.3秒才能运行，所以如果可以将其降低到2或3秒，我会很满意。

- Rich

---

采用暴力方法并不排斥避免不必要的工作。你想要一个能被2到20中所有数整除（尤其是20）的数字。因此从20开始，每次加上20（这也适用于C语言）。 - coredump

Answer 1

首先，你可以使用fixnum代替integer。后者包含所有整数，前者仅包括适合于机器字减去一些标记位的整数（通常大约为61或62位）。

do循环中的声明在循环体的开头：

(do ((m 1 (1+ m)))
    ((has-all-divisors m 2 20)
     m)
  (declare (fixnum m)))

您可以在这里使用loop：

(loop :for m :of-type fixnum :upfrom 1
      :when (has-all-divisors m 2 20)
        :do (return m))

代码优化:

• Please don't leave parentheses lying around like nail clippings.

• Use if for a two-branch conditional.

• Loop has an always keyword:

  (loop :for divisor :of-type fixnum :from start :to stop
        :always (divides-even-p num divisor))
  

- Svante

Answer 2

我对CL不是完全的专家，但我想给出一些建议，可能会对你有所帮助。

通用风格

不应该把右括号单独放在一个新行。例如，可以看看这里有些关于风格的注释。此外，文档字符串会帮助他人和你自己在未来理解代码。

性能

我还没有审查过我自己的解决方案，但我猜测指定使用fixnum而不是integer将导致另一个2倍的性能因素，并且应该适用于这个问题。

循环

你可以使用loop的always子句更富表现力地编写has-all-divisors:

(defun has-all-divisors (num start stop)
  (declare (type fixnum num start stop))
  (loop for divisor of-type fixnum from start to stop
        always (divides-even-p num divisor)))

替代方案

如果我记得这个问题没错的话，您可以使用另一个算法，应该会更快。收集2到20之间所有整数的质因数并计算它们的乘积。

- Martin Buchmann