मैं सख्त accumArray कैसे प्राप्त कर सकता हूं?

Question

मेरे पास कुंजी-मूल्य जोड़े की एक सूची है और मैं यह जानना चाहता हूं कि प्रत्येक कुंजी कितनी बार होती है और इसके साथ क्या मूल्य होता है, लेकिन जब मैं कोशिश करता हूं, तो मुझे एक स्टैक ओवरफ़्लो मिलता है।

import Array 
add (n, vals) val = n `seq` vals `seq` (n+1,val:vals) 
histo = accumArray add (0,[]) (0,9) [(0, n) | n <- [0..5000000]] 
main = print histo 

जब मैं 'GHC -O' के साथ इस संकलन और इसे चलाने, मैं: यहाँ कोड मैं चल रहा हूँ का एक सरलीकृत संस्करण है "ढेर अंतरिक्ष अतिप्रवाह:। वर्तमान आकार 8,388,608 बाइट्स"

मुझे लगता है कि मुझे पता है कि क्या हो रहा है: accumArray में फ़ोल्डल के समान गुण हैं, और इसलिए मुझे accumArray का सख्त संस्करण चाहिए। दुर्भाग्यवश, मुझे मिला एकमात्र डेटा Data.Array.Unboxed में है, जो सूचियों की सरणी के लिए काम नहीं करता है।

प्रलेखन कहता है कि जब संचय कार्य सख्त होता है, तो accumArray भी होना चाहिए, लेकिन मैं इसे काम पर नहीं ला सकता, और चर्चा here का दावा है कि दस्तावेज गलत है (कम से कम जीएचसी के लिए)।

क्या डेटा में किसी के अलावा accumArray का सख्त संस्करण है। Unn.Unboxed? या क्या मैं चाहता हूं कि ऐसा करने का एक बेहतर तरीका है?

Answer 1

खैर, सख्त का मतलब यह नहीं है कि कोई थंक्स नहीं बनाया गया है, इसका मतलब यह है कि यदि कोई तर्क नीचे है, तो परिणाम भी नीचे है। लेकिन accumArray वह सख्त नहीं है, अगर वे होते हैं तो यह सरणी में बोतलों को लिखता है। यह वास्तव में कुछ भी नहीं कर सकता है, क्योंकि इसे गैर-सख्त कार्यों की अनुमति देनी चाहिए जो परिभाषित मूल्यों को मध्यवर्ती बोतलों से उत्पन्न कर सकती हैं। और सख्तता विश्लेषक इसे फिर से लिख नहीं सकता है ताकि प्रत्येक लिखने पर डब्ल्यूएचएनएफ को संचय समारोह का मूल्यांकन किया जा सके, क्योंकि यह प्रोग्राम के अर्थशास्त्र को एक कठोर तरीके से बदल देगा (एक सरणी जिसमें कुछ बोतलों बनाम नीचे है) ।

यह कहा गया कि, मैं मानता हूं कि कई क्षेत्रों में सख्त और उत्सुक कार्यों की दुर्भाग्यपूर्ण कमी है।

आपकी समस्या के लिए, आप एक बड़ा ढेर का उपयोग कर सकते (+RTS -K128M यहाँ पर्याप्त नहीं था, लेकिन 256M किया), या आप उपयोग कर सकते हैं

import Data.Array.Base (unsafeRead, unsafeWrite) 
import Data.Array.ST 
import GHC.Arr 

strictAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i,a)] -> Array i e 
strictAccumArray fun ini (l,u) ies = case iar of 
             Array _ _ m barr -> Array l u m barr 
    where 
    iar = runSTArray $ do 
     let n = safeRangeSize (l,u) 
      stuff = [(safeIndex (l,u) n i, e) | (i, e) <- ies] 
     arr <- newArray (0,n-1) ini 
     let go ((i,v):ivs) = do 
       old <- unsafeRead arr i 
       unsafeWrite arr i $! fun old v 
       go ivs 
      go [] = return arr 
     go stuff 

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

एक अन्य विकल्प, एक सरणी के बजाय (या Data.IntMap अगर containers के संस्करण 0.4.1.0 है या बाद में) एक Data.Map उपयोग करने के लिए किया जाएगा के बाद से है कि insertWith', जो उपयोग पर संयोजन फ़ंक्शन के परिणाम बलों के साथ आता है। कोड उदाहरण के लिए एक Map का उपयोग करने का हो सकता है

import qualified Data.Map as M -- or Data.IntMap 
import Data.List (foldl') 

histo :: M.Map Int (Int,[Int]) -- M.IntMap (Int,[Int]) 
histo = foldl' upd M.empty [(0,n) | n <- [0 .. 15000000]] 
    where 
    upd mp (i,n) = M.insertWith' add i (1,[n]) mp 
    add (j,val:_) (k,vals) = k `seq` vals `seq` (k+j,val:vals) 
    add _ pr = pr -- to avoid non-exhaustive pattern warning 

नुकसान कर रहे हैं

• संयोजन समारोह प्रकार a -> a -> a होना आवश्यक है, तो यह एक सा अपने मामले में और अधिक जटिल होने की जरूरत है।
• ओ (1) के बजाय एक अद्यतन ओ (लॉग आकार) है, इसलिए बड़े हिस्टोग्राम के लिए, यह काफी धीमा होगा।
• Map एस और IntMap के पास कुछ पुस्तक-रखरखाव ओवरहेड है, ताकि एक सरणी से अधिक स्थान का उपयोग किया जा सके। लेकिन यदि सूचकांक की संख्या की तुलना में अद्यतनों की सूची बड़ी है, तो अंतर इस मामले में नगण्य होगा (ओवरहेड k प्रति कुंजी शब्द, मूल्यों के आकार से स्वतंत्र) है, जहां मूल्यों का आकार प्रत्येक के साथ बढ़ता है अद्यतन करें।