हास्केल

Question

में सूची से प्रतिस्थापन के बिना यादृच्छिक नमूना लेने का बेहतर तरीका मुझे लंबी सूची से प्रतिस्थापन के बिना यादृच्छिक नमूना लेने की आवश्यकता है (प्रत्येक तत्व केवल नमूना में एक बार होता है)। मैं नीचे दिए गए कोड का उपयोग कर रहा हूं, लेकिन अब मैं जानना चाहता हूं:

1. क्या कोई लाइब्रेरी फ़ंक्शन है जो यह करता है?
2. मैं इस कोड को कैसे सुधार सकता हूं? (मैं एक हास्केल शुरुआती हूं, इसलिए लाइब्रेरी फ़ंक्शन होने पर भी यह उपयोगी होगा)।

नमूनाकरण का उद्देश्य जनसंख्या में नमूना का विश्लेषण करने से निष्कर्षों को सामान्यीकृत करने में सक्षम होना है।

import System.Random 

-- | Take a random sample without replacement of size size from a list. 
takeRandomSample :: Int -> Int -> [a] -> [a] 
takeRandomSample seed size xs 
    | size < hi = subset xs rs 
    | otherwise = error "Sample size must be smaller than population." 
    where 
     rs = randomSample seed size lo hi 
     lo = 0 
     hi = length xs - 1 

getOneRandomV g lo hi = randomR (lo, hi) g 

rsHelper size lo hi g x acc 
    | x `notElem` acc && length acc < size = rsHelper size lo hi new_g new_x (x:acc) 
    | x `elem` acc && length acc < size = rsHelper size lo hi new_g new_x acc 
    | otherwise = acc 
    where (new_x, new_g) = getOneRandomV g lo hi 

-- | Get a random sample without replacement of size size between lo and hi. 
randomSample seed size lo hi = rsHelper size lo hi g x [] where 
(x, g) = getOneRandomV (mkStdGen seed) lo hi 

subset l = map (l !!) 

Answer 1

यहां एक त्वरित 'बैक-ऑफ-द-लिफाफा' क्या डैनियल फिशर उसकी टिप्पणी में सुझाव दिया, का उपयोग कर के कार्यान्वयन है मेरे पसंदीदा PRNG (MWC यादृच्छिक):

{-# LANGUAGE BangPatterns #-} 

module Sample (sample) where 

import Control.Monad.Primitive 
import Data.Foldable (toList) 
import qualified Data.Sequence as Seq 
import System.Random.MWC 

sample :: PrimMonad m => [a] -> Int -> Gen (PrimState m) -> m [a] 
sample ys size = go 0 (l - 1) (Seq.fromList ys) where 
    l = length ys 
    go !n !i xs g | n >= size = return $! (toList . Seq.drop (l - size)) xs 
        | otherwise = do 
         j <- uniformR (0, i) g 
         let toI = xs `Seq.index` j 
          toJ = xs `Seq.index` i 
          next = (Seq.update i toI . Seq.update j toJ) xs 
         go (n + 1) (i - 1) next g 
{-# INLINE sample #-} 

यह काफी है ए (terse) sample() के आर के आंतरिक सी संस्करण के कार्यात्मक पुनर्लेखन के रूप में इसे प्रतिस्थापन के बिना बुलाया जाता है।

sample एक रिकर्सिव वर्कर फ़ंक्शन पर केवल एक रैपर है जो वांछित नमूना आकार तक पहुंचने तक जनसंख्या को बढ़ा देता है, केवल उन शफल तत्वों को लौटता है। इस तरह के समारोह को लिखना सुनिश्चित करता है कि जीएचसी इसे रेखांकित कर सकता है।

यह उपयोग करने के लिए आसान है:

*Main> create >>= sample [1..100] 10 
[51,94,58,3,91,70,19,65,24,53] 

एक उत्पादन संस्करण आदेश समय में कटौती करने के लिए के बजाय एक परिवर्तनशील वेक्टर Data.Sequence की तरह कुछ का उपयोग करना चाहें जीसी कर बिताया।

Answer 2

मुझे लगता है कि यह करने के लिए एक मानक तरीका एक निश्चित-आकार बफर पहले एन तत्वों के साथ प्रारंभ रखने के लिए है, और तत्व i'th प्रत्येक के लिए, मैं> = एन, ऐसा करते हैं:

1. पिक एक यादृच्छिक संख्या, जे, 0 और मैं के बीच।
2. यदि जे < एन तो वर्तमान में के साथ बफर में j'th तत्व को प्रतिस्थापित करें।

आप प्रेरण द्वारा सत्यता साबित कर सकते हैं:

यह स्पष्ट रूप से नमूने के तौर पर (मुझे लगता है क्रम अप्रासंगिक है) यदि आप केवल एन तत्व उत्पन्न करता है। अब मान लीजिए कि यह तत्व के लिए सच है। इसका मतलब है कि बफर में होने वाले किसी भी तत्व की संभावना एन/(i + 1) है (मैं 0 पर गिनती शुरू करता हूं)।

यादृच्छिक संख्या चुनने के बाद, संभावना है कि i + 1` तत्व बफर में है N/(i + 2) (j 0 और i + 1 के बीच है, और उनमें से एन अंत में हैं बफर)। दूसरों के बारे में क्या?

P(k'th element is in the buffer after processing the i+1'th) = 
P(k'th element was in the buffer before)*P(k'th element is not replaced) = 
N/(i+1) * (1-1/(i+2)) = 
N/(i+2) 

यहां कुछ कोड है जो मानक (धीमी) प्रणाली का उपयोग करके नमूना आकार की जगह में करता है। यादृच्छिक।

import Control.Monad (when)                          
import Data.Array                             
import Data.Array.ST                            
import System.Random (RandomGen, randomR)                       

sample :: RandomGen g => g -> Int -> [Int] -> [Int]                    
sample g size xs =                             
    if size < length xs                            
    then error "sample size must be >= input length"                     
    else elems $ runSTArray $ do                          
    arr <- newListArray (0, size-1) pre                       
    loop arr g size post                           
    where                               
    (pre, post) = splitAt size xs                         
    loop arr g i [] = return arr                         
    loop arr g i (x:xt) = do                          
     let (j, g') = randomR (0, i) g                        
     when (j < size) $ writeArray arr j x                       
     loop arr g' (i+1) xt