हास्केल: क्या मैं स्मृति में सूची रखे बिना एक ही आलसी सूची में कई गुना कर सकता हूं?

Question

मेरा संदर्भ जैव सूचना विज्ञान है, विशेष रूप से अगली पीढ़ी अनुक्रमित है, लेकिन समस्या सामान्य है; तो मैं एक उदाहरण के रूप में एक लॉग फ़ाइल का उपयोग करेंगे।

फ़ाइल बहुत बड़ी (गीगाबाइट, बड़े संकुचित, तो यह स्मृति में फिट नहीं होगा) है, लेकिन पार्स करने के लिए (प्रत्येक पंक्ति एक प्रविष्टि है) आसान है, तो हम आसानी से की तरह कुछ लिख सकते हैं:

parse :: Lazy.ByteString -> [LogEntry] 

अब, मेरे पास बहुत सारे आंकड़े हैं जिन्हें मैं लॉग फ़ाइल से गणना करना चाहता हूं। इन सभी के रूप foldl' k z . map f के हैं

totalEntries = length 
nrBots = sum . map fromEnum . map isBotEntry 
averageTimeOfDay = histogram . map extractHour 

: यह इस तरह के रूप में अलग कार्यों लिखने के लिए सबसे आसान है।

समस्या यह है कि अगर मैं की तरह

main = do 
    input <- Lazy.readFile "input.txt" 
    let logEntries = parse input 
     totalEntries' = totalEntries logEntries 
     nrBots' = nrBots logEntries 
     avgTOD = averageTimeOfDay logEntries 
    print totalEntries' 
    print nrBots' 
    print avgTOD 

, सबसे प्राकृतिक तरीके से इस्तेमाल करने की कोशिश यह स्मृति में पूरी सूची आवंटित करेगा, जो कि मैं क्या नहीं करना चाहता है। मैं चाहता हूं कि गुना सिंक्रनाइज़ किया जाए, ताकि विपक्षी कोशिकाओं को कचरा इकट्ठा किया जा सके। अगर मैं केवल एक ही आंकड़े की गणना करता हूं, तो यही होता है।

मैं ऐसा एक बड़ा फ़ंक्शन लिख सकता हूं जो यह करता है, लेकिन यह गैर-संगत कोड है।

वैकल्पिक रूप से, जो है मैं, क्या कर रहे हैं मैं एक अलग से पारित चलाते हैं, लेकिन इस & पुन: लोड फ़ाइल हर बार uncompresses।

Answer 1

यह इस 'beautiful folding' essay की चर्चा करते हुए यह बहुत शांत था sdcvvc की टिप्पणी पर एक टिप्पणी है आधुनिकीकरण के अन्य बिट्स। एक साथ फोल्डिंग, xy और z एक सीधा उत्पाद है: (,,) <$> x <*> y <*> z। मैंने छोटी यादृच्छिक चींटियों की आधा गीगाबाइट फ़ाइल बनाई और इसमें 10 सेकंड लग गए - स्वीकार्य रूप से तुच्छ - लंबाई, योग और अधिकतम मेरे जंगली लैपटॉप पर गणना। यह और एनोटेशन द्वारा मदद की प्रतीत नहीं होती है, लेकिन संकलक Int देख सकता था, जिसमें मुझे रूचि थी; स्पष्ट map read . lines एक पार्सर के रूप में एक निराशाजनक जगह और समय आपदा का कारण बन गया, इसलिए मैंने ByteString.readInt के कच्चे उपयोग के साथ खुलासा किया; अन्यथा यह मूल रूप से Data.List प्रक्रिया है।

{-# LANGUAGE GADTs, BangPatterns #-} 

import Data.List (foldl', unfoldr) 
import Control.Applicative 
import qualified Data.ByteString.Lazy.Char8 as B 

main = fmap readInts (B.readFile "int.txt") >>= print . fold allThree 
    where allThree = (,,) <$> length_ <*> sum_ <*> maximum_ 

data Fold b c where F :: (a -> b -> a) -> a -> (a -> c) -> Fold b c 
data Pair a b = P !a !b 

instance Functor (Fold b) where fmap f (F op x g) = F op x (f . g) 

instance Applicative (Fold b) where 
    pure c = F const() (const c) 
    (F f x c) <*> (F g y c') = F (comb f g) (P x y) (c *** c') 
    where comb f g (P a a') b = P (f a b) (g a' b) 
      (***) f g (P x y) = f x (g y) 

fold :: Fold b c -> [b] -> c 
fold (F f x c) bs = c $ (foldl' f x bs) 

sum_, product_ :: Num a => Fold a a 
length_ :: Fold a Int 
sum_  = F (+) 0 id 
product_ = F (*) 1 id 
length_ = F (const . (+1)) 0 id 
maximum_ = F max 0 id 
readInts = unfoldr $ \bs -> case B.readInt bs of 
    Nothing  -> Nothing 
    Just (n,bs2) -> if not (B.null bs2) then Just (n,B.tail bs2) 
             else Just (n,B.empty) 

संपादित करें: आश्चर्य, हम एक अनबॉक्स्ड प्रकार ऊपर, और एक अनबॉक्स्ड वेक्टर उदा से ली गई साथ क्या करना है के बाद सेएक 2 जी फ़ाइल मेमोरी में फिट हो सकती है, यह सब कुछ तेज़ और कुछ हद तक बेहतर व्यवहार होता है यदि इसे डेटा के लिए स्पष्ट रीलेटरिंग दिया जाता है। वेक्टर। यूस्क्ड http://hpaste.org/69270 बेशक यह प्रासंगिक नहीं है जहां LogEntry जैसे प्रकार हैं नोट करें कि Fold टाइप और फोल्ड 'गुणा' अनुक्रमिक प्रकारों पर संशोधन के बिना सामान्यीकृत करता है, इस प्रकार उदाहरण के लिए Char एस या Word8 एस पर संचालन के साथ जुड़े फ़ोल्ड एक साथ बाइटस्ट्रिंग पर सीधे फोल्ड किए जा सकते हैं। विभिन्न बाइटस्ट्रिंग मॉड्यूल में foldl' एस का उपयोग करने के लिए fold को रीलेटर करके foldB को पहले परिभाषित करना होगा। लेकिन Fold और Fold के उत्पाद एक ही हैं जिन्हें आप किसी सूची या Char के वेक्टर या गुना होगा Word8 रों

Answer 2

आलसी डेटा muiltiple बार संसाधन के लिए, निरंतर अंतरिक्ष में, आप तीन कर सकते हैं:

• खरोंच से आलसी सूची n बार
• फ्यूज n एक एकल में गुजरता है फिर से निर्माण अनुक्रमिक गुना जो प्रत्येक चरण को लॉक चरण में करता है।
• उपयोग par एक ही समय

पर n समानांतर traversals करने के लिए उन अपने विकल्प हैं। सुंदर, के रूप में वे कहते हैं - - मैं Functor और Applicative उदाहरणों और कुछ जोड़ने का विरोध नहीं कर सकता है कि पिछले एक सबसे अच्छे :)