मैं हास्केल में एक साधारण डीपी एल्गोरिदम लागू करने की कोशिश कर रहा हूं (यह परियोजना यूलर से कोलात्ज़ अनुमान की समस्या के लिए है);हास्केल में Data.Map के साथ गतिशील प्रोग्रामिंग?
map<int,int> a;
int solve(int x) {
if (a.find(x) != a.end()) return a[x];
return a[x] = 1 + /* recursive call */;
}
तो कोड है कि मैं हास्केल में लिखा था इस तरह देख समाप्त हो गया:
solve :: (Memo, Int) -> (Memo, Int)
solve (mem, x) =
case Map.lookup x mem of
Just l -> (mem, l)
Nothing -> let (mem', l') = {- recursive call -}
mem'' = Map.insert x (1+l') mem'
in (mem'', 1+l')
(मुझे लगता है कि मैं सिर्फ यहां एक राज्य इकाई reimplementing कर रहा हूँ, लेकिन कभी यहां बराबर C++ है मन पल के लिए कि) कोड है जो सबसे बड़ा मान यह सबसे K = 1E6 में एक पैरामीटर के लिए दे सकते हैं खोजने की कोशिश करता हल कॉल:।
foldl'
(\(mem,ss) k ->
let (mem',x') = solve (mem, k)
in (mem', (x', k):ss))
(Map.singleton 1 1, [(1,1)]) [2..100000]
कोड के रूप में ऊपर लिखा एक ढेर अतिप्रवाह के साथ विफल रहता है। यह उम्मीद की जा रही है, मैं समझता हूं, क्योंकि यह वास्तव में एक बड़े अपर्याप्त थंक बनाता है। इसलिए मैं foldl अंदर '
x' `seq` (mem', (x',k):ss)
उपयोग करने की कोशिश, और यह कश्मीर = 1E5 के लिए सही जवाब गणना करता है। लेकिन यह के = 1e6 (12 सेकंड में ढेर ओवरफ्लो) के लिए विफल रहता है। तब मैं
mem'' `seq` l' `seq` (mem'', 1+l')
उपयोग करने की कोशिश, लेकिन यह (अभी भी ढेर अतिप्रवाह) कोई फर्क पड़ा। तब मैं
mem'' `deepseq` l' `seq` (mem'', 1+l')
का उपयोग कर यह बहुत धीमी है, शायद क्योंकि deepseq संपूर्ण नक्शा मेम '' के माध्यम से चलता है, एल्गोरिथ्म के समय जटिलता n * लॉग (एन) के बजाय द्विघात बनाने की कोशिश की।
इसे लागू करने का सही तरीका क्या है? मैं फंस गया हूं क्योंकि मैं पूरी गणना को सख्त बनाने के बारे में नहीं समझ सकता, और मुझे यकीन नहीं है कि गणना का कौन सा हिस्सा स्टैक ओवरफ़्लो देता है, लेकिन मुझे संदेह है कि यह नक्शा है। मैं, उदाहरण के लिए, सरणी का उपयोग कर सकता था, लेकिन मैं समझना चाहता हूं कि मैं यहां क्या कर रहा हूं।
आपका मतलब क्या है "सही?" –
मेरा मतलब है कि जो कि मेरे मन में है (सी ++) संस्करण के बराबर है, लेकिन जो स्टैक ओवरफ़्लो के साथ विफल नहीं होता है। – Kirill