水库采样的性能与获取列表长度和选择随机元素的比较

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:

-- 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 对 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并返回一个 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调用。

如果 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 时间没有明显变化，因为它只使用一代)。大约九倍的加速，这表明伪随机生成是主要因素。