我是一個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節點成爲一個結構而不是一個類,並得到了類似的結果。我也有一個遞歸算法來添加字典中的單詞,但它同樣糟糕。
我一直在爲此而努力了幾個小時,我有點沮喪......
我試着首先用哈希表實現......我認爲a-lists會更有效率。這個實現的要點是,一個單詞中的每個字母都應該位於一個單獨的子樹中,如果該字母的子分支不存在,則只創建一個新的子樹。有關終止於某些子項的單詞的信息以及子單元下存在多少單詞也是目標的一部分(因此,爲什麼我想通過關聯n-trie實例的關聯列表來跟蹤此信息。) 我同意它不似乎是最有效的方式來存儲信息... –
也(next-letters tri)只是訪問n-trie類的(下一個字母)屬性...所以這不應該是那麼大的一個內存問題 –
你的哈希表中每個鍵的值是多少?它是否是另一個節點?你如何遍歷這棵樹? –