तेजी से यादृच्छिकता और शुद्धता के साथ समानांतर गणना?

Question

मेरा लक्ष्य से parMap का उपयोग करके गणना को समानांतर करना है, लेकिन मैं अपने नमूना समारोह में कुछ यादृच्छिकता भी जोड़ना चाहता हूं।

यादृच्छिकता के बिना मेरी गणना केवल कुछ संख्या क्रंचिंग है और इसलिए यह शुद्ध है और मैं parMap का उपयोग कर सकता हूं। अच्छे नतीजे पाने के लिए, मुझे प्रत्येक चरण में कई नमूने लेने और परिणामों को औसत करने की आवश्यकता है। नमूनाकरण यादृच्छिक होना चाहिए।

एक समाधान random package का उपयोग करने के लिए हो सकता है, randoms पर कॉल करें और फिर गणना के दौरान उस सूची का उपभोग करें (गणना के लिए शुद्ध आलसी सूची को पार करके मैं इसे शुद्ध रखूंगा)। दुर्भाग्यवश, यह एक बहुत धीमी यादृच्छिक संख्या जनरेटर है और मुझे बहुत यादृच्छिक संख्या की आवश्यकता है इसलिए मैं mwc-random या mersenne-random (हालांकि, मुझे नहीं लगता कि मेर्सन-यादृच्छिक अभी भी बनाए रखा गया है) का उपयोग करना पसंद करेंगे।

randoms जैसे फ़ंक्शन लिखने के लिए mwc-random के साथ unsafePerformIO जैसे कुछ उपयोग करना सुरक्षित है? कुछ ऐसा:

randomsMWC :: Variate a => GenST s -> [a] 
randomsMWC g = unsafePerformIO $ unsafeSTToIO $ randomsMWC' g 
    where 
    randomsMWC' g = do 
    a <- uniform g 
    as <- unsafeInterleaveST $ randomsMWC' g 
    return (a : as) 

क्या मुझे इसके बजाय parallel number generator तक पहुंचने की आवश्यकता है? या क्या मुझे बुलेट काटने और स्वीकार करने की ज़रूरत है कि धीमे यादृच्छिक पैकेज का उपयोग किये बिना मेरा एल्गोरिदम शुद्ध नहीं है?

सुझाव? धन्यवाद!

Answer 1

तो अनियमितता के एक एकल थ्रेड स्रोत होने प्रदर्शन के लिए एक समस्या नहीं है, तो आप MWC यादृच्छिक चारों ओर एक शुद्ध आवरण

import Control.Monad.ST.Lazy 
import Control.Monad 
import System.Random.MWC 

rList :: Variate a => Seed -> [a] 
rList s = runST $ do 
    g <- strictToLazyST $ restore s 
    advance g 

advance :: Variate a => Gen s -> ST s [a] 
advance g = do 
    x <- strictToLazyST $ uniform g 
    xs <- x `seq` advance g 
    return (x:xs) 

यहाँ

rList एक बीज लेता है प्राप्त कर सकते हैं, और फिर lazily एक का उत्पादन आंशिक रूप से आलसी संख्याओं की अनंत धारा। मुझे यकीन नहीं है कि strictToLazyST वास्तव में सुरक्षित है, लेकिन कोई भी इसे ऑब्जेक्ट करने लगता है। मैंने कोई बेंचमार्किंग नहीं की है, लेकिन मुझे संदेह है कि यह बहुत तेज़ है। मुझे लगता है कि जनरेटर के साथ एन्कोड किए गए डेटा प्रवाह के कारण mwc-random थ्रेड सुरक्षित है, और इसका उपयोग ST मोनैड में किया जा सकता है। उपरोक्त हैक का उपयोग करने के लिए किसी को आमंत्रित करना। मुझे नहीं लगता कि seq आवश्यक है, लेकिन यह मुझे strictToLazyST का कम संदेहजनक बनाता है जो मुझे पता है कि मेरे पास निर्धारिती मूल्यांकन आदेश है (और यह अभी भी काम करने के लिए पर्याप्त आलसी है)।

आपको वास्तविक यादृच्छिक बीज उत्पन्न करने के लिए कहीं भी यादृच्छिकता (IO) की आवश्यकता है, लेकिन इससे आपको अधिकांश कोड शुद्ध रखना चाहिए, और जब आप आवश्यक हो तो बीज को फ़ाइल या पुन: उपयोग करने दें।

GHCi:

λ: gen <- create 
λ: x <- save gen 
λ: drop 1 $ take 10 $ rList x :: [Int] 
[4443157817804305558,-6283633474236987377,3602072957429409483, 
-5035101780705339502,-925260411398682800,423158235494603307, 
-6981326876987356147,490540715145304360,-8184987036354194323] 

Answer 2

मेरा अनुमान है कि Mersenne यादृच्छिक सुरक्षित थ्रेड नहीं है, इसलिए किसी भी unsafe... और साथ में चलाना का उपयोग कर एक से अधिक थ्रेड से बुला के साथ समस्याओं पर ले जाएगा है। (। यह भी देखें GHC manual धारा 8.2.4.1)

कार्य अनियमितता की जरूरत है कि शुद्ध नहीं हैं, वे अनियमितता के कुछ स्रोत है, जो या तो बाहरी है (hardware - एक युक्ति नमूना शोर की तरह) की जरूरत है और इसलिए IO करने के लिए बाध्य, या छद्म यादृच्छिक, जिसे गणना के दौरान कुछ राज्य रखने की जरूरत है। किसी भी तरह से वे शुद्ध हास्केल कार्यों नहीं हो सकते हैं।

मैं की तरह

class Monad m => MonadParRand m where 
    random  :: MTRandom a => m a 
    parSequence :: [m a] -> m [a] 

जो आपको एक विशिष्ट कार्यान्वयन करने के लिए बाध्य किया जा रहा बिना अपने मुख्य कोड लिखने के लिए अनुमति देगा, एक विशिष्ट इकाई प्रकार वर्ग को अपनी आवश्यकताओं के अलग उदाहरण के लिए कुछ के साथ शुरू होगा। या यदि आप बोल्ड महसूस कर रहे हैं आप monad-parallel का उपयोग करें और अब मुश्किल हिस्सा कैसे दोनों random और parSequence (या MonadParallel के bindM2) और यह तेजी से बनाने परिभाषित करने के लिए है की तरह

class MonadParallel m => MonadParRand m where 
    random  :: MTRandom a => m a 

कुछ निर्धारित कर सकते हैं। चूंकि आप bindM2 के नियंत्रण में हैं, इसलिए आप प्रबंधित कर सकते हैं कि थ्रेड कैसे उत्पन्न होते हैं और वे किस स्थिति में रहते हैं। तो आप प्रत्येक थ्रेड को एक बफर बांध सकते हैं जिससे यह यादृच्छिक संख्या खींचता है। यदि बफर खाली है, तो यह मेर्सन-यादृच्छिक (या कोई अन्य IO-आधारित नंबर जनरेटर) को सिंक्रनाइज़ कॉल करता है, बफर और आय भरता है।

(यदि आप ऐसा कुछ लागू करते हैं, तो इससे एक स्टैंडअलोन लाइब्रेरी बनाना बहुत अच्छा होगा।)

---

ध्यान दें कि randoms Mersenne यादृच्छिक से पहले से ही unsafeInterleaveIO का उपयोग करता है एक आलसी सूची तैयार करता है, लेकिन मैं कहेंगे सूची एक भी धागे से केवल भस्म हो के लिए है। और इसमें सुधार के लिए भी जगह है। यह unsafeInterleaveIO उपयोग करता है और के रूप में its comment में बताया गया है यह, कुछ भूमि के ऊपर है:

वहाँ असली ओवरहेड्स यहाँ हैं। उत्सुकता से भाग भरने और तत्वों को टुकड़े टुकड़े करने पर विचार करें।

Answer 3

मैं एक काफी नहीं रिलीज के लिए तैयार पैकेज hsrandom123Github कि यहाँ उपयोगी हो सकता है पर है। समानांतर गणनाओं के लिए उपयुक्त आरएनजी उपलब्ध कराने के लिए मैंने इस पैकेज को कार्यान्वित करना शुरू कर दिया है। यह the random123 C library से फिलॉक्स और थ्रीफ्री आरएनजी को दोहराता है (वहां भी विचारों का वर्णन करने वाला एक पेपर है)।

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

Answer 4

उत्तरों की पूर्णता के लिए, मुझे बताएं कि इस समस्या को हल करने के लिए मैं इस समय क्या कर रहा हूं।

गणना शुद्ध करने की कोशिश करने के बजाय, मैंने के बजाय async पैकेज का उपयोग करने का विकल्प चुना है।

यदि मैं शुद्ध होने के लिए अपने वर्तमान समाधान को संशोधित करने का निर्णय लेता हूं, तो मैं सबसे पहले फिलिप जेएफ द्वारा सुझाए गए समाधान का प्रयास करूंगा, इसलिए मैंने अपना जवाब स्वीकृत के रूप में चिह्नित किया है।

मेरे अगली चुनौती लगाना है काम का इष्टतम बेडौल अनुमान लगाने के लिए कैसे ताकि सूत्रण इसे ले बनाने के बजाय समय की मात्रा कम कर देता है अब :)