惰性序列分块是否确定性？

Question

我知道惰性序列可以分块处理。也就是说，如果我的程序需要从惰性序列中处理n个元素，实现的可能不止n个。

当我以相同的代码在相同的Clojure版本中再次运行时，我可以假设确实实现了相同的元素吗？我认为可以，但我不想在没有了解的情况下做出假设。

（以下包含额外的信息，供有兴趣的人士了解为什么这很重要，但不知道我的使用案例并不意味着必须了解这一点。所以 请随时跳过此段。我正在运行使用伪随机数发生器的模拟。这些模拟包括如果随机游走遇到“目标”则截断的随机游走。预先生成作为惰性序列的游走是方便的，并在找到目标时停止实现其元素。通常，我会丢弃原始随机游走的中间结果。它们在某个时间存在于数据结构中，但最终并没有使用它们。然而，我有时想能够回溯并重新运行模拟，以检查中间结果。存储模拟运行中使用的种子很容易，并使用它来设置随机数发生器的起始状态。然而，分块可能会使随机数发生器被调用次数比实际上需要的多。这是可以接受的，但如果分块可以根据除我的代码和Clojure版本之外的其他因素变化，那么重新运行具有相同种子的模拟可能无法保证产生相同的结果。这目前并不是一个大问题。我可以在不影响性能的情况下轻松地将中间数据变为非惰性。然而，我仍然想知道这一点是否必要。）

Answer 1

不应假设关于惰性序列何时被实现任何事情，所以这并不保证。

如果您想要对生成过程中的控制，请使用循环/递归或通过reduced进行reduce，或使用其他此类技术来获取控制权。

Comments

好的！  会做的。  谢谢。

Answer 2

这对我来说没有意义

这意味着重新运行具有相同种子的模拟不一定能保证产生相同的结果

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

我已经从事离散事件模拟工作超过十年（主要是确定性模拟，尽管偶尔有随机初始条件）。可重复性非常重要，尤其是在比较验证以及您提到的系统演化（例如中间状态）的细粒度检查。如果您控制种子、PRNG实例以及前面提到的其他因素，这会导致可重复的历史。

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

Comments

谢谢@Tom。我觉得我没有明确指出的是，我想在不重新初始化PRNG的情况下运行一系列不同的模拟（具有不同的参数）。(不重新初始化它是一种允许PRNG确保新数字与前面数字独立的好方法。也就是说，在PRNG能被信赖的程度内做到这一点——这是一件不同的话题。)

假设我使用一个种子初始化PRNG。然后我进行一个模拟运算，该运算生成一个懒惰序列steps1。比如，我进行一个相当于'take 10000'的操作。每个步骤有一个PRNG调用，因此我现在已经通过10000+k个状态，其中k是由于分块而产生的额外处理。然后，使用同一个PRNG但不重新设置种子，从那个点开始，我做一个不同的模拟运算，创建一个懒惰序列steps2，并对它运行'take 10000'。然后，我扔掉steps2，但后来我想更仔细地检查它，所以我又重新运行第一个模拟（或者如果我知道k是多少，我可以仅仅将PRNG推进10000+k次），然后再次运行第二个模拟以重新创建steps2。

但是根据@alexmiller的说法，我不应该假设k总是相同的。如果k可能会不同，那么即使我在第二次模拟之前先运行第一次模拟，也不能保证我实际上是在重新创建之前步骤2的样子。

如果我不使用懒惰，那么我会知道PRNG被调用的次数以创建步骤1；例如这里的状态数是10000，所以要重新创建步骤2，我只能给PRNG提供已知的种子，并扔掉前10000个数字，这并不需要多少时间。然后我可以对步骤2进行第二次模拟以创建步骤2。（这可能比所需要的说得更多。）

一个替代方案是读取PRNG的状态并将其存储起来，然后在需要重新创建一个运行时使用它来初始化。我使用的是一个PRNG（Well19937c），其内部状态比我用以初始化它的长种子还要大。

（我昨晚清除了惰性。我认为这可能会带来一些性能上的提升，但大多数处理时间都花在每一步都运行的例程上，所以差异很小。）

---

是的，我现在明白了。你通过将其作为流来抽取，创建了一个在PRNG状态中的隐式依赖，预期你的PRNG将会受到分区重新绘制的确定性影响。我认为这没有特别的优势（除了更多有用的伪随机值分布之外）与计算新的种子并在运行之间初始化相比。我想你可能只记得一个种子，用于任意数量的衍生序列。然而，在这种方法下，为了了解第n个序列之后会发生什么，比如说步骤_n，你必须运行所有先前的步骤，以到达观察你感兴趣的序列的起始点。我可能会在每一个序列的终点计算或推导种子，以便用作下一个的初始化器，这可以避免你需要捕获内部状态。你可以在序列生成之间引入一些隐式依赖，但你构建了一个在PRNG空间中的隐式种子分布，并且作为随机游走函数从中采样....我不认为采样的质量会非常偏向，但请以你的情况为准。

我认为另一个选项（为了保持和最大化惰性）是按照Stuart的答案https://stackoverflow.com/a/3409568来做 Showcase 是否人有纠正

---

我在毫无必要地小心地避免运行之间可能的相关性，但我会这么做。我同意每次都生成新的种子，例如使用同一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中生成下一个种子作为长整数会将WELL19937c的624位状态在运行之间降低到64位状态。

很有趣。这看起来Apache Commons Math API实现允许你获取int数组并用它来初始化种子，如果你想持久化状态的话，所以将int数组作为你的种子而不是降级到长空间可能是可行的，以防止精度损失。谢谢您的笔记。

---

谢谢。是的，我在用单个种子生成了一长串实验之后就开始思考这个问题。我认为我可能需要循环伪随机数生成器几十万次才能重新运行其中一个晚期的实验集合。

我还没有看到读取状态的方法。你在看哪个类？我可能遗漏了一个相关的接口或者类层次结构中的某个东西。你是说“Abstract Well”中的“v” "字节数组池"字段吗？我需要检查源代码，这听起来可能是我需要的。你是看的Apache Commons Math 4吗？它看起来仍在建设中，所以我一直在使用Math 3.6.1，它的结构非常不同。（请随意不回答——这不是你的工作为我查找Apache Commons的东西。）

---

getStateInternal()在Apache Commons PRNG的开发版本中。