时间戳

首页 > 解决方案 > Common Lisp SBCL 循环性能调整

common-lisp - Common Lisp SBCL 循环性能调整

问题描述

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

标签： common-lisp

解决方案

一方面，您可以使用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))

推荐阅读