6

在假期里，我的家人喜欢玩 Boggle。问题是，我在 Boggle 上很糟糕。所以我做了任何优秀程序员都会做的事：写一个程序来为我玩。

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

这是trie:add实现：

添加（[]，特里）->
    dict:store(stop, true, Trie);

添加（[Ch|Rest]，特里）->
    % setdefault（键，默认值，字典）->
    % case dict:find(Key, Dict) of
    % { ok, Val } -> { 字典, Val }
    % 错误 -> { dict:new(), Default }
    ％ 结尾。
    { NewTrie, SubTrie } = setdefault(Ch, dict:new(), Trie),
    NewSubTrie = add(Rest, SubTrie),
    字典：商店（Ch，NewSubTrie，NewTrie）。

您可以在此处查看其余部分以及如何使用它的示例（在底部）：

http://gist.github.com/263513

现在，这是我在 Erlang 中的第一个严肃程序，我知道它可能有很多问题……但我最关心的是它使用了800 MB 的 RAM。

那么，我做错了什么？我怎样才能让它少一点错误呢？

4

6 回答 6

4

您可以通过简单地将单词存储在 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 是必须的，但您可以使用非功能性方法，那么您可以尝试digraph s，正如 Paul 已经建议的那样。

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

于 2009-12-26T20:23:36.337 回答
4

我不记得 dict 需要多少内存，但让我们估计一下。你有 2.5e6 个字符和 2e5 个单词。如果您的 trie 根本没有共享，那将在 dicts 中使用 2.7e6 关联（每个字符和每个“停止”符号一个）。一个简单的纯功能 dict 表示每个关联可能有 4 个单词——它可能会更少，但我试图获得一个上限。在 64 位机器上，这需要 8*4*270 万字节，即 86 兆字节。这只是你的 800M 的十分之一，所以这里肯定有问题。

更新： dict.erl表示带有哈希表的字典；当你有很多非常小的字典时，这意味着很多开销，就像你一样。我会尝试更改您的代码以使用proplists模块，它应该与我上面的计算相匹配。

于 2009-12-26T21:22:56.483 回答
2

查看DAWG。它们比尝试紧凑得多。

于 2011-01-04T01:15:14.207 回答
2

解决问题的另一种方法是查看单词列表，看看是否可以从骰子中构造单词。这样你只需要很少的 RAM，而且编码可能会更有趣。（优化和并发）

于 2009-12-29T02:34:28.767 回答
1

如果所有单词都是英文，大小写无关紧要，所有字符都可以用 1 到 26 的数字编码（实际上，在 Erlang 中它们是97 到 122 的数字），保留 0 表示停止。因此，您也可以使用该array模块。

于 2009-12-26T23:04:47.450 回答
1

我不知道你的算法，但如果你要存储那么多数据，也许你应该考虑使用 Erlang 的内置 digraph 库来表示你的 trie，而不是这么多的字典。 http://www.erlang.org/doc/man/digraph.html

于 2009-12-26T18:56:03.067 回答