Lisp中的数组与列表：为什么下面的代码中的列表这么快？

Question

在Project Euler中解决问题75时，我得到了意外的结果。我的代码确实找到了正确的解决方案，但是行为却很奇怪。

我的解决方案包括遍历毕达哥拉斯树（Barning's矩阵）直到达到周界极限，计算周界假定每个值的次数，最后计算仅发生一次的周长。我公认的不整洁但有效的代码是：

(defparameter *barning-matrixes*
   '(#(1 -2  2) #(2 -1  2) #(2 -2  3)
     #(1  2  2) #(2  1  2) #(2  2  3)
     #(-1 2  2) #(-2 1  2) #(-2 2  3)))

(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
"Takes a primitive Pythagorean triple in a vector and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
   (let ((perimeter (reduce #'+ n)))
   (unless (> perimeter 1500000)
     (let ((next-nodes (mapcar #'(lambda (x)
                                   (reduce #'+ (map 'vector #'* n x))) *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(expand-node #(3 4 5))  ; Takes too darn long :-(
(count 1 *lengths*)

我希望树扩展可以在几毫秒内运行，但是遍历一棵不是很大的树需要花8.65秒，比预期的要多得多。

但是，当我调整代码以删除矢量时，我感到很惊讶...

(defparameter *barning-matrixes*
   '((1 -2  2) (2 -1  2) (2 -2  3)
     (1  2  2) (2  1  2) (2  2  3)
     (-1 2  2) (-2 1  2) (-2 2  3)))


(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
"Takes a primitive Pythagorean triple in a list and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
   (let ((perimeter (reduce #'+ n)))
   (unless (> perimeter 1500000)
     (let ((next-nodes (mapcar #'(lambda (x) (reduce #'+ (mapcar #'* n x))) *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(expand-node '(3 4 5))  ; Much faster, but why?!
(count 1 *lengths*)

...而且遍历速度大大加快，仅需35毫秒。这种巨大的差异令我着迷，并希望有人能解释为什么会发生这种情况。

谢谢Paulo

PS：我正在使用CCL。

Answer 1

您没有说您正在使用哪种实现。

您需要找出时间花在哪里。

MAP但对我来说，在 Common Lisp 中实现一个列表和一个与新向量长度相等的向量可能效率非常低。即使使用新的向量（有一些开销），实现也会快得多。

尝试将向量运算实现为循环并进行比较：

(loop with v = (make-array (length n))
      for n1 across n
      for x1 across x
      for i from 0
      do (setf (aref v i) (* n1 x1))
      finally (return v))

这个更快的版本也可以工作，但是用向量运算替换了列表运算：

(defparameter *barning-matrixes*
  #(#(1 -2  2) #(2 -1  2) #(2 -2  3) #(1  2  2) #(2  1  2) #(2  2  3) #(-1 2  2) #(-2 1  2) #(-2 2  3)))

(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
  "Takes a primitive Pythagorean triple in a vector and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
  (let ((perimeter (reduce #'+ n)))
    (unless (> perimeter 1500000)
      (let ((next-nodes
             (loop with v = (make-array (length *barning-matrixes*))
                   for e across *barning-matrixes*
                   for i from 0
                   do (setf (aref v i)
                            (reduce #'+
                                    (loop with v = (make-array (length n))
                                          for n1 across n
                                          for x1 across e
                                          for i from 0
                                          do (setf (aref v i) (* n1 x1))
                                          finally (return v))))
                   finally (return v))))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(time (expand-node #(3 4 5)))

让我们看看你的代码：

(defun expand-node (n)

; here we don't know of which type N is. You call it from the toplevel
; with a vector, but recursive calls call it with a list

  "Takes a primitive Pythagorean triple in a vector and traverses
 subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
  (let ((perimeter (reduce #'+ n)))
    (unless (> perimeter 1500000)
      (let ((next-nodes (mapcar #'(lambda (x)    ; this mapcar creates a list
                                    (reduce #'+
                                            (map 'vector
                                                 #'*
                                                 n  ; <- list or vector
                                                 x))) ; <- vector
                                *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))   ; this subseq returns a list most of the times...
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

MAP因此，大多数时候您都使用列表和向量进行调用。结果向量的大小是多少？MAP 必须通过遍历列表或通过其他方式来查找。结果向量长度是参数序列长度中最短的一个。然后它必须迭代列表和向量。如果 MAP 现在使用通用序列操作，则对列表的元素访问始终是遍历列表。显然，人们可以编写一个优化版本，它的速度更快，但 Common Lisp 实现可能会选择仅提供 MAP 的通用实现...