1

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

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

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

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

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

4

2 回答 2

4

我无法重现它。

在 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 且元素类型为 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
于 2012-10-22T10:33:25.527 回答
3

除了已经说过的关于数组与列表的内容之外，没有“最快”排序算法之类的东西。这最终取决于您要对哪些数据进行排序。一些算法在包含相似值的集合上表现更好，而另一些算法在包含接近排序值的集合上表现更好。

在实践中，可能存在其他复杂情况，例如在排序期间创建的额外 cons 或在数组排序期间分配的额外内存。需要调用 GC 的东西，这绝对可以扭转潮流。

每当您遇到需要排序的特定实际问题时，您都需要考虑具体情况以及您将处理的数据类型。例如，在渲染动画时对 3 维空间中的 Z 顶点进行排序可能最受益于对链表和几乎排序的数据进行操作的算法，气象研究数据的排序可能会受益于最能处理的算法以前未排序的主要是唯一数据。一些特定的软件可以进行向量化插入排序，这将比每个操作算法的任何单个值快很多倍，依此类推。

对一组随机数进行排序通常不能很好地表明您的代码将如何处理实际数据。

于 2012-10-22T01:13:49.073 回答