1

私のプロジェクトでは、処理する座標がたくさんありますが、2D の状況では、 の構築がや(cons x y)よりも高速であることがわかりました。(list x y)(vector x y)

consただし、のようなものが見つからなかったため、3D またはそれ以上に拡張する方法がわかりませんcons3。tuplecommon-lisp を高速化するための解決策はありますか?

説明のために、次のテストを行いました。

* (time (loop repeat 10000 do (loop repeat 10000 collect (cons (random 10) (random 10)))))

Evaluation took:
  7.729 seconds of real time
  7.576000 seconds of total run time (7.564000 user, 0.012000 system)
  [ Run times consist of 0.068 seconds GC time, and 7.508 seconds non-GC time. ]
  98.02% CPU
  22,671,859,477 processor cycles
  3,200,156,768 bytes consed

NIL
* (time (loop repeat 10000 do (loop repeat 10000 collect (list (random 10) (random 10)))))

Evaluation took:
  8.308 seconds of real time
  8.096000 seconds of total run time (8.048000 user, 0.048000 system)
  [ Run times consist of 0.212 seconds GC time, and 7.884 seconds non-GC time. ]
  97.45% CPU
  24,372,206,280 processor cycles
  4,800,161,712 bytes consed

NIL
* (time (loop repeat 10000 do (loop repeat 10000 collect (vector (random 10) (random 10)))))

Evaluation took:
  8.460 seconds of real time
  8.172000 seconds of total run time (8.096000 user, 0.076000 system)
  [ Run times consist of 0.260 seconds GC time, and 7.912 seconds non-GC time. ]
  96.60% CPU
  24,815,721,033 processor cycles
  4,800,156,944 bytes consed

NIL
4

3 に答える 3

5

このようなデータ構造を処理する一般的な方法は、 を使用することdefstructです。これが、Common Lisp でデータ構造を作成する方法です。したがって、3 次元空間に点が必要な場合は、多かれ少なかれ次のようにします。

(defstruct point-3d x y z)

これが配列よりも優れている理由:

  1. 物事に適切に名前を付けます。

  2. アクセサー、一部のデータがこのタイプであるかどうかをテストする関数、このタイプのオブジェクトを構築する関数、およびその他のグッズなど、とにかく作成する便利なものがたくさん作成されます。

  3. 入力は配列よりも複雑です。各スロットのタイプを個別に指定できます。

  4. データをきれいに印刷できる専用印刷機能。

これがリストよりも優れている理由：

  1. 次のようなことを行うことで、構造体にリストとして動作するようにいつでも要求できます。
(defstruct (point-3d (:type list)) x y z)
  • 配列とすべて同じもの。

最適化の問題:

おそらく、他の選択肢を探る必要があります。同等のメモリ インプリントの配列またはコンス セルを作成することの違いは、最適化する価値がありません。この特定の操作に関連する問題に直面している場合は、一般的にこのタスクを管理できないと考える必要があります。しかし実際には、オブジェクト プーリング、メモ化、一般的なキャッシングなどの手法を最初に試す必要があると思います。

もう 1 つの箇条書き: 効率的なコードを生成するようにコンパイラに指示していません。サイズ、速度、またはデバッグを最適化するようにコンパイラに指示できます。実行しようとしている最適化の種類を指定した後、実際にパフォーマンスを測定する必要があります。

違いを確認するための簡単なテストを作成しました。

(defstruct point-3d
  (x 0 :type fixnum)
  (y 0 :type fixnum)
  (z 0 :type fixnum))

(defun test-struct ()
  (declare (optimize speed))
  (loop :repeat 1000000 :do
     (make-point-3d :x (random 10) :y (random 10) :y (random 10))))

(time (test-struct))

;; Evaluation took:
;;   0.061 seconds of real time
;;   0.060000 seconds of total run time (0.060000 user, 0.000000 system)
;;   98.36% CPU
;;   133,042,429 processor cycles
;;   47,988,448 bytes consed

(defun test-array ()
  (declare (optimize speed))
  (loop :repeat 1000000
     :for point :of-type (simple-array fixnum (3)) :=
     (make-array 3 :element-type 'fixnum) :do
     (setf (aref point 0) (random 10)
           (aref point 1) (random 10)
           (aref point 2) (random 10))))

(time (test-array))

;; Evaluation took:
;;   0.048 seconds of real time
;;   0.047000 seconds of total run time (0.046000 user, 0.001000 system)
;;   97.92% CPU
;;   104,386,166 processor cycles
;;   48,018,992 bytes consed

私のテストの最初のバージョンは、最初のテストの前に GC を実行するのを忘れたため、バイアスがかかっていました。そのため、前のテストの後に残ったメモリを再利用する必要があり、不利になりました。数値がより正確になり、構造体と配列の使用に実質的な違いがないことも示されました。

繰り返しになりますが、以前の提案に従って、オブジェクトのプーリング、メモ化、その他の最適化手法を使用してください。ここでの最適化は行き止まりです。

于 2013-10-20T08:36:39.533 に答える
3

宣言とインライン関数を使用すると、構造体は配列とリストの両方よりも高速になる場合があります。

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

(print "Testing lists");
(terpri)

(time (loop repeat 10000 do
       (loop repeat 10000
        collect (list (random 1000.0)
                      (random 1000.0)
                      (random 1000.0)))))

(print "Testing arrays");
(terpri)

(declaim (inline make-pnt))
(defun make-pnt (&rest coords)
  (make-array 3 :element-type 'single-float :initial-contents coords))

(time (loop repeat 10000 do
       (loop repeat 10000
        collect (make-pnt (random 1000.0)
                          (random 1000.0)
                          (random 1000.0)))))

(print "Testing structs")
(terpri)

(declaim (inline new-point))
(defstruct (point 
         (:type (vector single-float))
         (:constructor new-point (x y z)))
  (x 0.0 :type single-float)
  (y 0.0 :type single-float)
  (z 0.0 :type single-float))

(time (loop repeat 10000 do 
       (loop repeat 10000
          collect (new-point (random 1000.0)
                             (random 1000.0)
                             (random 1000.0)))))


"Testing lists" 
Evaluation took:
  8.940 seconds of real time
  8.924558 seconds of total run time (8.588537 user, 0.336021 system)
  [ Run times consist of 1.109 seconds GC time, and 7.816 seconds non-GC time. ]
  99.83% CPU
  23,841,394,328 processor cycles
  6,400,180,640 bytes consed


"Testing arrays" 
Evaluation took:
  8.154 seconds of real time
  8.140509 seconds of total run time (7.948497 user, 0.192012 system)
  [ Run times consist of 0.724 seconds GC time, and 7.417 seconds non-GC time. ]
  99.84% CPU
  21,743,874,280 processor cycles
  4,800,178,240 bytes consed


"Testing structs" 
Evaluation took:
  7.631 seconds of real time
  7.620476 seconds of total run time (7.432464 user, 0.188012 system)
  [ Run times consist of 0.820 seconds GC time, and 6.801 seconds non-GC time. ]
  99.86% CPU
  20,350,103,048 processor cycles
  4,800,179,360 bytes consed
于 2013-10-20T10:17:10.763 に答える
1

浮動小数点値を扱っていると思いますが、その場合(make-array 3 :element-type 'single-float)が最適かもしれません。このようにして、(ほとんどの実装で) ボックス化されていない状態でフロートが格納されることを期待できます。

をたっぷりとふりかけてください(declare (type (simple-array single-float (3))))。

于 2013-10-20T08:02:13.617 に答える