此處第 2.2.4 節包含以下內容：
2.2.4 完全不合適的資料結構
有些人可能會覺得這個例子很難相信。這確實發生在我見過的一些代碼中：
(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)))))))))更糟糕的是，在特定的應用程式中，矩陣都是固定大小的，在 Lisp 中的矩陣運算與在 FORTRAN 中一樣快。
這個例子非常悲哀：代碼非常漂亮，但是添加矩陣的速度很慢。因此它是優秀的原型代碼和糟糕的生產代碼。你知道，你不能用 C 寫出這么糟糕的生產代碼。
顯然，作者認為這段代碼中使用的資料結構存在根本問題。在技??術層面上，出了什么問題？我擔心這個問題可能是基于意見的，但作者的措辭表明存在一個客觀正確且非常明顯的答案。
uj5u.com熱心網友回復：
Lisp 串列是單鏈接的。隨機訪問一個元素（通過第 n 個）需要遍歷所有的前任。為此目的，存盤同樣是浪費的。以這種方式處理矩陣是非常低效的。
Lisp 有內置的多維陣列，所以很自然地適合這個問題的是二維陣列，它可以直接訪問元素而不是遍歷鏈接。
uj5u.com熱心網友回復：
數字代碼中有一個強有力的假設，即訪問矩陣元素或更一般地陣列元素大約是恒定時間。所花費的時間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），但這并不重要。）。
這意味著，例如，幾乎所有涉及矩陣的演算法都會提升時間復雜度等級。那很糟。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/456736.html