常见的 Lisp SBCL 循环性能调整

Question

我正在使用欧拉项目问题 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 秒内运行。 2 倍加速，所以方向正确。还能做些什么来加快速度？对我来说最明显的事情是最小倍数的 do 循环。首先，我不知道如何为多个变量指定类型。你是怎么做到的？有没有更好的方法来执行开放式循环，从而产生更少的代码？您将如何尝试从这里提高性能？C 代码在大约 1.3 秒内运行，所以我很乐意将其缩短到 2 或 3 秒。

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))

代码改进：

• 请不要像指甲剪一样留下括号。

• 将if用于双分支条件。

• Loop有一个always关键字：

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

Answer 2

我不是CL的完全专家，但想提供一些建议，您可能会发现这些建议对您有所帮助。

一般风格

您不应在额外的行上留下右括号。例如，请参阅此处以获取有关样式的一些注释。此外，文档字符串将帮助其他人和您自己将来理解您的代码。

性能

我还没有审查我自己的这个问题的解决方案，但我想指定fixnum而不是integer会导致性能的另一个因素为 2，并且应该可以解决此问题。

圈

您可以使用loopsalways子句编写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 的整数的所有质因数并构建其乘积。