2

我是一个 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 节点成为结构而不是类，并得到了类似的结果。我也有一个从字典中添加单词的递归算法，但它同样糟糕。

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

4

1 回答 1

1

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

所以：

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

  • 使用WITH-OPEN-FILE. 不要使用OPEN/ CLOSE。

  • 使用IF代替COND- 特别是当我们处理正常的真/假谓词时。

于 2012-11-29T19:40:23.017 回答