优化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))))

每当我试图加载整个字典时，都会出现堆栈溢出。拼字词典里有超过10万个单词，但它在6000个单词时失败了……我的记忆力出了问题，但我似乎不知道是什么。

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

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

Answer 1

我要更改的第一件事是函数read-words。它使用尾部递归，看起来像Scheme。这在普通Lisp中不地道。使用WITH-OPEN-FILE打开文件，并使用循环构造读取行。如果Common Lisp系统没有优化尾部递归，那么这种递归已经在大型文本文件上造成堆栈溢出。

因此：

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

• 使用CCD_ 3。不要使用OPEN/CLOSE。

• 使用IF而不是COND——尤其是当我们处理正常的真/假谓词时。