So how come, there seems to be only 5 distinct generators coming ?
认为只有 5 台发电机是一种错觉。如果打印每个序列的第二个数字而不是第一个数字,您会得到以下结果:
random2ndFromSeed :: Int -> Int -> Int
random2ndFromSeed max seed =
let g0 = mkStdGen seed
(v1, g1) = randomR (0, max - 1) g0
(v2, g2) = randomR (0, max - 1) g1
in v2
λ>
λ> map (random2ndFromSeed 10) [1..40]
[6,9,3,8,1,4,8,3,6,9,3,8,1,4,8,3,6,9,3,8,1,4,8,3,6,9,3,8,1,4,8,3,6,9,3,8,1,4,8,3]
λ>
所以周期看起来是 8 而不是 5!
解决这个明显问题的一种方法是将标准生成器替换为三鱼一是设计较新,具有更好的统计特性。或者你也可以使用PCG-随机正如戴夫·康普顿所提到的。
import System.Random.TF
tfRandomFromSeed :: Int -> Int -> Int
tfRandomFromSeed max seed = let g0 = mkTFGen seed
in fst $ randomR (0, max - 1) g0
λ>
λ> map (tfRandomFromSeed 10) [1..40]
[4,5,6,7,5,3,3,0,0,4,2,8,0,4,1,0,0,1,3,5,6,4,3,6,4,0,3,6,4,0,2,4,5,9,7,3,8,5,2,4]
λ>
更一般地说,随机性的出现应该来自于生成器的重复应用next
功能。在这里,该函数仅对每个种子/序列应用一次,因此不要求随机性。
如何创建持久的二维随机场
从评论来看,实际需要的是二维空间中点的“随机”函数。如果玩家在一些随机游走之后返回到某个已经访问过的点,则期望找到与之前相同的随机值,并且这无需记住以前的随机值。
为了以某种方式实现这一点,让我们对随机值的统计特性有一些保证,我们需要使用单个种子和单个随机序列来实现;这就是我们的应用数学家testing.
我们需要两件事来产生这样一个持久的二维随机场:
- 一种将 2D 点映射到单个自然数的方法,用作随机序列的偏移量
- 一个可以有效访问的随机数生成器随意的每个序列的点
将 2D 点映射到自然数
例如,这可以通过利用康托配对函数来自初等集合论。
我们可以使用这段代码:
-- limited to first quadrant, x >= 0 and y >= 0:
cantor1 :: Int -> Int -> Int
cantor1 x y = y + (let s = x + y in div (s * (s+1)) 2)
-- for all 4 quadrants:
cantor :: (Int, Int) -> Int
cantor (x,y) =
let quadrant
| x >= 0 && y >= 0 = 0
| x < 0 && y >= 0 = 1
| x < 0 && y < 0 = 2
| x >= 0 && y < 0 = 3
| otherwise = error "cantor: internal error #1"
cant1
| x >= 0 && y >= 0 = cantor1 x y
| x < 0 && y >= 0 = cantor1 (-1-x) y
| x < 0 && y < 0 = cantor1 (-1-x) (-1-y)
| x >= 0 && y < 0 = cantor1 x (-1-y)
| otherwise = error "cantor: internal error #2"
in
4*cant1 + quadrant
安排任意访问
完成这个初步步骤后,我们必须认识到常规 Haskell 随机数生成 API 不太适合手头的任务。
API 通过以下方式提供对随机序列的顺序访问:next功能。但没有随意的访问,例如 C++ 随机库中提供的discard功能。和经典的一元风格使用莫纳德随机数接口都是关于顺序访问的。它基本上就像一个状态单子。
此外,使用某些随机数生成器,根本不可能有效访问序列的任意点。在这种情况下,C++discard
函数只是使用昂贵的单步执行来到达想要的点。
幸运的是,有一个Haskell 实现Pierre L'Ecuyer 等人MRG32k3a随机数生成器。
使用 MRG32k3a,对随机序列的任意访问可归结为 2 个伽罗瓦域中小矩阵的幂运算。感谢古老而受人尊敬的印度求幂算法,这可以在 O(log n) 时间内完成。
github中的MRG32k3a代码没有提供完整的Haskell风格的接口,例如RandomGen
实例,所以我们必须在它周围添加一些包装器代码。
首先,我们需要一些导入条款:
import System.Random
import System.Random.TF
import qualified Data.List as L
import qualified Text.Printf as TP
import qualified Data.Text as TL
import qualified Data.ByteString as BS
import qualified Data.Text.Encoding as TSE
import qualified Crypto.Hash.SHA256 as SHA
import qualified System.Random.MRG32K3A.Simple as MRG
然后是包装器代码本身:
newtype MRGen = MRGen MRG.State -- wrapper type for MRG32k3a generator
deriving Show
instance RandomGen MRGen where
genRange = let mrg32k3a_m1 = ((2::Integer)^32 - 209)
in const (0::Int, fromIntegral (mrg32k3a_m1 - 1))
next (MRGen g0) = let (v, g1) = MRG.next g0
in ((fromIntegral v)::Int, MRGen g1)
split (MRGen g0) = let g1 = MRG.advance ((2::Integer)^96) g0
in (MRGen g0, MRGen g1)
mkMRGen :: Int -> MRGen
mkMRGen userSeed = let longSeed = hashSeed userSeed
g0 = MRG.seed longSeed
in MRGen g0
ranSeek :: MRGen -> Integer -> MRGen
ranSeek (MRGen g0) count = let g1 = (MRG.advance count g0) in MRGen g1
hashSeed :: Int -> Integer
hashSeed userSeed =
let str = "MRG32k3a:" ++ (TP.printf "0x%x" userSeed)
bytes = (TSE.encodeUtf8 . TL.pack) $ str
ints = (map (fromIntegral) $ BS.unpack (SHA.hash bytes)) :: [Integer]
in
L.foldl' (\acc d -> acc*256 + d) 0 (take 20 ints)
功能mkMRGen
类似于mkStdGen
。对随机序列的任意访问由函数提供ranSeek :: MRGen -> Integer -> MRGen
在 O(log n) 时间内。
边注:我正在重新散列用户提供的种子mkMRGen
。这是因为 github 包使用其种子作为随机序列的偏移量。因此,为了避免小用户种子的序列重叠风险,我需要从用户种子生成大量数字。
感谢我们的RandomGen
例如,我们可以访问常用功能,例如随机 :: RandomGen g => g -> (a, g)。例如,我们可以从一个简单的数据生成一个 Double 类型的二维随机字段Int
像这样的种子:
randomDoubleField :: Int -> (Int, Int) -> Double
randomDoubleField userSeed (x,y) =
let k = 1 -- number of needed random values per plane point
g0 = mkMRGen userSeed
g1 = ranSeek g0 (fromIntegral (k * cantor (x,y)))
in fst (random g1)
现在我们有了这个小工具包,我们可以编写一个小测试程序,为零点的邻域绘制一些随机景观,每个 2D 点一个字符。
比如说,字符“t”代表一种类型的树,“T”代表另一种类型的树。树的缺失用减号表示。
主要程序:
randomCharField :: Int -> (Int, Int) -> Char
randomCharField userSeed (x,y) =
let n = floor (8.0 * randomDoubleField userSeed (x,y) )
in "------tT" !! n
rowString :: Int -> Int -> Int -> String
rowString userSeed size y =
let xRange = [(-size) .. size]
in map (randomCharField userSeed) [ (x,y) | x <- xRange ]
main = do
let userSeed = 42
size = 6
yRange = [(-size) .. size]
mapM_ (putStrLn . (rowString userSeed size)) yRange
程序输出:
--t-T----TT-t
------t-----T
-T--T--T-----
--t-T--tTTT--
--T--t---T---
t-Tt------t--
-T-----t-T---
-T-t-t----T--
tT-tT---tT--t
---TTt---t---
-------T---t-
--t---------t
-tT-t---t----
优化注意事项:如果性能是一个问题,您可能想要移动(mkMRGen userSeed)
计算脱离循环。