Arrays vs. Listen in Lisp: Warum sind Listen im folgenden Code so viel schneller?

Question

Ich habe ein unerwartetes Ergebnis beim Lösen Problem 75 in Project Euler bekommen. Mein Code findet die richtige Lösung, aber es verhält sich merkwürdig.

Meine Lösung besteht darin, einen Pythagoreischen Baum (Barning's matrices) zu durchlaufen, bis das Perimeterlimit erreicht ist, die Anzahl der Male gezählt, die der Umfang jeden Wert angenommen hat, und schließlich die Perimeterlängen, die nur einmal aufgetreten sind. Mein zugegebenermaßen unordentlicher aber funktionierenden Code ist:

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

ich den Baum Expansion erwartete in wenigen Millisekunden laufen, aber die expand-Knotenfunktion nahm 8,65 Sekunden - viel mehr als erwartet - ein nicht sehr zu durchqueren großer Baum.

aber ich war überrascht, als ich den Code, um die Vektoren zu entfernen gezwickt ...

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

... und die Verfahrgeschwindigkeit ging schneller enorm, wobei nur 35 ms. Ich bin fasziniert von diesem gewaltigen Unterschied und hoffe, dass jemand da draußen erklären kann, warum es passiert ist.

Danke, Paulo

PS: Ich verwende CCL für das alles.

Answer 1

Sie haben nicht angegeben, welche Implementierung Sie verwendet haben.

Sie müssten herausfinden, wo die Zeit verbracht wird.

Aber für mich sieht es so aus, als ob die Implementierung von einer Liste und eines Vektors gleicher Länge zu einem neuen Vektor in Ihrem Common Lisp sehr ineffizient sein könnte. Selbst wenn Sie einen neuen Vektor verwenden, der etwas Overhead hat, kann die Implementierung viel schneller sein.

Versuchen Sie, die Vektoroperation als LOOP zu implementieren und vergleichen:

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

Diese schnellere Version conses auch, aber die Liste Operationen mit Vektoroperationen ersetzt:

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

Schauen wir uns an Ihre Code:

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

Sie MAP mit einer Liste So rufen und ein Vektor die meiste Zeit. Wie groß ist der Ergebnisvektor? MAP muss das herausfinden, indem es die Liste durchläuft oder auf andere Weise. Die Länge des Ergebnisvektors ist die kürzeste Länge der Argumentsequenz. Dann muss es über die Liste und den Vektor iterieren. Wenn MAP nun generische Sequenzoperationen verwendet, durchläuft der Elementzugriff auf die Liste immer die Liste. Offensichtlich kann man eine optimierte Version schreiben, die alle tut, die schneller, aber eine Common Lisp Implementierung können wählen, nur eine generische Implementierung von MAP zur Verfügung zu stellen ...

Answer 2

Inspizieren vector # (1 2 3) auf SBCL gibt:

Sie können sehen, dass es etwas mehr Daten zu speichern gibt als in einer Liste, obwohl die genaue interne Darstellung der Vektoren unter den Implementierungen variiert.Für kleine Vektoren, die kopiert werden, wie in Ihrem Beispiel, werden Sie wahrscheinlich mehr Speicher zuweisen als mit Listen, was in den folgenden Zeilen sichtbar ist. Das Zuweisen von Speicher trägt zur Laufzeit bei. Beachten Sie in meinen Tests, dass der Zeitunterschied nicht so groß ist wie in Ihren Tests.

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

Answer 3

Willkommen in den Feinheiten der Common Lisp-Optimierung! Das erste, was zu beachten ist, sind die verschiedenen Programmoptimierungsstrategien, die von den verschiedenen Implementierungen durchgeführt wurden: Ich habe Ihre Beispiele in SBCL ausprobiert, und beide haben sehr effizient mit fast derselben Zeit gearbeitet, während in CCL die Vektorversion viel langsamer ausgeführt wurde als die Listenversion. Ich weiß nicht, welche Implementierung Sie ausprobiert haben, aber Sie können versuchen, verschiedene Implementierungen zu verwenden, um sehr unterschiedliche Ausführungszeiten zu sehen.

Von einigen Tests in CCL scheint es mir, dass das Hauptproblem dieser Form entsteht:

(map 'vector #'* n x) 

die viel viel ausgeführt wird, langsamer als die entsprechende Listenversion:

(mapcar #'* n x) 

Verwendung time Ich habe gesehen, dass die Vektorversion sehr viel kostet.

Dieser erste Eindruck wurde bestätigt, indem einfach map mit map-into unter Verwendung eines Hilfsvektors geändert wurde. Eigentlich ist die folgende Version etwas schneller in CCL als die Liste Version:

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

Answer 4

Jeder bereits beantwortet, während ich den Code zu optimieren versuche, so dass ich nur diese Version hier setzen, ohne zu viel zu erklären, zu belästigen. Es sollte ziemlich schnell laufen, zumindest auf 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)) 

Auf meinem langsamen Laptop,

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) 

Der ursprüngliche Code lief bei etwa ~ 1,8 Sekunden mit Vektoren und 0,8 Sekunden mit Listen.