Geek Answers Handbook

Erlang: What's the worst part about this implementation?

On holidays, my family likes to play Boggle. The problem is that I'm terrible at Boggle. Therefore, I did what any good programmer could do: wrote a program for me.

The algorithm is based on a simple trie prefix , where each node is a dictreference to the following letters.

This is the implementation 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 .

, - ? ?

+5
6

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

, , , proplist s, , -record(node, {a,b,....,x,y,z}).

+4

, , . 2.5e6 2e5 . , 2.7e6 dicts ( "stop" ). dict 4 - , . 64- 8 * 4 * 2,7 86 . 800M, - .

: dict.erl dicts -; , , . , proplists, .

+4

, . , , , , . ( concurrency)

+2

DAWG. , .

+2

, , , Erlang trie, dicts. http://www.erlang.org/doc/man/digraph.html

+1

If all words are in English, and the case does not matter, all characters can be encoded with numbers from 1 to 26 (and in fact in Erlang they are numbers from 97 to 122), reserving 0 to stop. That way you can use arraymodule .

+1
source

More articles:


All Articles