1

在我的项目中，我有很多坐标要处理，并且在 2D 情况下，我发现 的构造(cons x y)比(list x y)和更快(vector x y)。

但是，我不知道如何扩展cons到 3D 或更远，因为我没有找到类似cons3. 有什么解决方案可以快速tuple使用 common-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 中创建数据结构的方式。所以，如果你想在 3D 空间中有一个点，这或多或少是你会做的：

(defstruct point-3d x y z)

为什么这比数组更好：

  1. 它正确地命名事物。

  2. 它创建了一堆你无论如何都要创建的有用的东西，例如访问器、一个测试某些数据是否属于这种类型的函数、一个构造这种类型的对象的函数以及其他一些好东西。

  3. 键入比在数组中更复杂：您可以分别指定每个插槽的类型。

  4. 专业的打印功能，可以很好地打印您的数据。

为什么这比列出更好：

  1. 您始终可以通过执行以下操作来要求结构表现为列表：
(defstruct (point-3d (:type list)) x y z)
  • 所有与数组相同的东西。

优化问题：

您可能应该尝试探索其他替代方案。创建等效内存印记的数组或 cons 单元之间的区别不值得优化。如果您在执行此特定操作时遇到问题，您应该认为该任务通常难以管理。但实际上，我认为应该首先尝试对象池、记忆和通用缓存等技术。

另一个要点：您没有告诉编译器尝试生成有效的代码。您可以告诉编译器针对大小、速度或调试进行优化。在指定要尝试进行哪种优化后，您应该真正衡量性能。

我写了一个快速测试，看看有什么区别：

(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 回答