Erlang: ¿Qué hay de malo en esta implementación?

Question

Durante las vacaciones, a mi familia le encanta jugar Boggle. El problema es que soy terrible en Boggle. Así que hice lo que cualquier buen programador haría: escribió un programa para tocar para mí.

En el núcleo del algoritmo es un simple prefix trie, donde cada nodo es un dict de referencias a las siguientes letras.

Este es el trie:add aplicación:

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

Y se puede ver el resto, junto con un ejemplo de cómo se utiliza (en el fondo), aquí:

http://gist.github.com/263513

Ahora que este es mi primer programa serio en Erlang, sé que probablemente hay un montón de cosas mal con eso ... Pero mi immediat La preocupación es que usa 800 megabytes de RAM.

Entonces, ¿qué estoy haciendo más mal? ¿Y cómo podría hacerlo un poco menos mal?

Answer 1

Se podría implementar esta funcionalidad simplemente almacenar las palabras en una tabla de 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"]] 

Si trie es una necesidad, pero se puede vivir con un enfoque no-funcional, entonces usted puede intentar digraph s, como Paul ya sugirió.

Si desea permanecer funcional, puede guardar algunos bytes de memoria mediante el uso de estructuras con menos memoria, por ejemplo proplist s, o registros, como -record(node, {a,b,....,x,y,z}).

Answer 2

No sé tu algoritmo, pero si estás almacenando esa cantidad de datos, tal vez deberías considerar el uso de la biblioteca de digrafos incorporada de Erlang para representar tu trie, en lugar de tantos dicts. http://www.erlang.org/doc/man/digraph.html

Answer 3

No recuerdo cuánta memoria toma un dict, pero estimémoslo. Tienes 2.5e6 caracteres y 2e5 palabras. Si tu trie no compartía nada, eso tomaría 2.7e6 asociaciones en los dicts (una para cada personaje y cada símbolo de 'stop'). Una simple representación dict puramente funcional sería de 4 palabras por asociación, podría ser menos, pero estoy tratando de obtener un límite superior. En una máquina de 64 bits, eso tomaría 8 * 4 * 2.7 millones de bytes, o 86 megabytes. Eso es solo una décima parte de tus 800M, entonces algo seguramente está mal aquí.

Actualización:dict.erl representa los dictados con una tabla hash; esto implica mucha sobrecarga cuando tienes muchos dicts muy pequeños, como lo haces. Intentaría cambiar tu código para usar el módulo proplists, que debería coincidir con mis cálculos anteriores.

Answer 4

Si todas las palabras están en inglés, y el caso no importa, todos los caracteres pueden codificarse con números del 1 al 26 (y de hecho, en Erlang son son números del 97 al 122), reservando 0 para parar. Para que pueda usar el array module también.

Answer 5

Una forma alternativa de resolver el problema es ir a través de la lista de palabras y ver si la palabra se puede construir a partir de los dados. De esta forma, necesitará muy poca memoria RAM, y podría ser más divertido codificar.(optimización y concurrencia)

Answer 6

Mire en DAWG s. Son mucho más compactos que los intentos.