Erlang: Was ist am meisten falsch mit dieser Trie-Implementierung?

Question

In den Ferien spielt meine Familie gerne Boggle. Das Problem ist, ich bin schrecklich in Boggle. Also tat ich, was jeder gute Programmierer tun würde: Er schrieb ein Programm, um für mich zu spielen.

Im Kern des Algorithmus ist eine einfache prefix trie, wo jeder Knoten ist ein dict der Verweise auf die nächsten Buchstaben.

Dies ist die trie:add Umsetzung:

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).

Und Sie den Rest sehen, zusammen mit einem Beispiel dafür, wie es (unten) verwendet wird, hier:

http://gist.github.com/263513

Nun, dies ist mein erstes ernstes Programm in Erlang, ich weiß, dass es wahrscheinlich eine Menge Dinge nicht stimmt ... Aber mein sofort Die Sorge ist, dass es 800 Megabyte RAM verwendet.

Also, was mache ich am meisten falsch? Und wie könnte ich es etwas weniger falsch machen?

Answer 1

Sie diese Funktionalität durch einfaches Speichern der Wörter in einem ets Tabelle implementieren könnte:

% 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"]] 

Wenn Trie ist ein Muss, aber man kann leben mit einem nicht-funktionalen Ansatz, dann können Sie digraph versuchen s, wie Paul schon angedeutet hat.

Wenn Sie funktionsfähig bleiben möchten, können Sie einige Speicherbytes speichern, indem Sie Strukturen mit weniger Speicher verwenden, z. B. proplist s oder Datensätze wie -record(node, {a,b,....,x,y,z}).

Answer 2

Ich weiß nicht, über Ihren Algorithmus, aber wenn Sie so viele Daten speichern, sollten Sie vielleicht mit der eingebauten Digraph-Bibliothek von Erlang, um Ihren Trie, anstelle von so vielen Diktaten zu vertreten. http://www.erlang.org/doc/man/digraph.html

Answer 3

Ich erinnere mich nicht, wie viel Speicher ein Diktat dauert, aber lassen Sie uns schätzen. Sie haben 2.5e6 Zeichen und 2e5 Wörter. Wenn Ihr Trie überhaupt keine Freigabe hatte, würde das 2,7e6 Assoziationen in den Dicts benötigen (eine für jedes Zeichen und jedes Stop-Symbol). Eine einfache rein funktionale Diktatdarstellung würde vielleicht 4 Wörter pro Assoziation - es könnte weniger sein, aber ich versuche, eine obere Grenze zu bekommen. Auf einem 64-Bit-Rechner würde das 8 * 4 * 2,7 Millionen Byte oder 86 Megabyte benötigen. Das ist nur ein Zehntel Ihrer 800M, also stimmt hier etwas nicht.

Update:dict.erl repräsentiert dicts mit einer Hashtabelle; Das bedeutet viel Overhead, wenn Sie viele sehr kleine dicts haben, wie Sie es tun. Ich würde versuchen, Ihren Code zu ändern, um das proplists Modul zu verwenden, das meinen Berechnungen oben entsprechen sollte.

Answer 4

Wenn alle Wörter in Englisch sind und der Fall keine Rolle spielt, können alle Zeichen mit Zahlen von 1 bis 26 codiert werden (und in Erlang sind sie sind Zahlen von 97 bis 122), 0 reservieren für Halt. So können Sie auch die array module verwenden.

Answer 5

Eine alternative Möglichkeit, das Problem zu lösen, besteht darin, die Wortliste durchzugehen und zu sehen, ob das Wort aus den Würfeln konstruiert werden kann. Auf diese Weise benötigen Sie sehr wenig RAM und es macht mehr Spaß zu programmieren.(Optimierung und Nebenläufigkeit)

Answer 6

Blick in DAWG s. Sie sind viel kompakter als Versuche.