2

私はLispの初心者で、トライのクラスを定義し、スクラブル辞書全体を読み込むパッケージを作成しようとしています。構造体はノードとして機能します。各ノードには、それから派生した（他のサブトリーにつながる）文字を追跡する関連付けリストがあります。

これがクラスの私のコードです

(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語で失敗しています...メモリ使用量に問題がありますが、何がわからないようです。

これらの定義で私が行っていることで、メモリに関して本質的に高価なものはありますか？トライノードをクラスではなく構造体にしてみたところ、同様の結果が得られました。辞書から単語を追加するための再帰的アルゴリズムもありましたが、それも同様に悪かったです。

私はこれに何時間も苦労してきました、そして私は少しイライラしています...

4

1 に答える 1

1

最初に変更するのは関数read-wordsです。末尾再帰を使用し、Schemeのように見えます。これはCommonLispでは慣用的ではありません。を使用WITH-OPEN-FILEしてファイルを開き、ループ構造を使用して行を読み取ります。Common Lispシステムが末尾再帰を最適化しない場合、この再帰はすでに大きなテキストファイルにスタックオーバーフローを引き起こします。

それで：

  • 必要がなく、CL実装が実際に末尾再帰をサポートし、理解していることがわかっている場合は、末尾再帰を使用しないでください。たとえば、通常の高デバッグモードでは、末尾再帰の最適化が妨げられます。

  • を使用しますWITH-OPEN-FILE。OPEN/は使用しないでくださいCLOSE。

  • 特に通常のtrue/false述語を扱う場合は-IFの代わりに使用します。COND

于 2012-11-29T19:40:23.017 に答える