4

我编写了两个函数来从未知长度的列表中选择一个随机元素。第一个使用水库采样（水库大小为 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的预期遍历次数：

-- 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

这是我用于对这两个函数进行基准测试的代码：

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

这是一个剥离的输出：

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

换句话说，第一个函数比第二个函数快大约 200 倍。我预计运行时间主要受随机数生成和列表遍历次数（1 vs. 1.5）的影响。还有什么其他因素可以解释如此巨大的差异？

4

1 回答 1

9

您的基准操作实际上并未评估结果，

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

只得到一个新的StdGen并返回一个 thunk。这很直接。

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

计算列表的长度，然后返回一个 thunk，这当然要慢得多。

迫使双方评估结果，

return $! ...

使length使用版本更快，

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

（在通过打印其总和来强制对输入列表进行评估之后），因为这只需要一次调用 PRNG，而水库采样使用length list - 1调用。

如果使用比 a 更快的 PRNG，差异可能会更小StdGen。

实际上，使用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当然，时间不会发生可测量的变化，因为它只使用了一代）。大约九倍的加速，这表明伪随机生成是主导因素。

于 2012-12-26T00:30:36.683 回答