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

Question

我知道惰性序列可以被分块处理。也就是说，如果我的程序需要惰性序列中的 n 个元素，可能因为其他原因而需要处理超过 n 个元素。

我是否可以假设，在相同的 Clojure 版本中再次运行相同的代码，将会产生完全相同的元素？我会认为是这样，但我不希望在没有了解的情况下就假设。

（我这里包括附加信息，以防 anyone 对为什么这很重要感兴趣。但是，我认为了解我的用例对于回答该问题不必要。因此 请随意跳过此段落。我正在运行一些使用伪随机数生成器的模拟。这些涉及截断目标随机游走。提前将游走生成为一个懒性序列很方便，并在找到目标时停止实现其元素。通常，我会丢弃中间结果，比如原始随机游走。它们会存在于某个数据结构中，但最后我没有使用它们。然而，有时我希望能够回过头来再次运行模拟，以检查中间结果。很容易存储用于模拟运行的部分，并使用它将随机数生成器设置为相同的初始状态。但是，分块可能会导致随机数生成器被调用比严格必要的次数更多。这是可以的，但如果分块取决于我的代码和 Clojure 版本之外的某些因素，那么这意味着使用相同的种子再次运行模拟可能不会保证产生相同的结果。这目前并不是一个大问题。我可以在性能损失很小的情况下，将中间数据非懒性化。然而，我仍在想这是否是必要的。）

Answer 1

你不应该对懒序列何时实现做出任何假设，所以这并不保证。

如果你想要控制生成过程，可以使用循环/递归或reduce with reduced等技巧来获得这种控制。

Comments

好吧！(Will do) 谢谢。

Answer 2

这对我来说没有意义

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

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

我已从事离散事件仿真工作超过十年（主要确定性，尽管偶尔有随机初始条件）。可再现性，尤其是对于比较验证以及正如您所提到的，对系统演变（例如中间状态）的细粒度检验非常重要。如果您控制了种子、PRNG实例以及之前提到的其他因素，这将导致可再现的历史记录。

如前所述，如果您仍然感到担忧，您可以使用iterate和transduce/reduce/into定义一个不会分块（或生成中间序列）的贪婪迭代过程，以保持熟悉度、性能和控制。如今，我之所以采取这种方式，主要是因为性能原因，尽管我的模拟在“帧”的数量上较小，而在状态转换函数的复杂性上较大。

Comments

感谢@Tom。我认为我之前没有明确的是，我想在不重新初始化PRNG的情况下运行一系列独立的模拟（具有不同的参数）。（不重新初始化它是一种让PRNG确保新的数字与前面的数字无关的好方法。换句话说，就像任何PRNG都可以被认为会那样做——这是一个不同的话题。）

假设我使用种子初始化一个PRNG。然后进行一次模拟运行，生成一个懒序列steps1。我做一些类似于'take 10000'的操作。每一步都有一个PRNG调用，所以我现在已经把PRNG推进了10000+k个状态，k是额外处理导致的。然后，使用相同的PRNG但不会重新设置种子，从这个点开始进行不同的模拟运行，创建一个懒序列steps2，运行'take 10000'。然后丢弃steps2，但稍后我想更仔细地检查它，所以再次运行第一次模拟（或者如果我知道k是什么，可能只是将PRNG推进10000+k次），然后再次运行第二次模拟以重新创建steps2。

但据@alexmiller所说，我不应该假设k总是相同的。如果k可能不同，那么即使我先运行第一次模拟，也不能保证我真正重新创建出厂步骤2。

如果不使用懒加载，我将确切知道PRNG调用创建steps1的次数——在这个例子中是10000——所以为了重新创建steps2，我只需要给PRNG提供已知的种子，然后丢弃前10000个数字，这不会花太多时间。然后我可以运行第二次模拟来创建steps2。（可能比需要的细节多。）

另一种方法是读取PRNG的状态并将其存储，然后如果需要重新创建运行，可使用该状态来初始化它。我使用的是PRNG（Well19937c），其内部状态比我用来初始化它的长种子要大。

(昨晚我消除了懒惰。我认为可能会有一些性能上的提升，但大部分处理时间都在每个步骤都会运行的例行程序中，所以差别不大。)

---

我明白了。你通过把它作为一个流来从中抽取，来创建PRNG状态的隐性依赖，期望你的PRNG将受到分块重绘的确定性影响。我没有看到这方面的特定优势（除了实现伪随机值更有用的分布之外），与计算新种子并初始化每次运行相比。我认为你只需要记得一个种子，去衍生任意数量序列。不过，根据这种方法，为了发现第n个序列，比如步骤_n，后的结果，你现在必须运行所有的前一序列，以达到观察感兴趣序列的起点。我可能只会计算或推导每个序列的终止点的种子，用作下一个的初始化器，从而不需要捕获内部状态。你可以在序列生成过程中引入一些隐性依赖，但你正在构建PRNG空间上的种子隐性分布，并以此作为随机游走函数的采样……我认为采样的质量不会非常偏向，但视情而定。

我认为另一个选项（为了保持和最大化懒惰）是按照Stuart的回答（https://stackoverflow.com/a/3409568）取消分块：）

---

我在做一些不必要的事情来避免运行间可能的相关性，但我宁愿这么做。我同意每次都生成新种子是合理的，例如，通过使用相同的PRNG。（我不希望在某种方式下生成多个种子，例如从系统时间等，因为担心如果发生得太快，我可能会意外地得到相同的种子。）

请注意，从PRNG生成下一个种子作为长值会将WELL19937c的624位状态在每次运行之间减少到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实现允许您获取整数数组并用它来存储种子，如果您想持久化状态，那么用整数数组作为种子而不是降级到长整型空间可能可行，这有助于避免精度损失。 感谢您的笔记。

---

谢谢。是的，我在用同一个种子生成一系列实验后开始考虑这一点。我认为我得让PRNG循环几十万次，才能重新运行稍后的一些实验集。

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

---

Apache Commons PRNG的开发版本中有getStateInternal()方法。