3

到目前为止，在测试编写相同函数的不同方法的速度时，我一直在使用该time函数，通常它可以很好地指示不同函数的相对速度（因为它们通常相差大约 100k 个周期）。

然而，在试图为一个factorial函数找到最快的方法时，time一直缺乏。这些方法不仅看起来只相差 10k-30k 周期，而且它们的总时间也相差了大约一半（我猜这是预期的）。

三个factorial功能：

(defun factorial-recusion (n)   ; 1st      
  (if (equal n 1) 
      1
      (* n (factorial (- n 1)))))

(defun factorial-loop (n)   ; 2nd
  (let ((solution 1))
    (loop for x from n downto 2
       do (setf solution (* solution x))
       finally (return solution))))

(defun factorial-do (n)     ; 3rd
  (let ((solution 1))
    (do ((x n (1- x)))
    ((< x 2) (return solution))
      (setf solution (* solution x)))))

所以，我想我有两个问题：

1.) 哪种方法factorial应该是最快的（如果有的话），为什么？

2.）如果我要通过一般方法为自己找出更快的功能，那么最好的方法是什么（出于某种原因，我认为 LOC 是一个不好的速度指标）？或许有办法查看 Lisp 字节码的反汇编？或者也许有更好、更严格的方法？

我目前在 Ubuntu 12.04 x86-64 上运行 Linux 3.2.0-26、SBCL。

4

1 回答 1

5

SBCL 不会编译为“字节码”。它编译为本机机器码。

您可以使用DISASSEMBLE.

一旦数字进入 bignum 范围，阶乘函数的速度将由 bignum 算术乘法决定。

为了更清楚：您使用哪种迭代构造，DO 或 LOOP，并不重要。大部分时间都花在乘以 bignums 上。递归版本也没有太大区别。

这是一个典型的基准问题：许多简单的数值基准由一些算术运算的运行时间（如 bignums 的乘法）支配。它们不会测量通用语言操作（如各种类型的控制流）的速度差异。

带有快速 bignum 库的慢速 Lisp 可能比使用 Lisp 编写的 Bignum 代码的优化 Lisp 编译器更快。

于 2012-07-21T12:26:12.727 回答