6

休暇中、私の家族はボグルをプレイするのが大好きです。問題は、私はボグルでひどいです。それで、私はどんな優れたプログラマーでもすることをしました：私のために遊ぶためのプログラムを書きました。

アルゴリズムの中核となるのは単純な接頭辞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}
    ％エラー-> {dict：new（）、デフォルト}
    ％ 終わり。
    {NewTrie、SubTrie} = setdefault（Ch、dict：new（）、Trie）、
    NewSubTrie = add（Rest、SubTrie）、
    dict：store（Ch、NewSubTrie、NewTrie）。

そして、残りの部分と、それがどのように使用されているかの例（下部）をここで見ることができます：

http://gist.github.com/263513

さて、これはErlangでの私の最初の本格的なプログラムであり、おそらくそれには多くの問題があることを知っています…しかし、私の当面の懸念は、800メガバイトのRAMを使用することです。

だから、私は何をしているのですか-間違っていますか？そして、どうすればそれを少し間違えないようにすることができますか？

4

6 に答える 6

4

dictがどれだけのメモリを必要とするかは覚えていませんが、見積もりましょう。あなたは2.5e6の文字と2e5の単語を持っています。トライに共有がまったくない場合は、dictで2.7e6の関連付けが必要になります（各文字と「停止」記号ごとに1つ）。単純な純粋関数型のdict表現は、関連付けごとに4語になる可能性があります。これより少ない場合もありますが、上限を取得しようとしています。64ビットマシンでは、8 * 4 * 270万バイト、つまり86メガバイトかかります。それはあなたの800Mの10分の1に過ぎないので、ここで何かが間違いなく間違っています。

更新： dict.erlはハッシュテーブルでdictを表します。これは、あなたがそうするように、非常に小さなdictがたくさんある場合、多くのオーバーヘッドを意味します。上記の計算と一致するはずのproplistsモジュールを使用するようにコードを変更してみます。

于 2009-12-26T21:22:56.483 に答える
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"]]

トライが必須であるが、機能しないアプローチで生きることができる場合は、ポールがすでに示唆しているように、有向グラフを試すことができます。

機能を維持したい場合は、proplistなどのメモリ使用量の少ない構造体や、などのレコードを使用して、メモリを数バイト節約できます-record(node, {a,b,....,x,y,z})。

于 2009-12-26T20:23:36.337 に答える
2

問題を解決する別の方法は、単語リストを調べて、サイコロから単語を作成できるかどうかを確認することです。そうすれば、必要なRAMはごくわずかであり、コーディングする方が楽しいかもしれません。（最適化と並行性）

于 2009-12-29T02:34:28.767 に答える
2

DAWGを調べます。それらは、試行よりもはるかにコンパクトです。

于 2011-01-04T01:15:14.207 に答える
1

アルゴリズムについてはわかりませんが、大量のデータを保存している場合は、多くのdictではなく、Erlangの組み込みの有向グラフラ​​イブラリを使用してトライを表すことを検討する必要があります。 http://www.erlang.org/doc/man/digraph.html

于 2009-12-26T18:56:03.067 に答える
1

すべての単語が英語であり、大文字と小文字が区別されない場合、すべての文字を1から26までの数字でエンコードでき（実際、Erlangでは97から122までの数字です）、停止用に0を予約します。したがって、arrayモジュールも使用できます。

于 2009-12-26T23:04:47.450 に答える