懒序列分块是否确定？

Question

我知道懒序列可以分块进行处理。也就是说，如果我的程序需要一个懒序列中的 n 个元素，可能会实现多于 n 个元素。

我能否假设，如果我在同一版本的 Clojure 中第二次运行同一代码，将实现完全相同的元素？我认为是的，但我不想在没有了解的情况下假设这一点。

(以下附加信息是供感兴趣的人参考的，但我觉得了解我的具体使用场景并不是回答这个问题的必要条件。所以 请随意跳过此段。我在运行使用伪随机数发生器的模拟。这涉及随机游走，如果游走遇到“目标”则被截断。提前将游走作为一个懒序列生成是很方便的，并在找到目标时停止实现其元素。通常我会丢弃中间结果，如原始随机游走。他们存在于数据结构中的一种时间，但是最终没有使用它们。然而，我 occasionally 希望能够回过头去重新运行模拟，有时是为了检查中间结果。存储我用于模拟运行的种子是足够的，并使用它将随机数发生器设置到相同的状态。但是，分块可能会导致随机数发生器被调用比必要次数还要多。这没有关系，但如果分块除了我的代码和 Clojure 版本之外还取决于其他因素，那么重新运行带有相同种子的模拟不一定能保证产生相同的结果。目前这并不是一个大问题。我可以很容易地将中间数据转换为非懒的，而不会带来太多的性能损失。但是，我仍然想知道这是否是必要的。)

Answer 1

你不应该假设懒序列实现的任何情况，所以这不是可以保证的。

如果你想要控制生成过程，请使用循环/递归或reducing等功能来实现，或者使用其他此类技术来获得这种控制。

Comments

好的！我会这么做。谢谢。

Answer 2

这对我来说没有意义

这可能意味着使用相同的种子重新运行模拟并不一定会产生相同的结果

函数调用次数似乎无关紧要（除了例如性能[例如昂贵的函数计算]或其他情况，如纠缠副作用....）。因为你正在从序列中抽取结果，并在达到某个标准时停止，生成这些结果的过程应该可以使用相同的输入重现。如果这个迭代过程依赖于自己的PRNG，并且初始化时使用特定的种子值，并且状态转换函数依赖于不可变上下文和PRNG的当前状态（例如“功能上纯净”，但有状态PRNG的良性副作用），那么我看不出你怎么可能创建不同的状态序列。如果块生成决定比必要多运行22次，这不会影响前面的10次。这10个值（比如第10个在消耗序列时达到停止标准）被缓存，并且与任何后续值完全独立，因此序列的不可变性得到保留。只要为你生成的每个序列隔离一个PRNG，我相信你应该具有完全的独立性和可重现性（当控制因素如PRNG实现、运行时间、clojure版本等时）。

我已经从事离散事件模拟工作（主要是确定性模拟，尽管偶尔会使用随机初始条件）超过十年。可重复性非常重要，尤其是对于比较验证，以及您提到的对系统演变（例如中间状态）的细致检查。如果您控制种子、伪随机数发生器实例以及之前提到的一些其他因素，这将导致可重复的历史记录。

如前所述，如果您仍然担心，您可以使用迭代和转播/归约/累积来定义一个不会被分块（或生成中间序列）的急切迭代过程，从而保持熟悉、性能和控制。我通常出于性能原因选择这条路线，尽管我的模拟在生成的“帧”基数上通常较小，但状态转换函数的复杂性更高。

Comments

谢谢@Tom。我想没有说清楚的是，我想在不重新初始化伪随机数发生器的情况下运行一系列不同的模拟（具有不同的参数）。(不重新初始化伪随机数发生器是一种让伪随机数发生器确保新数字与前面的数字无关的好方法。也就是说，在PRNG可以信任做这个到什么程度——这又是另一个话题。)

假设我使用一个种子初始化了伪随机数发生器。然后我进行一次模拟运行，生成一个惰性序列steps1。我做类似于'take 10000'的事情。每步都有一个伪随机数发生器调用，所以现在我已经用10000+k个状态推进了伪随机数发生器，其中k是由于分块而产生的额外处理。然后，不重新种子但使用相同的伪随机数发生器，从这个点开始进行另一个不同的模拟运行，创建一个惰性序列steps2，并在它上面运行'take 10000'。然后，我丢弃steps2，但稍后我想更仔细地检查它，所以再次运行第一个模拟（或者如果我知道k是多少，可能只是将伪随机数发生器推进10000+k次），然后再运行第二个模拟以重新创建steps2。

但是根据@alexmiller的说法，我不应该假设k会始终相同。如果k可能不同，那么即使在第二个模拟之前运行第一个模拟也不能保证我确实重新创建了steps2。

如果您不使用惰性，那么您将确切知道伪随机数发生器被调用了多少次以创建steps1——在这个例子中是10000次——所以要重新创建steps2，您只需要给伪随机数发生器一个已知的种子，然后丢弃前10000个数字，这不需要很长时间。然后，您可以进行第二个模拟以创建steps2。(可能提供的细节超过了所需。)

另一种选择是读取伪随机数发生器的状态并将其存储起来，然后在使用它来重新创建运行时使用该状态进行初始化。我正在使用一个内部状态比用来初始化它的长种子更大的PRNG (Well19937c)。

（我昨晚去除了一部分惰性。我想我可能会从中看到一点性能上的好处，但因为大多数处理时间都在每个步骤都运行的例程中，所以差异很小。）

---

是的，我现在明白了。你试图将其作为流来从中提取，这样就创建了一个隐含的依赖关系，期望你的PRNG将受到分块重绘的可预测影响。我不认为这种做法有什么特别的优势（除了更有用的伪随机数分布之外），与在运行之间计算新的种子并初始化相比。我想，你只有一个种子需要记住，以生成任意数量的派生序列。按照这种方法，为了发现第n个序列之后会发生什么，比如说步骤_n，现在你必须运行所有前驱来达到起始点，以观察你感兴趣的那个序列。我可能只想在每个序列的结尾计算或推导出一个种子，用作下一个的初始化，这样就防止了你捕获内部状态。你可以在序列生成之间引入一些隐含的依赖关系，但你在一个区间上建立了一个隐含的种子分布，并以随机游走的方式从中采样......我认为采样的质量不会太有偏见，但可能因人而异。

我认为另一种选择（为了保留和最大化惰性）是按照stuart的回答取消分块 https://stackoverflow.com/a/3409568。只是关闭分块 :)

---

我过于小心以避免运行之间的可能相关性，但我宁愿这样做。我同意每次生成新的种子，例如使用相同的PRNG，是合理的。：（我宁愿不通过其他方式生成多个种子，例如从系统时间和类似的事物中，以免如果这样很快发生，我可能会意外地得到相同的种子。）

请注意，从PRNG生成下一个种子作为长整数将624位的WELL19937c状态降低到运行之间的64位状态。在实践中可能不会产生影响，但如果是这样的话，从上一个624位状态继续会更好。

我受到L'Ecuyer等人《用于并行计算机的随机数》的影响。
https://www.sciencedirect.com/science/article/pii/S0378475416300829
我没有并行运行模拟，但其中的一些原则是相关的。但是，我又可能在过度做了。

我也在给PRNG设定种子后丢弃了大约两千个数字，因为如果你真的很不幸，WELL发生器可能开始在一个不太随机的状态，一段时间。但我认为WELL19937c不应该有这个问题。（https://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf ）

取消分块：哇，这个很棒。谢谢。

---

> 注意，从 PRNG 生成下一个种子作为长值，会将 624 位的状态（对于 WELL19937c）减小到运行之间的 64 位状态。

有趣。看起来 Apache Commons Math API 实现允许您获取整数数组并用它来保持状态，因此如果您想向前保持状态，将整数数组作为种子存储而不是降级到 long 空间是可行的，这样可以防止精度丢失。谢谢您的笔记。

---

谢谢。是的，我开始思考这个问题，当我使用一个种子生成了一系列长的实验后。我想我必须循环 PRNG 几十万次才能重新运行实验中的一个后续集合。

我还没有看到读取状态的函数。你在看哪个类？我可能遗漏了相关接口或者类继承结构中的某个东西。你是否指的是 `Abstract Well` 中的 `v` “字节数组”字段？我将不得不检查源代码，这似乎可能是我需要的。或者你在看 Apache Commons Math 4？这似乎仍在建设中，所以我一直在使用 Math 3.6.1，它的组织结构非常不同。（请随意不回答——这不是你的工作为我查找 Apache Commons 的信息。）

---

getStateInternal() 位于 Apache Commons PRNGs 的发展版本中。