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

Question

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

我能否假定如果在同一版本的Clojure中再次运行相同的代码，将会实现完全相同的元素？我本以为是这样，但不希望在没有了解的情况下就假定。

（以下信息提供给可能对此感兴趣的人，但相信了解我的使用场景并非回答此问题的必要条件。所以，请随意跳过此段落。我正在运行一些模拟，这些模拟使用了伪随机数生成器。这包括截断“目标”时被截断的随机行走。预先作为一个惰性序列生成行走是方便的，然后在遇到目标时停止实现其元素。通常，我会丢弃中间结果，例如原始的随机行走。它们在某个时刻存在于数据结构中，但最终不再使用。然而，有时我想要返回并重新运行模拟，以便检查中间结果。存储用于模拟运行的种子很容易，并使用它将随机数生成器设置为相同的开始状态。但是，分块可能导致随机数生成器被调用比实际需要的时间多。这可以，但如果分块根据代码和Clojure版本之外的某些因素变化，那么再次使用相同的种子重新运行模拟就不保证会得到相同的结果。目前这不算什么大问题。我可以在几乎没有性能损失的情况下使中间数据非惰性。然而，我仍在想是否真的需要这么做。)

Answer 1

你不应该假定任何关于懒序列何时实现的事情，因此这并不一定保证。

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

Comments

好的！ 将会这样做。 谢谢。

Answer 2

我不太明白这个意思。

这意味着使用相同的种子重新运行模拟可能不能保证得到相同的成果。

函数被评估的次数似乎并不重要（除了例如性能等情况）。因为你是从序列中抽取结果，并按照某个标准停止，生成这些结果的删除逻辑应拥有相同的输入可重现。如果在每次迭代中都使用特定的种子初始化自己的PRNG，且状态转移函数依赖于不可变上下文和PRNG的当前状态（例如，“功...

我已经进行了十年以上的离散事件模拟工作（主要是确定性的，虽然偶尔会有随机的初始条件）。可重复性，尤其是对比验证以及您提到的，对系统演化（例如中间状态）进行细粒度检查非常关键。如果您控制了种子、伪随机数生成器的实例以及其他之前提到的因素，这会导致可重复的历史。

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

Comments

谢谢@Tom。我觉得我没有说清楚的是，我想在不重新初始化伪随机数生成器的情况下运行一系列单独的模拟（具有不同的参数）。（不重新初始化是一种让伪随机数生成器确保新数字与先前的数字独立的好方法。也就是说，根据任何伪随机数生成器可以信任去做的那部分，这又是一个不同的主题。）

假设我用种子初始化了一个伪随机数生成器。然后我进行了一次模拟运行，该运行生成了一个懒序列steps1。我做了一些相当于'take 10000'的事情。每一步都有一个伪随机数生成器的调用，所以我现在已经通过10000+k状态将伪随机数生成器推进了，其中k是由于分块而产生的额外处理。然后，使用相同的伪随机数生成器但未重新播种，我从那个点开始进行另一个模拟运行，该模拟运行创建一个懒序列steps2，并在上面执行'take 10000'。然后我扔掉了steps2，但后来我想更仔细地检查它，所以我又重新运行了第一个模拟（或者如果我 knew 是多少，我可以只是把伪随机数生成器推进10000+k次），然后再次运行第二个模拟来重新创建steps2。

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

如果我不使用惰性操作，那么我知道伪随机数生成器被调用的确切次数以创建steps1--在这个例子中是10000次--因此要重新创建steps2，我只需要给伪随机数生成器提供已知的种子，然后扔掉前10000个数字，这不会花费很长时间。然后我可以进行第二个模拟以创建steps2。（这可能比我需要的内容更多。）

另一个选择是读取伪随机数生成器的状态并将其存储起来，然后在使用它重新创建一个运行时使用它来初始化。我使用的是一个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生成下一种子作为长数，将WELL19937c的624位状态在运行之间减少到64位状态。

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

---

谢谢。是的，我在使用一个种子生成了一长串实验之后开始考虑这个问题。我认为我可能需要循环PRNG几百万次才能重新运行后期的一些实验。

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

---

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