这段矩阵加法代码中数据结构的选择有什么根本错误？

Question

第 2.2.4 节 here 包含以下内容：

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.

显然，作者认为这段代码中使用的数据结构存在根本性错误。在技术层面上，哪里出了问题？我担心这个问题可能是基于观点的，但作者的措辞表明有一个客观正确且非常明显的答案。

Answer 1

Lisp 列表是 singly-linked。随机访问一个元素（通过 nth）需要遍历所有前导。出于此目的，存储同样是浪费的。以这种方式处理矩阵非常低效。

Lisp 有 built-in 多维数组，因此自然适合这个问题的是 two-dimensional 数组，它可以直接访问元素而不是遍历链接。

Answer 2

在数字代码中有一个强有力的假设，即访问矩阵元素，或更一般地数组，大约是 constant-time。 a[n, m] 所花费的时间不应取决于 n 和 m。在这种情况下，这是完全不正确的，因为，给定 matrix-ref:

的明显定义

(defun matrix-ref (matrix n m)
  (nth m (nth n matrix)))

然后，由于 nth 花费的时间与其第一个参数成正比（更一般地说：访问 Lisp 列表的第 n 个元素花费的时间与 n+1 成正比，从零开始计数），那么matrix-ref 与两个指数之和成正比（或者实际上与两个指数之和（指数 + 1）成正比，但这并不重要。）。

这意味着，例如，几乎所有涉及矩阵的算法都会提高时间复杂度类。太糟糕了。

Answer 3

如上所述，列表类型的矩阵对于产品来说速度很慢。但是，这对教学有好处，您可以构建矩阵库，只需很少的 lisp 知识并且错误更少。我在阅读《神经网络设计》时构建了这样一个基本的矩阵库，请参阅github中的代码：https://github.com/hxzrx/nnd/blob/master/linear-algebra.lisp。

这段矩阵加法代码中数据结构的选择有什么根本错误？

What is fundamentally wrong in the choice of data structure in this matrix addition code?

performance

common-lisp

matrix