arrays - 为什么 lisp 中的列表排序比数组排序更快？

Question

我想当顺序处理序列时我应该更喜欢列表，如果我需要随机访问元素则更喜欢数组。

所以，我写了几行代码来证实我的想法。首先，我写了一个函数来测试多个点。它显示它在列表中运行得更快。

但后来我尝试了排序功能。由于排序函数需要随机访问元素，我希望它在数组中运行得更快。但结果恰恰相反。

(defun test-performance-map-mapcar ()
  (let* ((lst (generate-random 1000000))
     (arr (lst-to-arr lst)))
    (time (atom (sort lst #'>)))
    (time (atom (sort arr #'>)))))

那么，是排序函数应用了某种算法来适应列表，还是列表真的比 lisp 中的数组更有效？

Answer 1

我无法复制它。

在 LispWorks 中，对随机数向量进行排序比对随机数列表进行排序更快。

(defun test ()
  (let* ((list (loop repeat 10000000 collect (random 1000000)))
         (vector (coerce list 'vector)))
    (time (sort list #'>))
    (time (sort vector #'>))
    (values)))

例子:

CL-USER 9 > (test)
Timing the evaluation of (SORT LIST (FUNCTION >))

User time    =        8.697
System time  =        0.027
Elapsed time =        8.626
Allocation   = 170168 bytes
145 Page faults
Timing the evaluation of (SORT VECTOR (FUNCTION >))

User time    =        5.951
System time  =        0.018
Elapsed time =        5.904
Allocation   = 120512 bytes
86 Page faults

向量为 5.951 秒，列表为 8.697。

在 Common Lisp 中，一维数组就是向量。 SORT 也不适用于其他多维数组。

CL-USER 10 > (vector 'a 'b 'c)
#(A B C)

CL-USER 11 > (describe *)

#(A B C) is a (SIMPLE-VECTOR 3)
0      A
1      B
2      C

CL-USER 12 > (arrayp **)
T

CL-USER 13 > (typep (vector 'a 'b 'c) '(array symbol (3)))
T

因此，一个包含三个符号的向量也是一个长度为 3 且元素类型为 SYMBOL 的一维数组。

以我的示例(配备 Intel i7 处理器的 Apple Macbook Air)为例:

Implementation   | faster | seconds
-----------------+--------+--------
LispWorks 64bit  | vector |  5.951
Clozure CL 64bit | vector |  6.727
SBCL 1.1 64bit   | list   |  8.890
CLISP            | list   | 42.968