All geek questions in one place

Arrays versus Lists in Lisp: Why Lists in a List Below?

I got an unexpected result while solving Problem 75 in Project Euler . My code really finds the right solution, but it behaves strangely.

My solution is to move the Pythagorean tree ( Barning matrices ) to reach the perimeter limit, counting the number of times that the perimeter value each time assumed and finally counting the perimeter durations that occurred only once. My admittedly untidy but valid 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*)

I expected the tree extension to start in a few milliseconds, but the expand-node function took 8.65 seconds — much more than expected — to traverse a not-so-large tree.

, , ...

(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

, .

, .

MAP , 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...

+3

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))))))
+3

# (1 2 3) SBCL :

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

, , , . , , , , , , , . . , , .

;; 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
+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)

The source code ran in approximately ~ 1.8 seconds with vectors and 0.8 seconds with lists.

+2
source

Source: https://habr.com/ru/post/1648584/

More articles:


All Articles