LISP-TRIE数据结构中函数（内存）的优化

Question

我是一个lisp初学者，我试图编写一个包，为trie定义一个类，并在其中读取拼字词典的全部内容。该结构充当一个节点，每个节点都有一个关联列表，该列表跟踪来自它的字母（导致其他子区）。

下面是我的类代码

(DEFCLASS n-trie ()
  ((word :accessor word
         :initform 'nil
         :initarg :word)
   (word-count :accessor wcount
               :initform 0
               :initarg :wcount)
   (next-letters :accessor next-letters
                 :initform 'nil
                 :initarg :next-letters)))

这是我的添加单词函数

(defun add-word (string trie) ;;iterative method for looping through string
  (let ((s (coerce string 'list))
        (tri trie))
    (dolist (item s)
      (cond
       ((assoc item (next-letters tri))
        (incf (wcount tri))
        (setf tri (cdr (assoc item (next-letters tri)))))
       (t
        (incf (wcount tri))
        (setf (next-letters tri) (acons item (make-instance 'n-trie) (next-letters tri)))
        (setf tri (cdr (assoc item (next-letters tri)))))))
    (setf (word tri) string)))

下面是打开我的文件（拼字字典）并读取每一行的函数

(defun read-words (file trie)
  (let((str (open file)))
    (labels ((rec (tri)
                  (let ((line (read-line str nil nil)))
                    (cond 
                     (line (add-word line tri)
                           (rec tri))
                     (t (close str)
                        trie)))))
      (rec trie))))

每当我试图加载整个字典时，都会出现堆栈溢出。拼字字典里有100k多个单词，但它在6000个时失败了……我的记忆使用情况出了问题，但我似乎不知道是什么。

我在这些定义中所做的事情是不是固有的内存开销？我尝试将trie节点作为一个结构而不是一个类，得到了类似的结果。我也有一个递归算法来从字典中添加一个单词，但它同样糟糕。

我已经为此挣扎了几个小时，我有点沮丧...

Answer 1

我首先要更改的是函数read-words。它使用尾部递归，看起来像在Scheme中。这在普通的Lisp中是不地道的。使用with-open-file打开文件并使用循环构造读取行。如果公共Lisp系统没有优化尾递归，则此递归已经在大型文本文件上造成堆栈溢出。

所以：

>

不要在不必要的地方使用尾递归，并且您知道您的CL实现实际上支持并理解它。例如，高调试模式通常会阻止尾递归优化。

使用with-open-file。不要使用打开/关闭。

使用if而不是cond-尤其是在处理正常的true/false谓词时。