在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)))) 

每当我尝试加载整个词典时，就会发生堆栈溢出。拼字游戏字典中有超过10万字，并且在6000处失败......我的内存使用情况出了问题，但我似乎无法说出什么。

在这些定义中是否存在某些内在价值昂贵的记忆方法？我试图让trie节点成为一个结构而不是一个类，并得到了类似的结果。我也有一个递归算法来添加字典中的单词，但它同样糟糕。

我一直在为此而努力了几个小时，我有点沮丧......

Answer 1

我会改变的第一件事是函数read-words。它使用尾递归，看起来像Scheme中的。这在Common Lisp中不是惯用的。使用WITH-OPEN-FILE打开一个文件并使用循环结构来读取这些行。如果Common Lisp系统不优化尾递归，则此递归已在大型文本文件上创建堆栈溢出。

所以：

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

• 使用WITH-OPEN-FILE。请勿使用OPEN/CLOSE。

• 使用IF代替COND - 尤其是当我们处理一个正常的真/假谓词。