एरलांग: इस त्रिभुज कार्यान्वयन के साथ सबसे गलत क्या है?

Question

छुट्टियों में, मेरे परिवार को बोगल खेलना अच्छा लगता है। समस्या यह है कि, मैं Boggle पर भयानक हूँ। तो मैंने किया कि कोई भी अच्छा प्रोग्रामर क्या करेगा: मेरे लिए खेलने के लिए एक कार्यक्रम लिखा था।

एल्गोरिदम के मूल में एक साधारण 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 कार्यान्वयन है

अब, यह एरलांग में मेरा पहला गंभीर कार्यक्रम है, मुझे पता है कि शायद इसमें कुछ चीजें गलत हैं ... लेकिन मेरा तत्काल ई चिंता यह है कि यह 800 मेगाबाइट रैम का उपयोग करता है।

तो, मैं सबसे गलत क्या कर रहा हूं? और मैं इसे थोड़ा कम गलत कैसे बना सकता हूं?

Answer 1

आप बस एक 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 कोशिश कर सकते हैं जैसा कि पौलुस ने पहले से ही सुझाव दिया है।

यदि आप कार्यात्मक रहना चाहते हैं, तो आप कम स्मृति का उपयोग करके संरचनाओं का उपयोग करके स्मृति के कुछ बाइट्स बचा सकते हैं, उदाहरण के लिए proplist एस, या -record(node, {a,b,....,x,y,z}) जैसे रिकॉर्ड।

Answer 2

मुझे आपके एल्गोरिदम के बारे में पता नहीं है, लेकिन यदि आप इतना अधिक डेटा संग्रहीत कर रहे हैं, तो शायद आपको बहुत से डिब्बे की बजाय अपने त्रिभुज का प्रतिनिधित्व करने के लिए एर्लांग की अंतर्निहित डिग्राफ लाइब्रेरी का उपयोग करना चाहिए। http://www.erlang.org/doc/man/digraph.html

Answer 3

मुझे याद नहीं है कि एक जादू कितनी मेमोरी लेती है, लेकिन आइए अनुमान लगाएं। आपके पास 2.5e6 वर्ण और 2e5 शब्द हैं। यदि आपके त्रिभुज में कोई साझा नहीं था, तो यह डिक्ट्स में 2.7e6 संघों को ले जाएगा (प्रत्येक चरित्र के लिए एक और प्रत्येक 'स्टॉप' प्रतीक)। एक साधारण विशुद्ध रूप से कार्यात्मक dict प्रतिनिधित्व शायद प्रति संगठन 4 शब्द होगा - यह कम हो सकता है, लेकिन मैं ऊपरी बाउंड पाने की कोशिश कर रहा हूं। 64-बिट मशीन पर, इसमें 8 * 4 * 2.7 मिलियन बाइट, या 86 मेगाबाइट्स लगेगा। यह आपके 800 एम का केवल दसवां हिस्सा है, इसलिए यहां कुछ निश्चित रूप से गलत है।

अद्यतन:dict.erl एक हैशटेबल के साथ डिक्ट का प्रतिनिधित्व करता है; जब आपके पास बहुत कम छोटे डिक होते हैं, तो यह बहुत अधिक ओवरहेड का तात्पर्य है। मैं proplists मॉड्यूल का उपयोग करने के लिए अपना कोड बदलने की कोशिश करता हूं, जो उपरोक्त मेरी गणना से मेल खाना चाहिए।

Answer 4

सभी शब्द अंग्रेजी में हैं, और मामले में कोई फर्क नहीं है, तो सभी पात्रों 1 से 26 करने के लिए संख्या से इनकोडिंग जा सकता है, 0 आरक्षित (और वास्तव में, Erlang में वे संख्या 97 से 122 करने के लिए कर रहे हैं) रोकने के लिए। तो आप array module का भी उपयोग कर सकते हैं।

Answer 5

समस्या को हल करने का एक वैकल्पिक तरीका शब्द सूची के माध्यम से जा रहा है और देखें कि शब्द पासा से बनाया जा सकता है या नहीं। इस तरह आपको बहुत कम रैम की आवश्यकता है, और यह कोड के लिए और अधिक मजेदार हो सकता है।(अनुकूलन और समरूपता)

Answer 6

DAWG एस में देखें। वे कोशिशों की तुलना में बहुत अधिक कॉम्पैक्ट हैं।