2012-11-29 78 views
2

我是一個lisp初學者,我正在嘗試編寫一個爲trie定義類併爲其讀取整個拼字遊戲字典的包。該結構充當節點,每個節點都有一個關聯列表,用於跟蹤源自它的字母(通向其他子集)。在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節點成爲一個結構而不是一個類,並得到了類似的結果。我也有一個遞歸算法來添加字典中的單詞,但它同樣糟糕。

我一直在爲此而努力了幾個小時,我有點沮喪......

+0

我試着首先用哈希表實現......我認爲a-lists會更有效率。這個實現的要點是,一個單詞中的每個字母都應該位於一個單獨的子樹中,如果該字母的子分支不存在,則只創建一個新的子樹。有關終止於某些子項的單詞的信息以及子單元下存在多少單詞也是目標的一部分(因此,爲什麼我想通過關聯n-trie實例的關聯列表來跟蹤此信息。) 我同意它不似乎是最有效的方式來存儲信息... –

+0

也(next-letters tri)只是訪問n-trie類的(下一個字母)屬性...所以這不應該是那麼大的一個內存問題 –

+0

你的哈希表中每個鍵的值是多少?它是否是另一個節點?你如何遍歷這棵樹? –

回答

0

我會改變的第一件事是函數read-words。它使用尾遞歸,看起來像Scheme中的。這在Common Lisp中不是慣用的。使用WITH-OPEN-FILE打開一個文件並使用循環結構來讀取這些行。如果Common Lisp系統不優化尾遞歸,則此遞歸已在大型文本文件上創建堆棧溢出。

所以:

  • 不使用尾遞歸,在這裏沒有必要的,在那裏,你知道你的CL實現實際上支持它,理解它。例如,高調試模式通常會阻止尾遞歸優化。

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

  • 使用IF代替COND - 尤其是當我們處理一個正常的真/假謂詞。

+0

謝謝,我會給你一個鏡頭並回報。只是出於好奇...我一直認爲使用cond在CL中比在使用if ... –

+0

好,這似乎工作得很好。謝謝。 它仍然無法加載我的完整字典...我遇到了我的allegro cl免費版的堆限制。 關於解決方案的任何建議? –