Erlang:这个trie实现最糟糕的是什么？

Question

在假期,我的家人喜欢玩Boggle.问题是,我在Boggle很糟糕.所以我做了任何优秀的程序员会做的事情:写了一个程序给我玩.

该算法的核心是一个简单的前缀trie,其中每个节点都是dict对下一个字母的引用.

这是trie:add实施:

add([], Trie) ->
    dict:store(stop, true, Trie);

add([Ch|Rest], Trie) ->
    % setdefault(Key, Default, Dict) ->
    %     case dict:find(Key, Dict) of
    %         { ok, Val } -> { Dict, Val }
    %         error -> { dict:new(), Default }
    %     end.
    { NewTrie, SubTrie } = setdefault(Ch, dict:new(), Trie),
    NewSubTrie = add(Rest, SubTrie),
    dict:store(Ch, NewSubTrie, NewTrie).

你可以看到其余的,以及它如何使用的例子(在底部),这里:

http://gist.github.com/263513

现在,这是我在Erlang中的第一个认真的程序,我知道它可能有一些问题......但我最关心的是它使用800兆字节的RAM.

那么,我做错了什么？我怎么能把它弄错呢？

Answer 1

您可以通过简单地将单词存储在 ets 表中来实现此功能：

% create table; add words
> ets:new(words, [named_table, set]).
> ets:insert(words, [{"zed"}]).  
> ets:insert(words, [{"zebra"}]).    

% check if word exists
> ets:lookup(words, "zed").          
[{"zed"}]

% check if "ze" has a continuation among the words
78> ets:match(words, {"ze" ++ '$1'}).
[["d"],["bra"]]

如果 trie 是必须的，但您可以接受非功能性方法，那么您可以尝试有向图，正如 Paul 已经建议的那样。

如果您想保持功能正常，您可以通过使用使用较少内存的结构来节省一些字节的内存，例如proplist或记录，例如-record(node, {a,b,....,x,y,z}).