एसपीओजे के लिए यह ज्ञात डीपी तालिका कितनी धीमी है?

Question

स्पोइलर्स: मैं http://www.spoj.pl/problems/KNAPSACK/ पर काम कर रहा हूं इसलिए यदि आप संभव समाधान खराब नहीं करना चाहते हैं तो देखें।

बॉयलरप्लेट:

type Item = (Weight, Value) 
type Weight = Int 
type Value = Int 

weight :: Item -> Weight 
weight = fst 

value :: Item -> Value 
value = snd 

makeItem :: [String] -> Item 
makeItem [w, v] = (read w, read v) 

और प्राथमिक कार्य:

import Data.Sequence (index, fromList) 
import Data.MemoCombinators (memo2, integral) 

main = interact knapsackStr 

knapsackStr :: String -> String 
knapsackStr str = show $ knapsack items capacity numItems 
    where [capacity, numItems] = map read . words $ head ls 
     ls = lines str 
     items = map (makeItem . words) $ take numItems $ tail ls 

कुछ प्रकार के और सहायकों मंच तैयार करने के लिए

knapsack :: [Item] -> Weight -> Int -> Value 
knapsack itemsList = go 
    where go = memo2 integral integral knapsack' 
     items = fromList $ (0,0):itemsList 
     knapsack' 0 _ = 0 
     knapsack' _ 0 = 0 
     knapsack' w i | wi > w = exclude 
         | otherwise = max exclude include 
      where wi = weight item 
       vi = value item 
       item = items `index` i 
       exclude = go w (i-1) 
       include = go (w-wi) (i-1) + vi 

और इस कोड काम करता है; मैंने एसपीओजे नमूना परीक्षण मामले में प्लगिंग करने की कोशिश की है और यह सही परिणाम उत्पन्न करता है। लेकिन जब मैं एसपीओजे को यह समाधान प्रस्तुत करता हूं (ल्यूक पामर के मेमोकॉम्बिनेटर्स को आयात करने के बजाय, मैं बस आवश्यक स्रोतों को प्रतिलिपि स्रोत में कॉपी और पेस्ट करता हूं), यह समय सीमा से अधिक है। =/

मुझे समझ में नहीं आता क्यों; 0-0-1 knapsack करने के लिए एक कुशल तरीका के बारे में, और मुझे काफी आश्वस्त है कि यह जितना तेज़ हो जाता है: एक ज्ञापन कार्य जो केवल उप-प्रविष्टियों की गणना करेगा जो इसे पूरी तरह से करने के लिए आवश्यक हैं सही परिणाम क्या मैंने किसी भी तरह से यादों को गड़बड़ कर दिया? क्या इस कोड में धीमा बिंदु है कि मुझे याद आ रही है? एसपीओजे सिर्फ हास्केल के खिलाफ पक्षपातपूर्ण है?

मैंने जमा करने के शीर्ष पर {-# OPTIONS_GHC -O2 #-} भी रखा, लेकिन हां, इससे मदद नहीं मिली। मैंने एक समान समाधान की कोशिश की है जो Sequence एस की 2 डी सरणी का उपयोग करती है, लेकिन इसे धीमी गति से अस्वीकार कर दिया गया था।

Answer 1

एक बड़ी समस्या है जो वास्तव में इसे धीमा कर देती है। यह बहुत बहुलक है। फ़ंक्शन के प्रकार-विशिष्ट संस्करण पॉलीमोर्फिक किस्मों की तुलना में बहुत तेज हो सकते हैं, और किसी भी कारण से जीएचसी इस कोड को उस बिंदु पर रेखांकित नहीं कर रहा है जहां यह उपयोग में सटीक प्रकार निर्धारित कर सकता है। जब मैं करने के लिए integral की परिभाषा बदलने के लिए:

integral :: Memo Int 
integral = wrap id id bits 

मैं एक लगभग 5 गुना speedup मिलता है, मुझे लगता है कि एसपीओजे पर इसे स्वीकार करना काफी तेज़ है।

हालांकि यह अभी भी gorlum0 के समाधान से काफी धीमा है। मुझे संदेह है क्योंकि इसका कारण है क्योंकि वह सरणी का उपयोग कर रहा है और आप कस्टम ट्राई प्रकार का उपयोग करते हैं। एक ट्राई का उपयोग करने से अधिक मेमोरी और कैश मिस इत्यादि के कारण लुकअप धीमे हो जाएंगे। यदि आप IntMap में फ़ील्ड सख्त और अनबॉक्स करते हैं तो आप बहुत अंतर कर सकते हैं, लेकिन मुझे यकीन नहीं है यह संभव है। BitTrie में फ़ील्ड को सख्त करने का प्रयास करने के लिए मेरे लिए रनटाइम क्रैश बनाता है।

शुद्ध हैकेल ज्ञापन कोड अच्छा हो सकता है, लेकिन मुझे नहीं लगता कि यह असुरक्षित चीजें (कम से कम हुड के नीचे) के रूप में तेज़ है। आप Lennart Augustsson's technique लागू कर सकते हैं यह देखने के लिए कि क्या यह ज्ञापन पर बेहतर किराया है।

Answer 2

हास्केल को धीमा करने वाली एक चीज आईओ है, हास्केल में स्ट्रिंग प्रकार यूटीएफ 8 समर्थन देता है जिसे हमें एसपीओजे की आवश्यकता नहीं है। बाइटस्ट्रिंग तेजी से चमक रहे हैं ताकि आप इसके बजाय उनका उपयोग करने पर विचार करना चाहें।