Эрланг: Что самое плохое в этой реализации? - PullRequest
Новая
       55

Эрланг: Что самое плохое в этой реализации?

5 голосов
/ 26 декабря 2009

В праздничные дни моя семья любит играть в Boggle. Проблема в том, что я ужасен в Боггле. Поэтому я сделал то, что сделал бы любой хороший программист: написал программу для меня.

В основе алгоритма лежит простой префикс trie , где каждый узел представляет собой 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).

И остальное, а также пример его использования (внизу) можно посмотреть здесь:

http://gist.github.com/263513

Теперь, это моя первая серьезная программа на Эрланге, и я знаю, что с ней, вероятно, что-то не так… Но меня беспокоит то, что она использует 800 мегабайт оперативной памяти .

Итак, что я делаю больше всего неправильно? И как я могу сделать это немного менее неправильно?

Ответы [ 6 ]

4 голосов
/ 27 декабря 2009

Я не помню, сколько памяти занимает дикт, но давайте оценим. У вас есть 2.5e6 символов и 2e5 слов. Если ваша игра не делится вообще, это потребует 2.7e6 ассоциаций в словах (по одному на каждого персонажа и каждый символ «стоп»). Простое чисто функциональное диктовое представление может составлять 4 слова в ассоциации - это может быть меньше, но я пытаюсь получить верхнюю границу. На 64-битной машине это заняло бы 8 * 4 * 2,7 миллиона байт или 86 мегабайт. Это только десятая часть вашего 800M, так что здесь что-то не так.

Обновление: dict.erl представляет диктовки с хеш-таблицей; это подразумевает много накладных расходов, когда у вас много очень маленьких диктовок, как и у вас. Я бы попробовал изменить ваш код для использования модуля proplists , который должен соответствовать моим вычислениям выше.

4 голосов
/ 26 декабря 2009

Вы можете реализовать эту функцию, просто сохранив слова в таблице 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}).

2 голосов
/ 04 января 2011

Посмотрите на DAWG с. Они намного более компактны, чем попытки.

2 голосов
/ 29 декабря 2009

Альтернативный способ решения проблемы - просмотреть список слов и посмотреть, можно ли составить слово из кости. Таким образом, вам нужно очень мало оперативной памяти, и, возможно, будет интереснее писать код. (оптимизация и параллелизм)

1 голос
/ 27 декабря 2009

Если все слова на английском языке, и регистр не имеет значения, все символы могут быть закодированы числами от 1 до 26 (и на самом деле, в Erlang они являются числами от 97 до 122) , оставляя 0 для остановки. Таким образом, вы также можете использовать модуль array .

1 голос
/ 26 декабря 2009

Я не знаю о вашем алгоритме, но если вы храните такое количество данных, возможно, вам следует использовать встроенную библиотеку Эрфлана для представления вашего текста вместо множества слов. http://www.erlang.org/doc/man/digraph.html

...