common-lisp - 为什么列表比简单访问的向量更快？

Question

我知道有类似的问题，例如Arrays vs. lists in Lisp: Why are lists so much faster in the code below? ，但即使对于简单的元素访问，列表似乎也比向量快，这是违反直觉的。这是我的例子:

(let ((x '(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x #(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

第一个 block 在我的机器上运行 SBCL 几乎是第二个 block 的两倍。 (如果我测试读取访问时间，那么列表和向量的时间几乎相同)。我预计列表会慢 10 倍，因为它需要遍历到最后才能找到第 9 个元素。为什么列表更快？

Answer 1

奇怪的行为是由于您正在修改常量数据，这可能导致未定义的行为(参见 manual):

The consequences are undefined if literal objects (including quoted objects) are destructively modified.

如果你改变这两个表达式来修改两个非文字数据结构，比如:

(let ((x (list 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x (vector 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

那么结果将完全不同，正如另一个答案中所显示的那样。