工欲善其事必先利其器

Fri Jul 3, 2020

上周每周挑战的第一个任务是打印前十个强质数和弱质数。如果一个质数 pn 大于其两个相邻质数的平均数（即 pₙ > (pₙ₋₁+pₙ₊₁)/2），则该质数为"强"质数。如果一个质数小于其两个相邻质数的平均值，那么它就是"弱"质数。

当然，如果我们碰巧有一个所有质数的列表，这个挑战就变得微不足道了。那么我们只需要过滤掉前十个强数，和前十个弱数。事实上，如果我们碰巧有一个强质数的列表和一个弱质数的列表，那就更简单了。那我们就只需要打印出每个的前十个。

但是，质数和弱质数的数量是无限的（也有可能是强质数，虽然这还只是猜测），所以在大多数编程语言中建立一个完整的质数亚种列表是不切实际的。

然而，我喜欢 Raku 的另一个原因是它能很好地处理无限列表和序列。不用担心有限的上限，简化了大量的任务…这就是其中之一。

质数序列只是正整数序列，经过过滤（用 .grep）只保留那些质数。当然，Raku 已经有一个质数测试器：内置的 &is-prime 函数。质数序列永远不会改变，所以我们可以把它声明为一个常数:

constant p = [  (1..∞).grep( &is-prime )  ];

现在我们只需要提取强质数和弱质数。鉴于前面的"强"和"弱"的定义，我们得到：

sub strong (\n)  { n > 0 && p[n] > p[n-1, n+1].sum/2 }

sub weak   (\n)  { n > 0 && p[n] < p[n-1, n+1].sum/2 }

请注意，p[n-1，n+1] 是 p[n] 的两个邻域的列表，然后我们把它们加在一起(.sum)和平均(/2)。

这两个强度测试是在质数的索引上操作的，而不是它的值，所以要生成强质数和弱质数的完整列表，我们需要取这些索引（p.keys），过滤它们，只保留强或弱的索引（另一个 .grep），然后将每个索引映射回对应的质数。

这就得到了：

constant strong-p = [ p.keys.grep(&strong).map(->\n { p[n] }) ];
 
constant   weak-p = [ p.keys.grep(&weak  ).map(->\n { p[n] }) ];

这很好用，但是要把所有的质数(p)转换回索引(.keys)，然后再把每个索引转换回对应的质数，有点笨拙：.map(->\n { p[n] })。

因此，我们可以将 p 中的每个素数转换为键/值对，只对键进行 grep，然后只对值进行映射。就像这样：

constant strong-p = p.pairs.grep(*.key.&strong).map(*.value);

constant   weak-p = p.pairs.grep(*.key.&weak  ).map(*.value);

…其中 *.key.&strong 只是一个简写: -> \pair { strong( pair.key ) }。换句话说，过滤掉那些当传递给 &strong 的键时，返回 True 的对。

或者，更简单的是，我们可以在一个单一的映射中过滤和测试索引和值，对当前的质数和它的索引使用更易读的名字。像这样:

constant strong-p = p.kv.map: ->\n,\pₙ {pₙ if strong n};

constant   weak-p = p.kv.map: ->\n,\pₙ {pₙ if   weak n};

即：把无限的质数列表(p)转换为无限的交替 key-then-value 列表(p.kv)。对于每一个这样的 index-then-prime,调用索引 n 和质数 pₙ(.map:->\n,\pₙ), 然后只有当 pₙ 具有适当的强度时才保留 pₙ({pₙ if strong n} or {pₙ if weak n})。

无论我们用哪种方式生成无限的 strong-p 和 weak-p 列表，打印每一个列表的前十位都是很简单的:

say 'strong primes: ', strong-p[^10];
say 'weak primes:   ',   weak-p[^10];

请注意，在上面显示的所有代码中，所有的 grep 和 map 都是懒惰地、按需地、及时地工作。每个 grep 和 map 都只遍历你实际查询的索引（在本例中：索引0到9的值）所需的列表元素。因此，在这些无限列表上操作并不比使用有限列表花费更多的工作。

事实上，它通常需要更少的工作。

如果我们宁愿只使用有限的质数列表，我们就需要事先神奇地知道（即猜测）需要多少个质数才能保证我们的列表至少包含十个强质数和十个弱质数。

例如，我们可以合理地假设，前 1000 个整数可能至少包含 10 个强质数和 10 个弱质数，因此我们可以尝试:

constant p = [  (1..1000).grep(&is-prime)  ];

而且，确实，这样做也不错。只是我们刚刚做的工作是实际需要的十倍。

或者我们可能猜到了一个更严格的上限:

constant p = [  (1..100).grep(&is-prime)  ];

这本来可以省去所有额外的工作，但这只是一个快乐的意外。第10个强质数是97，但是为了正确测试它的强弱，我们还需要下面的质数(101)。然而，由于我们在100时停止生成质数，当 &strong 子程序请求第 n+1 个质数时，它将收到一个未定义的值。当作为一个数字使用时，这个未定义的值将转换为零，因此97的两个质邻的平均值将被计算为 (89+0)/2，这肯定小于97，这将(错误地，但正确地！)表明97是一个强质数。

这不是科学，这是巫术。

如果我们想避免使用一个极度保守的上限的额外工作（如果我们的"极度保守"的概念不够保守的话，还有出错的风险），那么我们需要另一种方法。我们需要对连续的整数进行迭代，找到连续的质数，然后测试它们的强度，直到我们绝对确定我们有足够的每一个质数。

这看起来就像：

    # The various lists of primes are all initially empty...
    my        \p = [];
    my \strong-p = [];
    my   \weak-p = [];

    # The definitions of "strong" and "weak" (as before)...
    sub strong (\n)  { n > 0 && p[n] > p[n-1, n+1].sum/2 }
    sub weak   (\n)  { n > 0 && p[n] < p[n-1, n+1].sum/2 }

    # Try every integer i as a potential prime...
    for 1..* -> \i {

        # If it's actually prime...
        if is-prime(i) {

            # Add it to the list of known primes...
            p.push(i);

            # If there are enough known primes to test strengths...
            if p.elems >= 3 {

                # Can now test the second-last prime in the list...
                my \n = p.end - 1;

                # And add it to the appropriate list (if any)...
                if    strong(n) { strong-p.push( p[n] ) }
                elsif   weak(n) {   weak-p.push( p[n] ) }
            }
        }

        # Stop when we have at least 10 of each subspecies...
        last if strong-p & weak-p >= 10;
    }

    # Print out the first ten of each...
    say 'strong primes: ', strong-p[^10];
    say 'weak primes:   ',   weak-p[^10];

这工作正确，而且不做不必要的计算。

但与之相比，写起来要难得多，读起来也会难得多(要验证，要维护):

    # All the primes...
    constant p = [  (1..∞).grep(&is-prime)  ];

    # The definitions of "strong" and "weak"...
    sub strong (\n)  { n > 0 && p[n] > p[n-1, n+1].sum/2 }
    sub weak   (\n)  { n > 0 && p[n] < p[n-1, n+1].sum/2 }

    # All the strong and weak primes...
    constant strong-p = p.kv.map: ->\n,\pₙ {pₙ if strong n};
    constant   weak-p = p.kv.map: ->\n,\pₙ {pₙ if   weak n};

    # Print out the first ten...
    say 'strong primes: ', strong-p[^10];
    say 'weak primes:   ',   weak-p[^10];

哦，这个声明式版本的速度也是迭代方案的四倍。

这也是为什么在 Raku 中，工欲善其事必先利其器的原因。

by Damian

PS: 那些已经熟悉 Perl 的人可能已经注意到，在上面的例子中完全没有标号变量（比如：$n 或 @p）。当然，Raku 确实有带符号的变量，但你不需要使用它们。你可以使用无符号变量来代替，这些变量是用前导反斜线声明的。

my \p = [];

for 2..* -> \i {...}

sub strong (\n) {...}

…然后在使用时不加任何前置的标点符号：

sub strong (\n)  { n > 0 && p[n] >p[n-1, n+1].sum/2 }

if is-prime(i) {
    p.push(i);
}

所以，如果唯一让你不愿意尝试这种神奇的新语言的是你对标点符号变量的病态恐惧和理性厌恶，也许是时候给 Raku 一个尝试了？