Erlang：这个trie实现最错的是什么？

问题描述

在假期，我的家人喜欢玩Boggle。问题是，我在Boggle很可怕所以我做了什么好的程序员会做的：写了一个程序为我玩。

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

这是 trie：添加实现：

 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） 

您可以在这里查看其余的以及如何使用（在底部）的示例：

现在，这是我在Erlang的第一个认真的程序，我知道这可能是一堆事情错了...但是我直接关心的是它使用了。

那么，我做错了什么？而且我该怎么做一点点错误？

解决方案

您可以通过简单地将单词存储在ets中来实现此功能表：

 ％create table;添加单词
> ets：new（words，[named_table，set]）。 
> ets：insert（words，[{zed}]）。 
> ets：insert（words，[{zebra}]）。 
 
％检查单词是否存在
> ets：lookup（words，zed）。 
 [{zed}] 
 
％检查ze在单词
 78之间是否有延续; ets：match（words，{ze++'$ 1'}）。 
 [[d]，[bra]] 
  

如果trie是必须，但是您可以使用非功能性方法，那么您可以尝试 s或记录，例如 -record（node， {a，b，....，x，y，z}）。

Over the holidays, my family loves to play Boggle. Problem is, I'm terrible at Boggle. So I did what any good programmer would do: wrote a program to play for me.

At the core of the algorithm is a simple prefix trie, where each node is a dict of references to the next letters.

This is the trie:add implementation:

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

And you can see the rest, along with an example of how it's used (at the bottom), here:

Now, this being my first serious program in Erlang, I know there are probably a bunch of things wrong with it… But my immediate concern is that it uses 800 megabytes of RAM.

So, what am I doing most-wrong? And how might I make it a bit less-wrong?

解决方案

You could implement this functionality by simply storing the words in an ets table:

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

If trie is a must, but you can live with a non-functional approach, then you can try digraphs, as Paul already suggested.

If you want to stay functional, you might save some bytes of memory by using structures using less memory, for example proplists, or records, such as -record(node, {a,b,....,x,y,z}).

这篇关于Erlang：这个trie实现最错的是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！