3

我有一个函数，它采用一系列随机数/浮点数，并使用它们来生成一个值/结构（即，采用随机速度和球被抛出的点的位置并输出它会降落的坐标） . 我需要连续生成数千个。

我实现所有东西的方式是每个计算都接受一个 stdGen，用它来生成几个数字，并传递一个新的 stdGen 以允许它链接到另一个。

为了对 10000 个项目执行此操作，我制作了一个列表，generate_item n从中基本上输出一个(value,gen)元组（该值是我要计算的值），其中的值gen是从获取的计算中递归输出的 stdGen值来自generate_item n-1

但是，该程序在大约一千个结果左右时似乎爬行得慢得不切实际。而且似乎绝对不可扩展。这可能与我将所有generate_item结果都存储在内存中这一事实有关吗？

或者有没有比我上面描述的更惯用的方法在 Haskell 中使用 Monads 或其他方法来解决这个问题？

请注意，即使在 ruby​​ 和 python 等高级脚本语言中，从随机值生成算法的代码也会在几秒钟内生成 10k；这些计算几乎不密集。

代码

-- helper functions that take in StdGen and return (Result,new StdGen)
plum_radius :: StdGen -> (Float,StdGen)
unitpoint   :: Float -> StdGen -> ((Float,Float,Float),StdGen)
plum_speed  :: Float -> StdGen -> (Float,StdGen)

-- The overall calculation of the value
plum_point  :: StdGen -> (((Float,Float,Float),(Float,Float,Float)),StdGen)
plum_point gen  = (((px,py,pz),(vx,vy,vz)),gen_out)
  where
    (r, gen2)         = plum_radius gen
    ((px,py,pz),gen3) = unitpoint r gen2
    (s, gen4)         = plum_speed r gen3
    ((vx,vy,vz),gen5) = unitpoint s gen4
    gen_out           = gen5

-- Turning it into some kind of list
plum_data_list  :: StdGen -> Int -> (((Float,Float,Float),(Float,Float,Float)),StdGen)
plum_data_list seed_gen 0  = plum_point seed_gen
plum_data_list seed_gen i  = plum_point gen2
  where
    (_,gen2)  = plum_data_list seed_gen (i-1)

-- Getting 100 results
main = do
  gen <- getStdGen
  let data_list = map (plum_data_list gen) [1..100]
  putStrLn List.intercalate " " (map show data_list)
4

3 回答 3

6

考虑只使用 mersenne-twister 和vector-random包，它们专门针对生成大量高质量随机数据进行了优化。

列表不适合分配大量数据——最好使用打包表示——除非你正在流式传输。

于 2013-03-07T10:08:34.560 回答
5

首先，您所描述的模式——获取一个StdGen然后返回一个带有值的元组，另一个StdGen被链接到下一个计算中——正是Statemonad 编码的模式。重构代码以使用它可能是开始熟悉一元模式的好方法。

至于你的性能问题，StdGen是出了名的慢。我对这些东西做的不多，但我听说mersenne twister更快。

但是，您可能还想发布您的代码，因为在您生成大型列表的情况下，根据您的操作方式，懒惰确实对您有利或不利。但是如果没有看到你在做什么，很难给出具体的建议。一个经验法则，以防万一你来自另一种函数式语言，如 Lisp——在生成列表（或其他惰性数据结构——例如树，但不是 a Int）时，避免尾递归。它更快的直觉不会转移到惰性语言。例如使用（没有我会在实践中实际使用的单子风格编写）

randoms :: Int -> StdGen -> (StdGen, [Int])
randoms 0 g = (g, [])
randoms n g = let (g',  x)  = next g
                  (g'', xs) = randoms (n-1) g'
              in (g'', x : xs)

这将允许“流式传输”结果列表，因此您可以在生成后面的部分之前访问它的早期部分。（在这种情况下，它有点微妙，因为访问结果StdGen必须生成整个列表，所以在你使用完列表之前，你必须小心避免这样做——我希望有一个快速的随机生成器支持良好的split操作，那么您可以完全不必返回生成器）。

哦，以防万一你在处理 monads 时遇到了麻烦，这是上面用 state monad 编写的函数：

randomsM :: Int -> State StdGen [Int]
randomsM 0 = return []
randomsM n = do
    x <- state next
    xs <- randomsM (n-1)
    return (x : xs)

看到信件了吗？

于 2013-03-07T09:18:03.630 回答
4

其他张贴者有优点，StdGen性能不是很好，您可能应该尝试使用 State 而不是手动传递生成器。但我认为最大的问题是你的plum_data_list功能。

它似乎旨在进行某种查找，但由于它是在没有任何记忆的情况下递归实现的，因此您所做的调用必须递归到基本情况。也就是说，plum_data_list seed_gen 100需要随机生成器 fromplum_data_list seed_gen 99等，直到plum_data_list seed_gen 0。当您尝试生成这些值的列表时，这将为您提供二次性能。

可能更惯用的方法是让plum_data_list seed_gen生成一个无限的点列表，如下所示：

plum_data_list :: StdGen -> [((Float,Float,Float),(Float,Float,Float))]
plum_data_list seed_gen = first_point : plum_data_list seed_gen'
  where
    (first_point, seed_gen') = plum_point seed_gen

然后您只需将代码修改为main类似take 100 $ plum_data_list gen的内容，即可恢复线性性能。

于 2013-03-07T13:15:15.610 回答