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