Lispのリストとリスト：リストはなぜ以下のコードではるかに高速ですか？

Question

Problem 75 in Project Eulerを解決している間に予期しない結果が発生しました。私のコードは正しい解を見つけることができますが、それは不思議です。

私の解決策は、周囲の限界に達するまでピタゴラスの木（Barning's matrices）をトラバースし、周囲がそれぞれの値を取った回数を数え、そして最後に1回だけ起こった周長を数えます。あるマイ確かにだらしないが、コードを機能：

(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秒かかった - 予想よりも多くの - ではない非常に横断します大木。私はベクトルを削除するためのコードを微調整するとき

しかし、私は...

(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を使用しています。

Answer 1

あなたはあなたが使用していた実装を言っていませんでした。

あなたは時間がどこに費やされているかを知る必要があります。

私の場合は、リストの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が汎用シーケンス操作を使用する場合、リストへの要素アクセスは常にリストをトラバースします。 SBCLが与える上で明らかに...

Answer 2

検査ベクトル＃（1 2 3）1は、すべてのこと速くない最適化されたバージョンを、書くことができますが、Common Lispの実装では、MAPの唯一の一般的な実装を提供することを選択するかもしれません：

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 

Answer 3

Common Lisp最適化の複雑さへようこそ！ 最初に留意すべきことは、さまざまな実装によって実行されるさまざまなプログラム最適化戦略についてです：私はSBCLであなたの例を試してみましたが、どちらも非常に効率的でした。CCLではベクトルバージョンがはるかに遅く実行されましたリストバージョンよりも。試したインプリメンテーションについてはわかりませんが、異なる実装を使用して非常に異なる実行時間を試すことができます。

(map 'vector #'* n x) 

対応するリストのバージョンよりもはるかにゆっくりと実行されます：

(mapcar #'* n x) 

使用CCLでいくつかのテストから

主な問題は、このフォームから生じるように私には思えますtime私はベクトルバージョンが大量に消費することを見ました。

この最初の印象は、mapをmap-intoに変更するだけで、補助ベクトルを使用して確認されています。私は、コードを最適化しようとしたときに

(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

誰もがすでに答えたので、私はあまりにも多くを説明するために悩まずに、ここでこのバージョンを入れます：実際には、次のバージョンでは、リストのバージョンよりも若干速いCCLです。少なくとも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秒で走りました。