5

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

我的解决方案包括遍历毕达哥拉斯树（巴宁矩阵）直到达到周长限制，计算周长假定每个值的次数，最后计算仅出现一次的周长。我公认的不整洁但功能正常的代码是：

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

我预计树扩展将在几毫秒内运行，但 expand-node 函数需要 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 毫秒。我对这种巨大的差异很感兴趣，并希望有人能解释为什么会发生这种情况。

谢谢，保罗

PS：我正在使用 CCL 来完成这一切。

4

4 回答 4

4

你没有说你使用的是哪个实现。

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

但对我来说，MAP在你的 Common Lisp 中实现一个列表和一个与新向量等长的向量可能效率很低。即使使用具有一些开销的新向量，实现也可以更快。

尝试将向量操作实现为 LOOP 并进行比较：

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

于 2016-07-21T07:37:42.497 回答
4

欢迎来到复杂的 Common Lisp 优化！首先要注意的是不同实现执行的不同程序优化策略：我在 SBCL 中尝试了您的示例，它们几乎在同一时间都非常有效地执行，而在 CCL 中，向量版本的执行速度要慢得多列表版本。我不知道您尝试过哪种实现，但您可以尝试使用不同的实现来查看非常不同的执行时间。

从 CCL 中的一些测试来看，在我看来主要问题来自这种形式：

(map 'vector #'* n x)

它的执行速度比相应的列表版本慢得多：

(mapcar #'* n x)

使用time我已经看到矢量版本消耗了很多。

这个第一印象已经通过简单地改变map，map-into使用辅助向量得到证实。实际上，以下版本在 CCL 中比列表版本稍快：

(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))
         (temp-vector (make-array 3 :initial-element 0)))
     (unless (> perimeter 1500000)
       (let ((next-nodes (mapcar #'(lambda (x)
                                   (reduce #'+ (map-into temp-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))))))
于 2016-07-21T07:41:49.947 回答
3

在 SBCL 上检查向量 #(1 2 3) 给出：

Dimensions: (3)
Element type: T
Total size: 3
Adjustable: NIL
Fill pointer: NIL
Contents:
0: 1
1: 2
2: 3

您可以看到要存储的数据比在列表中要多一些，尽管向量的确切内部表示因实现而异。对于像您的示例中那样不断被复制的小向量，您最终可能会分配比列表更多的内存，这在下面的字节 consed行中可见。分配内存有助于运行时间。在我的测试中，请注意时间差异没有您的测试那么大。

;; VECTORS
(time (expand-node #(3 4 5)))
;; Evaluation took:
;;   2.060 seconds of real time
;;   2.062500 seconds of total run time (1.765625 user, 0.296875 system)
;;   [ Run times consist of 0.186 seconds GC time, and 1.877 seconds non-GC time. ]
;;   100.10% CPU
;;   4,903,137,055 processor cycles
;;   202,276,032 bytes consed

;; LISTS
(time (expand-node* '(3 4 5)))
;; Evaluation took:
;;   0.610 seconds of real time
;;   0.609375 seconds of total run time (0.609375 user, 0.000000 system)
;;   [ Run times consist of 0.016 seconds GC time, and 0.594 seconds non-GC time. ]
;;   99.84% CPU
;;   1,432,603,387 processor cycles
;;   80,902,560 bytes consed
于 2016-07-21T07:38:00.517 回答
2

在我尝试优化代码时，每个人都已经回答了，所以我将这个版本放在这里，不再解释太多。它应该运行得相当快，至少在 SBCL 上是这样。

(declaim (optimize (speed 3) (safety 0) (debug 0)))

(declaim (type (simple-array (simple-array fixnum 1) 1) *barning-matrixes*))
(defparameter *barning-matrixes*
  (map '(simple-array (simple-array fixnum 1) 1)
       (lambda (list)
         (make-array 3 :element-type 'fixnum
                       :initial-contents list))
       '((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))))

(declaim (type (simple-array fixnum 1) *lengths*))
(defparameter *lengths* (make-array 1500001 :element-type 'fixnum
                                            :initial-element 0))

(declaim (ftype (function ((simple-array fixnum 1))) expand-node))
(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"
  (loop with list-of-ns = (list n)
        for n = (pop list-of-ns)
        while n
        do (let ((perimeter (let ((result 0))
                              (declare (type fixnum result))
                              (dotimes (i (length n) result)
                                (incf result (aref n i))))))
             (declare (type fixnum perimeter))
             (unless (> perimeter 1500000)
               (let ((next-nodes
                       (let ((result (list)))
                         (dotimes (matrix 9 (nreverse result))
                           (let ((matrix (aref *barning-matrixes* matrix)))
                             (push (let ((result 0))
                                     (declare (type fixnum result))
                                     (dotimes (i 3 result)
                                       (incf result
                                             (the fixnum
                                                  (* (the fixnum (aref matrix i))
                                                     (the fixnum (aref n i)))))))
                                   result))))))
                 (declare (type list next-nodes))
                 (loop for i from perimeter to 1500000 by perimeter
                       do (incf (aref *lengths* i)))
                 (dotimes (i 3)
                   (push (make-array 3 :element-type 'fixnum
                                       :initial-contents (list (pop next-nodes)
                                                               (pop next-nodes)
                                                               (pop next-nodes)))
                         list-of-ns))))))
  (values))

在我缓慢的笔记本电脑上，

CL-USER> (load (compile-file #P"e75.lisp"))
; ...compilation notes...
CL-USER> (time (expand-node (make-array 3 :element-type 'fixnum
                                          :initial-contents '(3 4 5))))
Evaluation took:
  0.274 seconds of real time
  0.264000 seconds of total run time (0.264000 user, 0.000000 system)
  96.35% CPU
  382,768,596 processor cycles
  35,413,600 bytes consed

; No values
CL-USER> (count 1 *lengths*)
161667 (18 bits, #x27783)

原始代码使用向量运行大约 1.8 秒，使用列表运行 0.8 秒。

于 2016-07-21T08:34:02.697 回答