Lisp中的数组与列表:为什么下面的代码中的列表这么快? [英] Arrays vs. lists in Lisp: Why are lists so much faster in the code below?

问题描述

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

I got an unexpected result while solving Problem 75 in Project Euler. My code does find the correct solution, but it behaves strangely.

我的解决方案包括遍历毕达哥拉斯树( Barning的矩阵)直到达到边界限制，计算周长采用每个值的次数，最后，计算仅发生一次的周长.我公认的不整洁但可以正常运行的代码是:

My solution consists of traversing a Pythagorean tree (Barning's matrices) until the perimeter limit is reached, counting the numbers of times the perimeter assumed each value, and, lastly, counting the perimeter lengths that occurred only once. My admittedly untidy but functioning code is:

(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秒(比预期的要长得多)来遍历不是很大的树.

I expected the tree expansion to run in a few milliseconds, but the expand-node function took 8.65 seconds--a lot more than expected--to traverse a not very large tree.

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

However, I was surprised when I tweaked the code to remove the vectors...

(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毫秒.这种巨大的差异让我着迷，并希望有人能解释它发生的原因.

...and the traversing went hugely faster, taking only 35 ms. I'm intrigued by this massive difference and am hoping someone out there can explain why it happened.

谢谢，保罗

PS:我正在使用CCL.

PS: I'm using CCL for all this.

推荐答案

您没有说您正在使用哪个实现.

You didn't say which implementation you were using.

您需要找出时间在哪里.

You would need to find out, where the time is spend.

但是对我来说，列表的 MAP 的实现和在Common Lisp中与新矢量长度相等的矢量的实现似乎效率很低.即使使用一个新的向量(这会带来一些开销)，实现起来也可以更快.

But for me it looks like the implementation of MAP of a list and a vector of equal length to a new vector in your Common Lisp might be very inefficient. Even when consing a new vector, which has some overhead, the implementation can be much faster.

尝试将矢量运算实现为LOOP并进行比较:

Try to implement the vector operation as a LOOP and compare:

(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))

这个更快的版本也很重要，但已将列表操作替换为矢量操作:

This faster version conses too, but has replaced the list operations with vector operations:

(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的通用实现...

So you call MAP with a list and a vector most of the times. What is the size of the result vector? MAP has to find out by traversing the list or by some other way. The result vector length is the shortest of the argument sequence lengths. Then it has to iterate over the list and the vector. If MAP now uses generic sequence operations, the element access into the list is always traversing the list. Obviously one can write an optimized version, which does all that faster, but a Common Lisp implementation might choose to provide only a generic implementation of MAP...

这篇关于Lisp中的数组与列表:为什么下面的代码中的列表这么快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！