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

Question

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

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

（以下信息可能会对感兴趣的人有所帮助，但不了解我的具体用法仍可回答问题。因此，请随意跳过此段落。我在运行使用伪随机数生成器的模拟。这包括随机游走，如果游走遇到“目标”，则被截断。提前将游走作为惰性序列生成是很方便的，然后在找到目标时停止生成其元素。通常，我会丢弃原始随机游走等中间结果。它们同时存在于一种数据结构中，但最后我没有使用它们。然而，我有时想重新运行模拟来检查中间结果。很容易存储模拟运行时使用的种子，并使用它将随机数生成器设置回相同的状态。但是，分块可能会导致随机数生成器调用次数比严格需要的多。这是可以接受的，但如果分块取决于除我的代码和 Clojure 版本之外的其他因素，那么使用相同种子重新运行模拟不能保证产生相同的结果。目前这并不是个大问题。我可以将中间数据转换为非惰性的，而不会对性能产生很大的影响。然而，我仍在想是否这是必要的。）

Answer 1

你不应该对惰性序列何时实例化做出任何假设，因此这并不保证。

如果你想要控制生成，请使用循环/递归或使用reduced的reduce，或其他类似的技术来获取这种控制。

Comments

好的！会做到的。谢谢。

Answer 2

这对我来说没什么意义

这意味着在相同的种子条件下重新运行模拟并不保证产生相同的结果

函数被评估的次数似乎并不重要（例如，除非是性能方面[例如昂贵的函数计算]或其他情况，如纠缠副作用等）。由于你正在从序列中抽取结果，并在某个标准下停止，生成这些结果的过程应该使用相同的输入可重复。如果这个迭代过程依赖于一个以特定种子值初始化的PRNG，并且状态转换函数依赖于一个不可变的环境和PRNG的当前状态（例如，函数纯但具有具有状有态PRNG的良性副作用），那么我不明白你如何创建不同的状态序列。如果块生成决定运行比必要的多22次，它不会影响前面的10次。这10个值（比如说第10个值在消耗seq时满足停止标准）将被缓存，并且与任何后续的值完全不相关，因此序列的不可变性得到保持。只要为每个生成的序列隔离一个PRNG，我相信你应该有完整的独立性和可重复性（当控制PRNG实现、运行时、Clojure版本等因素时）。

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

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

Comments

谢谢@Tom。我认为我没有说清楚的是，我想在不重新初始化PRNG的情况下运行一系列不同的模拟（具有不同的参数）。(不重新初始化它是一种让PRNG确保新数字与前面的数字无关的好方法。也就是说，到任何PRNG可以信任去完成这一点的程度——这又是另一个话题。）

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

但是根据@alexmiller的观点，我不能假设k始终相同。如果k可能不同，那么即使在第二个模拟之前运行第一个模拟，也不能保证我实际上正在重新创建steps2。

如果我不使用懒性，我就知道PRNG用于创建steps1的调用次数恰好是10000次（如本例所示）——为了重新创建steps2，我只需要给PRNG提供已知的种子，然后丢弃前10000个数字，这不会花费太多时间。然后我可以进行第二个模拟以创建steps2。（这可能比需要的更多。）

另一种选择是从PRNG中读取状态并将其存储起来，然后在我需要重新创建一个运行时使用它来初始化。我使用的是PRNG（Well19937c），其内部状态比我用于初始化的长种子更大。

(昨晚我消除了懒惰。我认为这可能会带来一点性能的提升，但大部分处理时间都花在每一步都必须运行的例程中，所以差别很小。)

---

是的，我现在明白了。通过尝试将其作为一个流从中抽取，你在PRNG状态中创建了一个隐式依赖，你期望你的PRNG会在分块溢出中被确定性地影响。我觉得这与计算新种子并在运行之间初始化相比没有特别的优势（除了更多的伪随机值分布可能更有用）。我猜你只有一个种子需要记住，用于任意数量的导出序列。然而，按照这种方法，为了发现第n个序列后会发生什么，比如说步骤_n，你现在必须运行通过所有前导，到达起始点以观察你感兴趣的序列。我可能只是在每个序列结束时计算或推导出一个种子，作为下一个的初始化器来使用，这样可以防止你捕获内部状态。你可以在序列生成中引入一些隐式依赖，但你实际上正在构建PRNG空间的种子隐式分布，并从中采样作为随机游走函数······我认为采样的质量不会太有偏差，但也许不同的情况会有所不同。

我认为另一个选项（为了保留和最大化懒惰）是按照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中生成下一个种子作为长整型将WELL19937c的624位状态在运行之间降低到64位状态。

很有意思。看起来Apache Commons Math API的实现允许您取回整数数组并用它来种子，如果您想要将状态持久化，所以将整数数组作为种子存储而不是降级到长整型空间可能是可行的，以防止精度损失。感谢您的笔记。

---

谢谢。是的，我在用同一个种子生成了一连串实验之后开始这样怀疑。我认为我可能需要循环伪随机数生成器几十万次才能重运行后期实验集合中的一组。

我还没有看到读取状态的方法。你在看哪个类？我可能漏掉了一个相关的接口或者在类层次结构中的某个东西。你是指抽象WELL中的“v” “字节池”字段吗？我需要检查源，但听起来这可能是我需要的东西。或者你在看Apache Commons Math 4？这个版本似乎仍处于建设中，所以我一直在使用3.6.1，它有着完全不同的组织结构。（请自由选择不回答——这不是你的工作为我查找Apache Commons里的东西。）

---

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