저수지 샘플링 대 목록의 길이를 얻고 무작위 원소를 채취하는 것

Question

나는 알 수없는 길이의 목록에서 임의의 원소를 선택하는 두 가지 함수를 작성했다. 첫 번째는 저수지 표본 추출 (크기가 1 인 저수지)을 사용하고 두 번째 표는 임의 색인을 선택하여 반환하는 목록의 길이를 가져옵니다. 웬일인지, 전자는 훨씬 빠릅니다.

첫 번째 함수는 단일 순회를 사용하고 각 요소를 확률 (1/i)로 선택합니다. 여기서 i는 목록의 요소 색인입니다. 결과적으로 각 요소를 선택하는 확률이 높아집니다.

pickRandom :: [a] -> IO a 
pickRandom [] = error "List is empty" 
pickRandom (x:xs) = do 
    stdgen <- newStdGen 
    return (pickRandom' xs x 1 stdgen) 

-- Pick a random number using reservoir sampling 
pickRandom' :: (RandomGen g) => [a] -> a -> Int -> g -> a 
pickRandom' [] xi _ _ = xi 
pickRandom' (x:xs) xi n gen = 
    let (rand, gen') = randomR (0, n) gen in 
    if (rand == 0) then 
    pickRandom' xs x (n + 1) gen' -- Update value 
    else 
    pickRandom' xs xi (n + 1) gen' -- Keep previous value 

번째 버전은 그 길이를 얻기 위해 일단 목록을 통과하고 동일한 확률 다시, 요소의 하나 얻을 0 입력리스트 (-1)의 길이 사이의 인덱스를 픽업. 목록 1.5의 탐색의 예상 번호 :

benchmarking Using reservoir 
mean: 82.72108 ns, lb 82.02459 ns, ub 83.61931 ns, ci 0.950 

benchmarking Using length 
mean: 17.12571 ms, lb 16.97026 ms, ub 17.37352 ms, ci 0.950 

에서 :

여기

main :: IO() 
main = do 
    gen <- newStdGen 
    let size = 2097152 
     inputList = getRandList gen size 
    defaultMain [ bench "Using length" (pickRandomWithLen inputList) 
       , bench "Using reservoir" (pickRandom inputList) 
       ] 

가 제거 출력 : 여기에

-- Traverses the list twice 
pickRandomWithLen :: [a] -> IO a 
pickRandomWithLen [] = error "List is empty" 
pickRandomWithLen xs = do 
    gen <- newStdGen 
    (e, _) <- return $ randomR (0, (length xs) - 1) gen 
    return $ xs !! e 

나는이 두 가지 기능을 벤치마킹에 사용하는 코드입니다 다른 용어로, 첫 번째 기능은 두 번째 기능보다 약 200 배 빠릅니다. 나는 런타임이 난수 생성과리스트 횡단 수 (1 대 1.5)에 의해 주로 영향을받을 것으로 예상했다. 그러한 큰 차이를 설명 할 수있는 다른 요인은 무엇입니까?

귀하의 벤치 마크 행동이 실제로 결과를 평가하지 않는

Answer 1

,

pickRandom :: [a] -> IO a 
pickRandom [] = error "List is empty" 
pickRandom (x:xs) = do 
    stdgen <- newStdGen 
    return (pickRandom' xs x 1 stdgen) 

는 새로운 StdGen을 얻고 썽크를 반환합니다. 꽤 즉각적입니다.

pickRandomWithLen :: [a] -> IO a 
pickRandomWithLen [] = error "List is empty" 
pickRandomWithLen xs = do 
    gen <- newStdGen 
    (e, _) <- return $ randomR (0, (length xs) - 1) gen 
    return $ xs !! e 

은 목록의 길이를 계산 한 다음 썽크를 반환합니다. 물론 그 속도는 훨씬 느립니다. 그 결과를 평가하기 위해 모두 강제

,

return $! ... 

는 (입력리스트 강제 후 그 합을 인쇄하여 전에 평가되어야한다)

benchmarking Using length 
mean: 14.65655 ms, lb 14.14580 ms, ub 15.16942 ms, ci 0.950 
std dev: 2.631668 ms, lb 2.378186 ms, ub 2.937339 ms, ci 0.950 
variance introduced by outliers: 92.581% 
variance is severely inflated by outliers 

benchmarking Using reservoir 
collecting 100 samples, 1 iterations each, in estimated 47.00930 s 
mean: 451.5571 ms, lb 448.4355 ms, ub 455.7812 ms, ci 0.950 
std dev: 18.50427 ms, lb 14.45557 ms, ub 24.74350 ms, ci 0.950 
found 4 outliers among 100 samples (4.0%) 
    2 (2.0%) high mild 
    2 (2.0%) high severe 
variance introduced by outliers: 38.511% 
variance is moderately inflated by outliers 

훨씬 빠르게 length 사용 버전을 만드는 왜냐하면 저수지 샘플링은 length list - 1 호출을 사용하는 반면 PRNG에 대한 호출은 한 번만 필요하기 때문입니다.

StdGen보다 빠른 PRNG를 사용하면 차이가 줄어들 것입니다.System.Random.Mersenne 대신 StdGen의를 사용하여 실제로

은 (pickRandom'는 IO a 결과 유형이 있어야하며 특정 범위에서 어떤 세대를 제공하지 않습니다 만 기본 범위는 집어 요소 조금의 분포를 기울입니다,하지만 이후 우리는 관심이 있기 때문에 의사 난수 생성에 필요한 시간, 즉 저수지 샘플링 시간이

mean: 51.83185 ms, lb 51.77620 ms, ub 51.91259 ms, ci 0.950 
std dev: 482.4712 us, lb 368.4433 us, ub 649.1758 us, ci 0.950 

로 떨어진다) 중요하지 그것은 단지 하나를 사용하기 때문에합니다 (pickRandomWithLen 시간은 물론, 잴 변경되지 않습니다 세대). 약 9 배 빠른 속도로 의사 랜덤 생성이 지배적 인 요소임을 보여줍니다.