4

未知の長さのリストからランダムな要素を選択するための2つの関数を作成しました。1つ目は（サイズ1のリザーバーを使用した）リザーバーサンプリングを使用し、2つ目はリストの長さを取得してランダムなインデックスを選択して返します。何らかの理由で、前者の方がはるかに高速です。

最初の関数は、単一の走査を使用し、確率（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

2番目のバージョンは、リストを1回トラバースしてその長さを取得し、次に0と入力リストの長さ（-1）の間のインデックスを選択して、要素の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

これら2つの関数のベンチマークに使用するコードは次のとおりです。

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

言い換えると、最初の関数は2番目の関数よりも約200倍高速です。ランタイムは、主に乱数の生成とリストトラバーサルの数（1対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、サンクを返すだけです。それはすぐにできます。

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 $! ...

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への呼び出しが1回だけで済み、リザーバーサンプリングでは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もちろん、1世代しか使用しないため、時間は測定可能なほど変化しません）。約9倍のスピードアップ。これは、疑似ランダム生成が支配的な要因であることを示しています。

于 2012-12-26T00:30:36.683 に答える