8

より長いリストから、置き換えなしでランダムなサンプルを取得する必要があります (各要素はサンプル内で 1 回だけ発生します)。以下のコードを使用していますが、知りたいのですが：

  1. これを行うライブラリ関数はありますか？
  2. このコードを改善するにはどうすればよいですか? （私はHaskell初心者なので、ライブラリ関数があってもこれは役に立ちます）。

サンプリングの目的は、サンプルの分析から得られた結果を母集団に一般化できるようにすることです。

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 !!)
4

2 に答える 2

6

これは、ダニエル・フィッシャーが私の好みのPRNG（mwc-random）を使用して、彼のコメントで提案したものの簡単な「封筒裏の計算」の実装です。

{-# 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 #-}

これは、Rの内部Cバージョンの（簡潔な）機能的な書き直しであり、sample()置き換えなしで呼び出されます。

sampleは、目的のサンプルサイズに達するまで母集団を段階的にシャッフルし、その数のシャッフルされた要素のみを返す再帰ワーカー関数の単なるラッパーです。このように関数を書くと、GHCがそれをインライン化できるようになります。

使い方は簡単です：

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

Data.Sequence本番バージョンでは、GCの実行に費やす時間を削減するために、代わりに可変ベクトルのようなものを使用したい場合があります。

于 2012-12-08T21:39:59.313 に答える
2

これを行う標準的な方法は、最初の N 要素で初期化された固定サイズのバッファーを保持し、i 番目の要素ごとに i >= N であると思います。

  1. 0 から i までの乱数 j を選びます。
  2. j < N の場合、バッファ内の j 番目の要素を現在の要素に置き換えます。

帰納法によって正しさを証明できます。

N個の要素しかない場合、これは明らかにランダムサンプルを生成します（順序は関係ないと思います）。ここで、i 番目の要素まで true であるとします。これは、バッファーに要素が存在する確率が N/(i+1) であることを意味します (0 からカウントを開始します)。

乱数を選択した後、i+1 番目の要素がバッファーにある確率は N/(i+2) (j は 0 と i+1 の間であり、そのうちの N 個がバッファーに格納されます) です。他の人はどうですか？

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)

サンプルサイズのスペースで、標準の (遅い) System.Random を使用してそれを行うコードを次に示します。

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
于 2012-12-10T05:27:29.173 に答える