懒序列分块是否具有确定性？

Question

我知道懒序列可以分块处理。也就是说，如果我的程序需要一个懒序列中的n个元素，所实现的可能多于n个。

我是否可以假设，如果我在Clojure相同版本中再次运行相同的代码，将返回实现完全相同的元素？我会这样认为，但我不希望在不了解的情况下做出这样的假设。

（以下包括额外的信息，以防有人对此感兴趣，但我认为知道我具体的应用场景并不必要来回答这个问题。因此，可以自由跳过此段落。我正在运行利用伪随机数生成器的模拟。这包括随机游走，如果游走遇到“目标”，则会被截断。事先作为一个懒序列生成一个游走是方便的，并在找到目标时停止实现元素。通常，我会丢弃中间结果，如原始随机游走。它们暂时存在于数据结构中，但最终我不会使用它们。然而，我有时想返回并重新运行模拟来检查中间结果。存储模拟运行所使用的种子是非常容易的，并可以使用它将随机数生成器设置为相同的初始状态。然而，分块可能会使随机数生成器被调用超过必要的次数。这是可以的，但如果分块会因代码和Clojure版本之外的某些因素而变化，这意味着即使使用相同的种子重新运行模拟也不一定会产生相同的结果。这现在并不是一个大问题。我可以稍有不牺牲太多性能的情况下使中间数据非懒序列。然而，我仍然想知道这是否是必需的。）

Answer 1

你不应该对懒序列何时实现有任何假设，因此这并不保证。

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

Comments

好的！会做的，谢谢。

Answer 2

我不理解这什么意思

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

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

我已经进行了十多年的离散事件模拟工作（主要是确定性，尽管偶尔初始条件是随机的）。可重现性非常重要，特别是用于比较验证，以及你提到的对系统演化的细粒度检查（例如中间状态）。如果你控制了种子、伪随机数生成器实例以及之前提到的其他因素，那么这将导致可重现的历史。

正如提到的，如果你仍然担心，你可以通过使用迭代和transduce/reduce/into来定义一个不会分片（或生成中间数列）的积极迭代过程，从而保留熟悉度、性能和控制。我通常出于性能考虑走这条路，尽管我的模拟在"框架"数量上较小，在状态转换功能复杂度上更实质。

Comments

感谢@Tom。我认为我没有讲清楚的是，我想在不同的参数下运行一系列独立的模拟（而不是重新初始化伪随机数生成器）。（不重新初始化是一种很好的方法，可以确保伪随机数生成器产生的新数字与之前的数字无关。也就是说，在PRNG可以得到信任做到这一点——这是一个不同的话题。）

假设我使用一个种子初始化伪随机数生成器。然后我运行一个模拟运行，生成一个惰性序列steps1。我做相当于'take 10000'的事情。每一步都有一个伪随机数生成器的调用，所以我现在已经将伪随机数生成器推进了10000+k个状态，其中k是由于分片而额外的处理。然后，使用同一个伪随机数生成器但不需要重置种子，从那个点开始进行另一个不同的模拟运行，创建一个惰性序列steps2，并在其上运行'take 10000'。然后我丢弃steps2，但我以后想更仔细地检查它，所以我重新运行第一个模拟（或者如果我知道k是什么，只是将伪随机数生成器推进10000+k次），然后再次运行第二个模拟来重新创建steps2。

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

如果我不使用惰性，那么我会知道伪随机数生成器被调用以创建steps1的次数——在这个例子中是10000次——所以为了重新创建steps2，我只需要给伪随机数生成器已知的种子，然后丢弃前10000个数字，这不需要多少时间。然后我可以进行第二个模拟来创建steps2。（这可能是比需要的更详细的说明了。）

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

（我昨晚把懒惰抛开了。我认为这可能会带来一点性能上的好处，但大部分处理时间都花在每一步都运行的例程上了，所以差异很小。）

---

是啊，我现在明白了。你在PRNG状态中创建了一个隐含的依赖关系，因为当你试图把它作为一个流来抽取时，你期望你的PRNG会受到分块重绘的确定性影响。我不太看出这种方法的特别优势（除了更实用的伪随机值分布之外），与在运行之间计算新的种子并初始化相比。我猜你只有一个种子需要记住，以生成任意数量的派生序列。然而，按照这种方法，为了发现第n个序列之后会发生什么，比如说steps_n，你现在必须遍历所有的前趋才能达到起点，从而观察你感兴趣的区域。我可能会在每个序列的末尾计算或推导出一个种子，用作下一个序列的初始化值，这样可以防止你捕获内部状态。你可以在seq生成之间引入一些隐含的依赖关系，但你正在构建一个在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的实现允许你从这个int数组中获取数据并使用它对种子进行初始化，如果你的意思是持久化状态，那么存储int数组作为你的种子而不是降级到长整型空间可能是可行的，这样可以防止精度丢失。感谢您的笔记。

---

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

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

---

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