随机生成器意外行为

Question

我在使用 System.Random 库时遇到了一些我不完全理解的行为。下面的 shuffle 函数是 Fischer-Yates shuffle 的一个实现，它也可以作为一个没有替换的随机样本。例如。用列表调用 shuffle 并且列表的长度将打乱整个列表，但是用列表调用它并且数字 2 应该提取长度为 2 的随机样本。

import           Control.Monad               as M
import           Control.Monad.ST
import           Data.Vector.Unboxed         as VU
import           Data.Vector.Unboxed.Mutable as VUM
import           System.Random

go = do
  g <- newStdGen
  let (rand_vec1, g1) = randVector 10 g
  let (rand_vec2, g2) = randVector 10 g
  let (rand_sample1, g3) = shuffle rand_vec1 2 g
  let (rand_sample2, g4) = shuffle rand_vec1 2 g
  print rand_vec1
  print rand_vec2
  print rand_sample1
  print rand_sample2

randVector :: (RandomGen g) => Int -> g -> (VU.Vector Int, g)
randVector n = shuffle vector (VU.length vector) where
  vector = VU.enumFromN 0 n

shuffle :: (RandomGen g, Unbox a) => VU.Vector a -> Int -> g -> (VU.Vector a, g)
shuffle li size g = runST $ do
  vector <- VU.unsafeThaw li
  let n = VUM.length vector - 1
  let step g i = do
              let (j,g') = randomR (0,n) g
              VUM.swap vector i j
              return g'
  g' <- M.foldM step g [0..size-1]
  v' <- VU.unsafeFreeze vector
  let vec = VU.take size v'
  return (vec, g')

我注意到 rand_vec1 和 rand_vec2 总是相同的，这是意料之中的，因为使用了相同的随机数生成器。

然而，rand_sample1 和 rand_sample2 不同，即使它们都使用相同的随机生成器。更奇怪的是，超过一半的时间，但并非总是如此，rand_sample2 只包含从中采样的向量的前两个数字（如下例所示）。怎么会？示例输出：

[3,0,4,9,7,2,1,8,5,6]

[3,0,4,9,7,2,1,8,5,6]

[9,2]

[3,0]

（另外，感谢代码审查）

Answer 1

因为 shuffle 使用 unsafeThaw/Freeze 它实际上是在修改输入向量，即本例中的 rand_vec1。

尝试运行这个：

go = do
  g <- newStdGen
  let (rand_vec1, g1) = randVector 10 g
  print rand_vec1
  let (rand_vec2, g2) = randVector 10 g
  print rand_vec2
  let (rand_sample1, g3) = shuffle rand_vec1 2 g
  print rand_sample1
  print ("rand_vec1: ", rand_vec1)
  let (rand_sample2, g4) = shuffle rand_vec1 2 g
  print rand_sample2
  print ("rand_vec1: ", rand_vec1)

这是输出：

*Main> go
[7,0,3,5,2,6,9,8,1,4]
[7,0,3,5,2,6,9,8,1,4]
[0,3]
("rand_vec1: ", [0,3,7,5,2,6,9,8,1,4])
[3,7]
("rand_vec1: ", [3,7,0,5,2,6,9,8,1,4])

要回答你的第二个问题，简短的回答是 shuffle 返回的向量与（修改后的）输入向量共享相同的内存。

随机生成器意外行为

Random generator unexpected behavior

random

haskell

random-sample