Erlang: Điều gì là sai nhất với việc thực hiện trie này?

Question

Trong những ngày nghỉ, gia đình tôi rất thích chơi Boggle. Vấn đề là, tôi khủng khiếp ở Boggle. Vì vậy, tôi đã làm những gì bất kỳ lập trình viên tốt sẽ làm: đã viết một chương trình để chơi cho tôi.

Tại lõi của thuật toán là một đơn giản prefix trie, trong đó mỗi nút là một tham chiếu dict của các chữ cái tiếp theo.

này là việc thực hiện 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).

Và bạn có thể xem phần còn lại, cùng với một ví dụ về cách nó được sử dụng (ở phía dưới), ở đây:

http://gist.github.com/263513

Bây giờ, đây là chương trình nghiêm túc đầu tiên của tôi ở Erlang, tôi biết có lẽ có nhiều điều sai trái với nó… Nhưng e quan tâm là nó sử dụng 800 megabyte RAM.

Vì vậy, tôi đang làm gì sai nhất? Và làm thế nào tôi có thể làm cho nó một chút ít sai?

Answer 1

Bạn có thể thực hiện chức năng này bằng cách đơn giản lưu trữ từ một bảng 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"]] 

Nếu Trie là điều bắt buộc, nhưng bạn có thể sống với một cách tiếp cận không hoạt động, sau đó bạn có thể thử digraph s, như Paul đã gợi ý.

Nếu bạn muốn duy trì chức năng, bạn có thể tiết kiệm một số byte bộ nhớ bằng cách sử dụng cấu trúc sử dụng ít bộ nhớ hơn, ví dụ proplist s hoặc bản ghi, chẳng hạn như -record(node, {a,b,....,x,y,z}).

Answer 2

Tôi không biết thuật toán của bạn, nhưng nếu bạn đang lưu trữ nhiều dữ liệu, có thể bạn nên xem xét sử dụng thư viện đồ họa tích hợp của Erlang để đại diện cho trie của bạn, thay vì rất nhiều dicts. http://www.erlang.org/doc/man/digraph.html

Answer 3

Tôi không nhớ có bao nhiêu bộ nhớ mà một dict mất, nhưng hãy ước tính. Bạn có 2,5e6 ký tự và 2e5 từ. Nếu trie của bạn không có chia sẻ gì cả, thì sẽ mất 2,7e6 liên kết trong các dicts (một cho mỗi ký tự và mỗi ký hiệu 'stop'). Một biểu diễn dict thuần túy đơn giản có thể có 4 từ cho mỗi liên kết - nó có thể ít hơn, nhưng tôi đang cố gắng để có một giới hạn trên. Trên máy tính 64 bit, nó sẽ mất 8 * 4 * 2,7 triệu byte hoặc 86 megabyte. Đó chỉ là một phần mười của 800 triệu của bạn, do đó, một cái gì đó chắc chắn sai ở đây.

Cập nhật:dict.erl đại diện cho dicts có thẻ bắt đầu bằng #; điều này ngụ ý rất nhiều chi phí khi bạn có rất nhiều dicts rất nhỏ, như bạn làm. Tôi muốn thử thay đổi mã của bạn để sử dụng mô-đun proplists, mà phải phù hợp với các tính toán của tôi ở trên.

Answer 4

Nếu tất cả các từ bằng tiếng Anh, và trường hợp không quan trọng, tất cả các nhân vật có thể được mã hóa bằng số 1-26 (và trên thực tế, trong Erlang họ là số 97-122), đặt 0 để dừng lại. Vì vậy, bạn cũng có thể sử dụng số array module.

Answer 5

Một cách khác để giải quyết vấn đề là đi qua danh sách từ và xem liệu từ đó có thể được xây dựng từ xúc xắc hay không. Bằng cách đó bạn cần rất ít RAM, và nó có thể thú vị hơn để viết mã.(tối ưu hóa và đồng thời)

Answer 6

Nhìn vào DAWG s. Chúng nhỏ gọn hơn nhiều so với cố gắng.