Erlang :이 trie 구현에서 가장 잘못된 점은 무엇입니까?

휴일 동안 내 가족은 Boggle 게임을 좋아합니다. 문제는, 나는 Boggle에게 끔찍합니다. 그래서 나는 훌륭한 프로그래머가 할 일을했습니다. 나를 위해 게임 할 프로그램을 썼습니다.Erlang :이 trie 구현에서 가장 잘못된 점은 무엇입니까?

알고리즘의 핵심 부분은 단순한 prefix trie입니다. 각 노드는 다음 문자에 대한 참조로 dict입니다. 당신이 (바닥에) 사용되는 방법의 예와 함께, 나머지를 볼 수 있습니다

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

이

은 trie:add 구현

이제 Erlang에서 처음으로 진지한 프로그램이되었는데, 아마 거기에는 여러 가지 문제가 있다는 것을 알고 있습니다 ...하지만 내 immediat 걱정거리는 RAM의 800 메가 바이트을 사용한다는 것입니다.

그래서 내가 가장 잘못하고있는 것은 무엇입니까? 어떻게 조금 덜 잘못 만들 수 있습니까?

출처

2009-12-26 David Wolever

하. 몇 년 전에 PHP에서 그렇게했습니다. – gahooa

입력 단어 목록의 크기는 어느 정도입니까? – Zed

내 단어 목록은 200,000 단어 (또는 2.5 megs)입니다. –

가 :

트라이은 필수이지만, 당신은 비 기능적 접근 방식으로 살 수있는 경우

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

, 다음 digraph을 시도 할 수 있습니다 s, Paul은 이미 제안했습니다.

기능을 유지하려면 메모리가 적은 구조체 (예 : proplist) 또는 -record(node, {a,b,....,x,y,z})과 같은 레코드를 사용하여 일부 메모리를 절약 할 수 있습니다.

출처

2009-12-26 20:23:36 Zed

아, 시원한 - 팁 주셔서 감사. –

좋아요. 그렇기 때문에 저는 ets로 꼼꼼히 살펴 보았습니다. 그러나 나는 "나쁜 주장"으로 문제를 겪어 왔습니다. 어쩌면 간단한 해결책을 아십니까? 질문은 여기에 있습니다 : http://stackoverflow.com/questions/1964990/erlang-ets-reset-ets-table-after-getting-a-bad-argument –

그래, 나는 프로 플라이스트 구현을 너무 바꿨다. 그리고 쉘이 멈추는 문제가 발생했습니다. 나는 여기에 물었다 : http://stackoverflow.com/questions/1982257/erlang-erl-shell-hangs-after-building-a-large-data-structure (추신 : 귀하의 모든 도움을 주셔서 감사합니다 - 그것은 대단히 감사합니다.). –

알고리즘에 대해서는 잘 모르겠지만, 많은 데이터를 저장하고 있다면 얼랭의 빌트인 그래프 라이브러리를 사용하여 많은 dict 대신 트라이를 표현해야합니다. http://www.erlang.org/doc/man/digraph.html

당신은 단순히 ETS 테이블에 단어를 저장하여이 기능을 구현할 수

출처

2009-12-26 18:56:03 Paul

멋지다 - 나는 그것을 들여다 볼 것이다. 감사. –

메모리가 얼마인지 기억이 안납니다.하지만 예상하겠습니다. 당신은 2.5e6 문자와 2e5 단어가 있습니다. 귀하의 트라이가 전혀 공유되지 않았다면, 그 딕트에서 2.7e6 협회 (각 문자와 각 '정지'기호에 대해 하나씩)를 취할 것입니다. 단순한 순전히 기능적인 dict 표현은 아마도 협회 당 4 단어 일 것입니다 - 그것은 더 적을 수는 있지만 상한을 얻으려고합니다. 64 비트 컴퓨터에서는 8 * 4 * 2.7 백만 바이트 또는 86 메가 바이트가 소요됩니다. 800M의 10 분의 1 밖에 안되기 때문에 여기서 뭔가 잘못 될 것입니다.

업데이트 :dict.erl은 해시 테이블이있는 dicts를 나타냅니다. 이것은 매우 작은 dicts를 가지고있을 때 많은 오버 헤드를 의미합니다. 위의 계산과 일치해야하는 proplists 모듈을 사용하도록 코드를 변경하려고합니다.

출처

2009-12-26 21:22:56

dict() 구문에 필요한 메모리 양을 확인하려면'erts_debug : flat_size (dict : new()) '를 호출하십시오. 32 비트 시스템에서는 184 바이트, 64 비트 시스템에서는 368 바이트 인 46 단어를 반환합니다. – Zed

제안을 주셔서 감사합니다 ... 내가 여기에 물어 보았던 내 proplist 기반 trie를 만들 때 쉘이 멈추는 이상한 문제가 생겼지 만 http://stackoverflow.com/questions/1982257/ erlang-erl-shell-hangs-after-a-large-data-structure - 혹시라도 통찰력을 제공 할 수 있습니까? –

모든 단어가 영어로되어 있고 대소 문자가 중요하지 않은 경우 모든 문자를 1에서 26까지의 숫자로 인코딩 할 수 있습니다. 실제로 Erlang의 경우 은이고 97에서 122까지의 숫자입니다. 0 그만. 따라서 array module도 사용할 수 있습니다.

출처

2009-12-26 23:04:47