懒序列分块是否确定？

Question

我知道懒序列可以被分块处理。也就是说，如果我的程序需要从懒序列中获取n个元素，实际生成的元素可能超过n个。

我能否假设，如果在同版本的 Clojure 中再次运行相同的代码，将得到完全相同的元素？我想应该是这样，但我不想在没有了解的情况下做出这样的假设。

(以下信息包含了一些额外的信息，以供感兴趣的读者参考，但了解我的用例并不是回答此问题的必要条件。因此，请自由跳过本段。我正在运行使用伪随机数生成器的模拟。这些涉及随机游走，如果游走遇到“目标”，则会被截断。提前生成一个作为懒序列的游走很方便，然后在找到目标时停止逐个生成元素。通常，我会抛弃中间结果，如原始随机游走。这些结果会在一个数据结构中存在，但最终我并不需要使用它们。然而，我想有时候能够返回并重新运行模拟，以便检查中间结果。储存模拟运行的种子很简单，并使用它来设置随机数生成器的初始状态。但是，分块可能会导致随机数生成器被调用比实际需要的次数多。这没问题，但如果分块取决于除了我的代码和 Clojure 版本之外的其他东西，那么这意味着使用相同的种子重新运行模拟的并不会保证产生相同的结果。这目前不是问题。我可以通过不使中间数据变得懒加载而大幅减少性能损失。但我仍在想，这是否必要。)

Answer 1

不应该假设关于惰性序列何时被实现的情况，所以这是没有保证的。

如果你想要对生成过程进行控制，请使用循环/递归或减少，或者使用其他类似技术来获取控制权。

Comments

好的！ 会做的。 谢谢。

Answer 2

这对我来说没有意义。

这可能会导致使用相同种子重新运行模拟不一定能产生相同的结果。

函数调用的次数似乎无关紧要（例如，除了性能[例如昂贵的函数计算]或其他情况，如纠缠的副作用等）。由于您正在从序列中提取结果，并在某些标准处停止，生成这些结果的进程应该可以使用相同的输入进行重现。如果这个迭代过程依赖于使用特定种子初始化的自己的PRNG，并且状态转换函数依赖于不可变上下文和PRNG的当前状态（例如，“功能上纯”但具有具有状态的PRNG的良性副作用），那么我看不出您如何创建不同的状态序列。如果块生成决定运行比必要的多22次，这不会影响之前的10次。这10个值（比如说第10个值是消耗seq时停止标准的充分条件）被缓存，并且与任何后续值完全独立，因此保持了序列的不可变性。只要为每个生成的序列隔离一个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个数字，这并不需要很长时间。然后我可以在第二步模拟中创建步骤2。(这可能比需要的更详细。)

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

（我昨晚排除了懒惰。我认为由此可能带来一些微小的性能提升，但大多数处理时间都耗费在每一步都会运行的例程中，所以差异很小。）

---

是的，我现在明白了。你在尝试从它作为一个流来抽取，从而在PRNG状态中创建了一个隐含的依赖性，期望通过分块重绘来以确定的方式影响你的PRNG。我认为这个方法（除了更有效的伪随机值分布外）没有特定的优势，与在运行之间计算一个新的种子并初始化相比。我想你可能只有一个种子要记住，用于任意数量的衍生序列。然而，按照此方法，为了发现第n个序列之后会发生什么，比如步骤_n，你现在必须遍历所有前驱才能到达起点，以便观察你感兴趣的序列。我可能会在每个序列的末尾计算或推导出一个种子，作为下一个的初始化器，这样可以避免你捕获内部状态。你可以在seq生成之间引入一些隐含的依赖，但你正在构建一个被抽样作为随机游走函数的种子在PRNG空间的隐含分布。我不认为抽样的质量会有多大的偏差，但可能因人而异。

我认为另一个选项（为了保留并最大化懒惰）是根据Stuart的回答取消分块 https://stackoverflow.com/a/3409568 。只是关闭分块吧 :)

---

为了避免运行之间的可能相关性，我做得过于小心了，但我愿意这么做。我同意每次生成一个新的种子是合理的，例如使用相同的PRNG。我宁愿不使用其他方式生成多个种子，例如从系统时间和类似的东西，担心如果这样做太频繁，我会不小心得到相同的种子。

请注意，从PRNG生成下一个种子将624位的WELL19937c状态减少到64位状态，这在实践中可能无关紧要，但如果不影响结果，从先前的624位状态继续会更好。

我受到了L'Ecuyer及其等人《并行计算机的随机数》的启发。
https://www.sciencedirect.com/science/article/pii/S0378475416300829
我没有并行运行模拟，但其中的一些原则是相关的。但 Again，我可能做得太多了。

我在初始化伪随机数生成器后还会丢弃一两千个数字，因为如果你真的很不幸，WELL生成器可能会在一个不太随机的状态中开始一段时间。但我认为WELL19937c不应该有这个问题。(请参阅https://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf )

分解块：哇，很有趣。谢谢。

---

>请注意，使用PRNG生成下一个种子作为长数据将WELL19937c的624位状态在运行之间降低到64位状态。

有趣。看起来Apache Commons Math API实现允许您获取int数组并用它来设置种子，如果您想要持续状态，这似乎是可行的，因此将int数组作为种子而不是降级到long空间可以防止精度丢失。感谢您的笔记。

---

谢谢。是的，我在用一个种子生成了一连串实验后开始思考这个问题。我认为我可能需要轮换PRNG几十万次才能重新运行那些后来的实验集。

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

---

getStateInternal()方法位于Apache Commons PRNGs的开发版本中。