Erlang: Что больше всего неправильно с этой trie реализацией?
По праздникам мое семейство любит играть Испуг. Проблема, я ужасен в Boggle. Таким образом, я сделал то, что сделает любой хороший программист: записал программу для проигрывания для меня.
В ядре алгоритма простой префикс trie, где каждый узел является a 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 }
% error -> { dict:new(), Default }
% end.
{ NewTrie, SubTrie } = setdefault(Ch, dict:new(), Trie),
NewSubTrie = add(Rest, SubTrie),
dict:store(Ch, NewSubTrie, NewTrie).И Вы видите остальных, наряду с примером того, как он использовал (внизу), здесь:
Теперь, причем этот моя первая серьезная программа в Erlang, я знаю, что существует, вероятно, набор вещей неправильно с ним …, Но мое непосредственное беспокойство - то, что это использует 800 мегабайтов RAM.
Так, что я делаю больше всего неправильно? И как я мог бы сделать его немного меньше неправильно?
5 ответов
Эту функциональность можно реализовать, просто сохранив слова в таблице 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 - это must, то можно жить с нефункциональным подходом, тогда вы можете попробовать digraphs, как уже предлагал Пол.
Если вы хотите сохранить работоспособность, вы можете сохранить некоторые байты памяти, используя структуры, использующие меньше памяти, например proplists, или записи, такие как - record(node, {a,b,....,x,y,z}).
Альтернативный способ решения проблемы - просмотреть список слов и посмотреть, можно ли построить слово из кубиков. Таким образом, вам понадобится очень мало оперативной памяти, и, возможно, будет более интересно кодировать. (оптимизация и параллелизм)
Я не помню, сколько памяти занимает диктат, но давайте оценим. У вас 2.5e6 символов и 2e5 слов. Если бы ваше три вообще не делилось, то это заняло бы 2,7e6 ассоциаций в диктовке (по одной на каждый символ и на каждый символ "стоп"). Простое чисто функциональное представление диктата может быть 4 слова на ассоциацию - это может быть меньше, но я пытаюсь получить верхнюю границу. На 64-битной машине это заняло бы 8*4*2.7 миллиона байт, или 86 мегабайт. Это всего лишь десятая часть от ваших 800M, так что здесь что-то определённо не так.
Update: dict.erl представляет диктаты с хэшированием; это подразумевает много накладных расходов, когда у вас есть много очень маленьких диктатов, как у вас есть. Я бы попробовал изменить ваш код, чтобы использовать модуль proplists, который должен соответствовать моим вычислениям, приведенным выше.
. Если все слова на английском языке, и регистр не имеет значения, то все символы могут быть закодированы числами от 1 до 26 (а на самом деле в Эрланге они являются числами от 97 до 122), зарезервировав 0 для стопа. Поэтому можно использовать и модуль array.
Не знаю, как ваш алгоритм, но если вы храните столько данных, то, возможно, вам стоит подумать об использовании встроенной библиотеки диграфов Эрланга для отображения вашего триединства, а не стольких диграфов. http://www.erlang.org/doc/man/digraph.html