懒序列的分块处理是否是确定的？

Question

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

我在想，如果我在同一版本的Clojure中第二次运行相同的代码，是否可以假设会实现恰好相同的元素？我会这么想，但我不想在没有了解的情况下就假设。

（我在这里提供额外的信息，以防有人感兴趣为什么这很重要，但是我认为了解我的用例并不必要才能回答这个问题。所以请随意跳过此段。我正在运行使用伪随机数生成器的模拟。这些涉及随机游走，当游走遇到“目标”时将被截断。提前作为一个懒序列生成游走是方便的，然后当找到目标时停止实现其元素。通常，我会丢弃中间结果，例如原始随机游走。它们在某个时候存在于数据结构中，但后来我没有使用它们。然而，有时我希望能够回顾并重新运行模拟，以便检查中间结果。很容易存储用于模拟运行的种子，并使用它将随机数生成器设置为从相同的状态开始。但是，分块可能导致随机数生成器被调用超过所需的次数。这是可以的，但如果分块除了我的代码和Clojure版本之外还取决于其他因素，那么重新运行具有相同种子的模拟不能保证会产生相同的结果。这目前不是什么大问题。我可以不大幅度影响性能地将中间数据变成非懒序列。然而，我还是想知道这是否是必需的。）

Answer 1

您不应该对延迟序列的实现时间做出任何假设，所以这并不保证。

如果想要控制生成过程，可以使用循环/递归或使用reduced的reduce或其他类似技术来获得这种控制。

Comments

好的！ 我会做的。 谢谢。

Answer 2

这对我来说没有意义

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

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

我已经从事离散事件模拟工作超过十年了（主要是确定性的，但偶尔会有随机初始条件）。可重现性，尤其是对于比较验证以及您提到的对系统中各个阶段（如中间状态）的精细检查，非常重要。如果您控制了种子、伪随机数发生器的实例以及之前提到的其他因素，这将导致可重现的历史。

正如所述，如果您仍然担心，您可以通过使用迭代和转导/归约/ Receive 来定义一个不会分块（或生成中间序列）的积极迭代过程，从而保持熟悉、性能和控制的感受。我通常出于性能原因走这条路，尽管我的模拟在生成的“帧”数量上较小，而在状态转换函数的复杂性上更实质。

Comments

谢谢@Tom。  我认为我没有讲清楚的是，我想在不重新初始化伪随机数生成器的情况下运行一系列不同的模拟（带不同的参数）。  （不重新初始化，这是一个使伪随机数生成器确保新数字与前面的数字无关的好方法。  即任何伪随机数生成器可以信赖做到这一点——这是一个不同的话题。）

假设我使用一个种子初始化伪随机数生成器。  然后我进行一次模拟运行，生成一个返回序列步骤1。  我做了类似于'take 10000'的事情。  每一步有一个伪随机数生成器调用，所以我现在将伪随机数生成器推进了10000+k状态，其中k是由于分块而产生的额外处理。  然后，使用同样的伪随机数生成器但不在重新播种的情况下，从那个点开始进行不同的模拟运行，创建步骤2，并在上面运行'take 10000'。  然后我丢弃步骤2，但以后我想更仔细地检查它，所以我重新运行第一个模拟（或者如果我知道了k是多少，我可以只将伪随机数生成器前进了10000+k次），然后再次运行第二个模拟以重新创建步骤2。

但是根据@alexmiller的说法，我不应该假设k始终相同。  如果k可能会有所不同，那么  即使在第二次模拟之前先运行第一次模拟也并不能保证我真正重新创建了步骤2。

如果我不使用懒惰性，我知道伪随机数生成器被调用以创建步骤1的确切次数——在这个例子中是10000次，所以我可以通过给伪随机数生成器一个已知的种子来重新创建步骤2，且只需丢弃第一个10000的数量，这不会占用太多时间。  然后我可以执行第二次模拟以创建步骤2。  （这可能比需要的说得更多。）

另一种可能性是读取伪随机数生成器的状态并保存它，然后在需要重建运行时使用该状态来初始化它。  我正在使用一个伪随机数生成器（Well19937c），它的内部状态比用它初始化的种子长。

（我昨晚排除了懒惰。我认为因此我可能看到了一点性能的提升，但由于大部分的渲染时间都在每个步骤都运行的例程中，所以区别很小。）

---

是的，我现在明白了。你通过将其作为流来尝试从中抽取，以期你的伪随机数生成器在重绘分块时能确定性受到影响，从而创建了一个隐式的PRNG状态依赖。我不认为这种做法有什么特别的优势（除了更有效的伪随机值分布），与计算新种子并在运行之间初始化相比。我猜你只需要记住一个种子，就可以用于任意数量的派生序列。但是，按照这种方法，为了发现第n个序列（例如steps_n）之后会发生什么，现在你必须运行所有前导序列到达起点，以观察你感兴趣的序列。我可能会在序列结束时计算或推导一个种子，用作下一个序列的初始化器，这样可以防止你捕获内部状态。你可以在序列生成和随机游走函数中引入一些隐式依赖，但你正在构建一个跨越PRNG空间的种子隐式分布并从中抽取样本……我认为样本质量不会太有偏，但具体情况可能会有所不同。

我认为另一个选项（为了保留和提高懒惰）是将分块取消，如Huang的回答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数组作为种子而不是降级到long空间可能是可行的，从而防止精度损失。谢谢你的笔记。

---

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

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

---

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