此处第 2.2.4 节包含以下内容：
2.2.4 完全不合适的数据结构
有些人可能会觉得这个例子难以置信。这确实发生在我见过的一些代码中：
(defun make-matrix (nm))
（让（（矩阵（）））
（dotimes（在矩阵中）
(推(make-list m)矩阵))))
(defun 加法矩阵 (m1 m2)
（让（（l1（长度m1））
(l2 (长度 m2)))
(let ((矩阵 (make-matrix l1 l2)))
（dotimes（i l1 矩阵）
（dotimes（j l2）
(setf(第n个i(第n个j矩阵))
(+(第n个i(第n个jm1))
(第n个i(第n个jm2))))))))
更糟糕的是，在特定的应用程序中，矩阵都是固定大小的，矩阵运算在 Lisp 中和在 FORTRAN 中一样快。
这个例子非常悲伤：代码绝对漂亮，但它添加矩阵的速度很慢。因此，它是优秀的原型代码和糟糕的生产代码。您知道，您无法用 C 语言编写如此糟糕的生产代码。
显然，作者认为此代码中使用的数据结构存在根本性错误。从技术层面来说，到底出了什么问题？我担心这个问题可能是基于观点的，但作者的措辞表明有一个客观正确且非常明显的答案。
Section 2.2.4 here contains the following:
2.2.4 Totally Inappropriate Data Structures
Some might find this example hard to believe. This really occurred in some code I’ve seen:
(defun make-matrix (n m)
(let ((matrix ()))
(dotimes (i n matrix)
(push (make-list m) matrix))))
(defun add-matrix (m1 m2)
(let ((l1 (length m1))
(l2 (length m2)))
(let ((matrix (make-matrix l1 l2)))
(dotimes (i l1 matrix)
(dotimes (j l2)
(setf (nth i (nth j matrix))
(+ (nth i (nth j m1))
(nth i (nth j m2)))))))))
What’s worse is that in the particular application, the matrices were all fixed size, and matrix arithmetic would have been just as fast in Lisp as in FORTRAN.
This example is bitterly sad: The code is absolutely beautiful, but it adds matrices slowly. Therefore it is excellent prototype code and lousy production code. You know, you cannot write production code as bad as this in C.
Clearly, the author thinks that something is fundamentally wrong with the data structures used in this code. On a technical level, what has went wrong? I worry that this question might be opinion-based, but the author's phrasing suggests that there is an objectively correct and very obvious answer.
发布评论
评论（3）
LISP列表单独链接。随机访问元素（通过nth）需要遍历所有前辈。为此，存储同样浪费了。以这种方式使用矩阵非常效率低下。
LISP具有内置的多维阵列，因此对于此问题的自然拟合将是一个二维阵列，该数组可以直接访问元素而不是穿越链接。
Lisp lists are singly-linked. Random access to an element (via nth) requires traversing all predecessors. The storage is likewise wasteful for this purpose. Working with matrices this way is very inefficient.
Lisp has built-in multidimensional arrays, so a natural fit for this problem would be a two-dimensional array, which can access elements directly instead of traversing links.
数值代码中有一个很强的假设，即访问矩阵元素或更一般的数组元素大约是恒定的。
a [n，m]花费的时间不应取决于n和m。在这种情况下，这是无可接道的，因为，鉴于matrix-ref的明显定义：然后，由于
nth将时间与其第一个参数成正比（更一般而言）（更一般而言） LISP列表的元素需要与n+1成正比的时间，从零计数），然后m artrix-ref所花费的时间与两个索引的总和成比例（或实际上是两个（指数 + 1），但这没关系。）。这意味着，例如，几乎所有涉及矩阵的算法都将移动时间复杂性类。那很糟糕。
There's a strong assumption in numerical code that access to elements of matrices, or more generally arrays, is approximately constant-time. The time taken for
a[n, m]should not depend onnandm. That's hopelessly untrue in this case, since, given the obvious definition ofmatrix-ref:then, since
nthtakes time proportional to its first argument (more generally: accessing the nth element of a Lisp list takes time proportional to n+1, counting from zero), then the time taken bymatrix-refis proportional to the sum of the two indices (or in fact to the sum of the two (indices + 1) but this does not matter.).This means that, for instance, almost any algorithms involving matrices will move up time complexity classes. That's bad.
如上所述，列表类型的矩阵对于产品来说速度很慢。然而，它对教学很有好处，你可以用很少的 lisp 知识构建一个矩阵库，并且 bug 更少。当我阅读《神经网络设计》时，我已经构建了这样一个基本的矩阵库，请参阅github中的这段代码： https://github.com/hxzrx/nnd/blob/master/linear-algebra.lisp。
List type of matrix is slow for products as descripted above. However, it's good for teaching, you can build a matrix library with very little knowledge of lisp and with less bugs. I've build such a basic matrix library when I read "Neural Network Design", see this code in github: https://github.com/hxzrx/nnd/blob/master/linear-algebra.lisp.