<p>对于这个问题有一个很好的工具:有限状态机。你知道吗</p>
<p>但是Python并不是一种很好的语言,不适合快速实现。你知道吗</p>
<p>这里是一个非确定性状态机,它可以识别任何输入流中的两个序列。<code>*</code>表示从3到6的抛出:</p>
<p><img src="https://i.stack.imgur.com/sZpeF.png" alt="NFSM"/></p>
<p>这很难实现,因为它一次可以占用多个状态,但有一种称为子集构造的标准算法,它将此转换为一个<em>确定性</em>状态机,实现起来非常有效。在这里应用它会产生:</p>
<p><img src="https://i.stack.imgur.com/kR76v.png" alt="DFSM"/></p>
<p>这是一个C实现。在Python中,可以使用一个映射,将当前状态的元组加上下一个状态的输入数字。在这里,我们使用<code>goto</code>在执行代码中根据位置实现映射:</p>
<pre><code>#include <stdio.h>
#include <stdlib.h>
#define ROLL do { r = 1 + rand() %6; } while (0)
int main(void) {
int n_trials = 10000000;
int t_total_11 = 0;
int t_total_12 = 0;
for (int n = 0; n < n_trials; n++) {
int r, t = -1, t_11 = 0, t_12 = 0;
A:
++t;
ROLL;
if (r == 1) goto AB;
goto A;
AB:
++t;
ROLL;
if (r == 1) goto ABC;
if (r == 2) goto AD;
goto A;
ABC:
++t;
if (!t_11) {
t_11 = t;
t_total_11 += t_11;
if (t_12) continue;
}
ROLL;
if (r == 1) goto ABC;
if (r == 2) goto AD;
goto A;
AD:
++t;
if (!t_12) {
t_12 = t;
t_total_12 += t_12;
if (t_11) continue;
}
ROLL;
if (r == 1) goto AB;
goto A;
}
printf("Avg for 11: %lf\n", (double) t_total_11 / n_trials);
printf("Avg for 12: %lf\n", (double) t_total_12 / n_trials);
return 0;
}
</code></pre>
<p>在我的旧Macbook上,它在5.3秒内迭代了1000万次(不是100万次)。所以这是一个很酷的~快100倍。当然,好的位元取决于PRNG的速度。Gnu的<code>rand</code>很快,但不是那么随机。显然,这足以说明趋同。程序打印:</p>
<pre><code>Avg for 11: 41.986926
Avg for 12: 35.997196
</code></pre>
<p>当我有更多的时间,我会尝试一个Python impl。你知道吗</p>