Tableaux comparés aux listes en Lisp: Pourquoi les listes sont-elles tellement plus rapides dans le code ci-dessous?

Question

J'ai obtenu un résultat inattendu en résolvant Problem 75 in Project Euler. Mon code trouve la bonne solution, mais il se comporte bizarrement. Ma solution consiste à traverser un arbre de Pythagore (Barning's matrices) jusqu'à ce que la limite de périmètre soit atteinte, en comptant le nombre de fois que le périmètre a pris chaque valeur, et, enfin, en comptant les longueurs de périmètre qui se sont produites une seule fois. Mon certes, mais le code désordre fonctionnel est:

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

Je me attendais à l'expansion de l'arbre pour exécuter en quelques millisecondes, mais la fonction nœud expansion a pris 8,65 secondes - beaucoup plus que prévu - à traverser un peu grand arbre.

Cependant, j'ai été surpris quand je peaufiné le code pour supprimer les vecteurs ...

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

... et le déplacement allé extrêmement vite, en prenant seulement 35 ms. Je suis intrigué par cette énorme différence et j'espère que quelqu'un là-bas pourra expliquer pourquoi c'est arrivé.

Merci, Paulo

PS: J'utilise le CCA pour tout cela.

Answer 1

Vous n'avez pas indiqué quelle implémentation vous utilisiez.

Vous auriez besoin de savoir où est le temps passé.

Mais pour moi, il semble que la mise en œuvre de MAP d'une liste et un vecteur de longueur égale à un nouveau vecteur dans votre Common Lisp pourrait être très inefficace. Même en présence d'un nouveau vecteur, qui a un peu de surcharge, l'implémentation peut être beaucoup plus rapide.

Essayez de mettre en œuvre l'opération vectorielle en boucle et comparer:

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

Cette version plus rapide conses aussi, mais a remplacé les opérations de la liste des opérations vectorielles:

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

Regardons votre 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)))))) 

Alors vous appelez MAP avec une liste et un vecteur la plupart du temps. Quelle est la taille du vecteur de résultat? MAP doit le découvrir en parcourant la liste ou d'une autre manière. La longueur du vecteur résultat est la plus courte des longueurs de séquence d'arguments. Ensuite, il doit parcourir la liste et le vecteur. Si MAP utilise maintenant des opérations de séquence générique, l'accès à l'élément dans la liste traverse toujours la liste. Évidemment on peut écrire une version optimisée, qui fait tout cela plus vite, mais une implémentation Common Lisp pourrait choisir de ne fournir qu'une implémentation générique de MAP ...

Answer 2

Inspecter le vecteur # (1 2 3) sur SBCL donne:

Vous pouvez voir qu'il y a un peu plus de données à stocker que dans une liste, même si la représentation interne exacte des vecteurs varie parmi les implémentations.Pour les petits vecteurs qui continuent à être copiés comme dans votre exemple, vous finirez probablement par allouer plus de mémoire qu'avec des listes, ce qui est visible dans les lignes octets ci-dessous. L'allocation de mémoire contribue à l'exécution. Dans mes tests, notez que la différence de temps n'est pas aussi grande que dans vos 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

Bienvenue dans les subtilités de l'optimisation Common Lisp! La première chose à noter concerne les différentes stratégies d'optimisation de programme exécutées par les différentes implémentations: J'ai essayé vos exemples en SBCL, et les deux ont fonctionné très efficacement avec presque le même temps, tandis que dans CCL la version vectorielle était beaucoup plus lente que la version de la liste. Je ne sais pas quelle implémentation vous avez essayée, mais vous pouvez essayer d'utiliser différentes implémentations pour voir des temps d'exécution très différents.

quelques tests effectués dans le CCA, il me semble que le principal problème provient de ce formulaire:

(map 'vector #'* n x) 

qui est exécuté beaucoup plus lentement que la version de la liste correspondante:

(mapcar #'* n x) 

aide time J'ai vu que la version vectorisée console beaucoup.

Cette première impression a été confirmée en changeant simplement map avec map-into, en utilisant un vecteur auxiliaire. En fait, la version suivante est légèrement plus rapide dans le CCA que la version de la liste:

(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

Tout le monde a déjà répondu alors que je tentais d'optimiser le code, donc je vais juste mettre cette version ici sans prendre la peine d'expliquer trop. Il devrait fonctionner assez rapidement, au moins sur 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)) 

Sur mon ordinateur portable lent,

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) 

Le code d'origine ont fonctionné à environ ~ 1,8 seconde avec des vecteurs, et 0,8 secondes avec des listes.