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

Question

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

我可以假设如果在相同的Clojure版本中再次运行相同的代码，则确实会实现相同的元素吗？我认为是这样的，但不希望在没有了解之前就做出假设。

(我包含以下额外信息，以防有人感兴趣为什么这很重要，但我不认为了解我的用例是回答问题的必要条件。所以 请随意跳过此段落。我正在运行使用伪随机数生成器的模拟。这些涉及如果步进遇到“目标”，则截断的随机漫步。方便地将漫步作为懒惰序列提前生成，然后在找到目标时停止实现其元素。通常，我会丢弃中间结果，如原始的随机漫步。它们暂时存在于一个数据结构中，但最终我没有使用它们。然而，我有时想能够回过头来重新运行模拟，以便检查中间结果。存储用于模拟的运行的种子很容易，并且可以使用它将随机数生成器设置为从相同的状态开始。然而，分块可能导致随机数生成器调用次数多于严格必要的次数。这是可以接受的，但如果分块不仅取决于我的代码和Clojure版本，那么重新运行相同的种子重新运行模拟就不一定保证产生相同的结果。目前这不太重要。我可以不造成太多性能损失地将中间数据变为非懒惰。然而，我仍然想知道这是否真的必要。)

Answer 1

你不能假设延迟序列何时实现，所以这不可能保证。

如果你想控制生成过程，请使用循环/递归或reduce with reduced，或使用其他此类技术来获取该控制。

Comments

好的！我会去的。谢谢。

Answer 2

这对我来说没有意义

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

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

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

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

Comments

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

假设我用一个种子初始化PRNG。然后进行一次模拟运行，生成一个惰性序列steps1。我进行类似于'take 10000'的操作。每一步都有一个PRNG调用，所以我现在已经将PRNG推进了10000+k状态，其中k是因分块导致的额外处理。然后，使用相同的PRNG但不必重新设置种子，从那个点开始，进行不同的模拟运行以创建lazy sequence 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个序列之后发生了什么，比如steps_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生成下一个种子作为长整数将624位状态（对于WELL19937c）减少到运行之间的64位状态。

很有趣。看起来Apache Commons Math API的实现允许你在想要持续状态时从int数组中获取并使用它，因此将int数组作为种子而不是降级到long空间可能是可行的，这样可以防止精度损失。谢谢您的笔记。

---

谢谢。是的，我在使用一个种子生成了一系列长序列的实验后开始思考这个问题。我认为我需要循环PRNG几十万次才能重新运行后期实验中的一组。

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

---

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