越简单越好
— 焉知非鱼上周每周挑战的第一个任务是生成范埃克序列:
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0,...
第一个挑战是要理解什么是范埃克序列，因为网上的各种解释都没有即时的帮助。
范埃克序列是一个从零开始的整数列表，序列中的下一个数字由当前数字与该数字最近的前一个出现的距离给出。
例如，如果当前指数N处的数字（我们称它为：Aₙ）是7，那么为了计算指数N+1处的数字，我们通过序列回溯7的最近一次出现（在某个较早的指数M处）。那么序列中的下一个数字就是这两个7的出现之间的距离: N - M
唯一复杂的是，如果当前数字在前面的序列中没有出现，那么下一个数字就是零。这并不像你想象的那样武断：我们可以把这个零值看作是 Aₙ 到自身的距离。也就是说，如果没有前面的出现，那么"前面"出现的唯一可能的候选者只是 Aₙ 本身，所以这种情况下的距离是 N - N，也就是零。
好了，这就是范埃克序列。现在我们如何在 Raku 中生成它？
如果你一直在关注我最近的博客文章，那么了解到 Raku 有一个适当的内置工具，它将让我们通过一个单一的语句来完成整个任务，可能不会有太多的惊喜。这个工具就是序列运算符。
... 序列操作符接受一个初始值列表，然后是一个代码对象（即一个块或子例程），接着是一个终止条件。
my @sequence = @initial-list, &code-obj ... $termination;
它从初始值开始建立一个序列（字面意思是 Seq 类的对象），然后通过在初始列表的最后元素上反复调用代码对象，在初始列表之后生成额外的值。每次调用代码对象时，它返回的值都会被追加到序列中，直到返回一个与终止条件智能匹配的值，这时序列就完成了。例如
# initial code-obj termination
my @odd-nums = 1, 3, 5, {$^n + 2} ... 999;
my @N-powers = $N, $N², {$^x * $N} ... * > 1_000_000;
my @fibonacci = 0, 1, 1, {$^a + $^b} ... ∞;
这些例子与范埃克的序列有一个重要的不同。每个例子都只使用一个前值（或者在Fibonacci的情况下，使用两个前值）来计算下一个数字。但范埃克序列中的下一个数字既取决于紧接的前一个值(Aₙ)，也取决于前一个值之前的整个序列…它必须被搜索以找到 Aₙ 的适当的前一个出现。
当然，Raku 也支持这种序列：如果你的代码对象使用了特殊的数组参数 @_（或者实际上，任何其他的变量数组参数），那么它每次都会被传递整个前面的序列。
所以现在我们需要做的就是建立一个代码对象(在本例中：一个子例程)，当传递给 @_ 中的整个前一个序列时，计算下一个范埃克的数字。它可能看起来像这样:
sub next-vanEck's {
my $N = @_.end;
my $M = try ($N-1...0).first: {@_[$^m] == @_[$N]};
with $M { return $N - $M }
else { return 0 }
}
当前序列中的最终索引由 @_.end 给出(就像 Perl 中的 $#_)，所以这就是我们当前的N个位置。为了找到最近的前一个相同的数字，我们从索引 N-1 向后走到零，寻找第一个索引 ($^m)，其中该索引的值 (即 @_[$^m]) 等于索引 N 的值 (即 @_[$N])。如果找到 M，则返回 N-M，否则返回0。
顺便说一下:
with $M {... }块只是一个方便的速记:if $M.defined { my $_ := $M; ...}。- 搜索 M 的
try前缀是为了处理$N为0的边缘情况，在这种情况下，$N-1...0会产生一个负数组索引，从而引发异常。 - 是的，在 Raku 中，在子例程名（或任何其他标识符）中使用撇号或连字符是完全可以的，只要它被正常的标识符包围，所以它不会与字符串的开始相混淆。
一旦我们有了一个计算下一个范埃克数的代码对象,那么整个范埃克序列就是:
constant vanEck's = 0, &next-vanEck's ... ∞;
让序列运行到无穷大是没有问题的，因为 ... 会惰性地生成它的值：只计算满足给定请求所需的元素数量。
一旦我们有了我们的常数序列，我们就可以请求任何特定的索引，这时下一个范埃克数将被调用尽可能多的次数来计算请求的值:
say vanEck's[100]; # prints: 23
这固然是一个干净、紧凑、不乱的解决方案，但并没有达到宣传的目的：“一句话”。
然而，上面的版本只是一个起点，我们还可以对它进行许多改进…通过更 Raku 风格的思考和编码。
首先，当一段代码通过索引迭代，然后查找相应的数组元素时，这往往是一个危险的信号。尤其是 Raku，它可以直接迭代那些数组元素，然后在我们需要的时候找到相应的索引（就像我们在这里做的那样）:
# Version 2...
sub next-vanEck's {
my $N = @_.end;
my $M = @_.head(*-1).first(@_.tail):end:k;
with $M { return $N - $M }
else { return 0 }
}
在这个版本中，我们通过取列表中最后一个元素之前的所有元素(@_.head(*-1))，然后搜索第一个与最后一个元素相等的元素(.first(@_.tail))来查找索引 M。
但是，由于我们需要最接近前面的匹配，我们需要在前面的元素中向后搜索，所以我们添加了一个 :end 副词来告诉 .first 从最后搜索。然后，当我们找到一个匹配时，我们需要找到该匹配的位置（而不是在那里找到的值），所以我们添加一个 :k 副词，告诉 .first 返回匹配的 “key”（即匹配发生的索引），而不是匹配的值。
这种新的定位M索引的方式所需的代码略少，而且不容易出现逐个错误，但真正的好处是它的速度也明显快了。因为它是在迭代数组元素而不是数组索引，所以它不必为了比较每一个之前的元素和最后的元素而进行两次显式数组查找。
这里还有一个小的代码优化可能。正如我们在这个探索的开始时看到的那样，如果没有M索引就返回0的特殊情况，相当于在这种情况下将M设置为N。如果我们这样做，那么我们就可以直接返回 N-M，而不需要对特殊情况进行测试。就像这样:
# Version 3...
sub next-vanEck's {
my $N = @_.end;
my $M = @_.head(*-1).first(@_.tail):end:k // $N;
return $N - $M;
}
如果 .first 搜索没有找到前面的匹配，它将返回一个未定义的值来代替，所以后面的定义–或者干脆使用 N 值来代替，在这种情况下，N-M 将按要求为零。
当然，在已经减少了这么多代码之后，坚持使用$N和$M变量的唯一原因是为了自我记录.否则，我们可以简单地将 $N 用 @_.end 代替，将 $M 用新的 head-first-tail 搜索表达式代替，产生:
# Version 4...
sub next-vanEck's {
@_.end - (@_.head(*-1).first(@_.tail):end:k // @_.end)
}
这时，我们也几乎不需要命名的子例程。代替:
constant vanEck's
= 0, &next-vanEck's ... ∞;
我们可以简单地将子例程体 “内联"为一个代码块，产生一个真正的单语句解决方案:
constant vanEck's
= 0, {@_.end-(@_.head(*-1).first(@_.tail):end:k//@_.end)}...∞;
工作完成了！
或者是吗？当然，如果我们现在写:
say vanEck's[100]; # Should print: 23
……我们打印出了 23，正如预期的那样。
但如果我们写：
say vanEck's[10_000]; # Should print: 14
好吧，我们确实打印出了14个…最终。大约一分钟后。 :-(
如果我们想尝试 vanEck's[100_000]，我们就有时间在一个小时外的餐馆里……悠闲地吃午饭。如果我们想尝试 vanEck's[1_000_000]，我们就必须下周再来吃。
所以…我们设法让我们的解决方案尽可能的简单，但代价是非常糟糕的，完全不可扩展的运行时性能。
而且，当你停下来想一想，它运行得如此糟糕也就不足为奇了。为了生成下一个范埃克数字，我们的代码必须查看（可能）N-1 个早期数字中的每一个，将它们中的每一个与序列中最近的数字进行比较。换句话说，计算一个范埃克的数字需要 O(N) 次操作，所以计算其中的N个数字必须是 O(N²) 次。因此，找到序列中仅有的1万个数需要1分多钟，找到前10万个数需要几个小时，找到前100万个数需要近7天。
很显然，在我们能从无限供应的范埃克数中获得无数好处之前，我们需要找到一种方法来消除代码对象内部的那种重复的 O(N) 搜索。
可喜的是，这并不难。有一种算法上的洛伦兹收缩，我们可以经常应用于这类情况：我们可以通过扩大空间维度来缩小时间维度…。更简单地说，我们可以用更多的内存来换取额外的速度。
在这种情况下，我们的诀窍是永久地跟踪（在一个静态变量中）序列中每个数字的最近的前例的索引 M。 然后，当我们再次遇到这个数字时，我们可以在我们的变量上执行一次查找，以找到这个数字的最近的先前索引。那么我们要做的就是每次更新我们记忆中的 M 值（因为我们刚刚在后面的索引中又看到了同一个数字：N）。
基于这种方法的 next-vanEck 的子例程是这样的:
# Version 4...
sub next-vanEck's {
state @M;
my $N = @_.end;
my $M = @M[@_.tail] // $N;
@M[@_.tail] = $N;
return $N - $M;
}
@M 数组会跟踪每个前一个值的最近的前一个索引。所以，当我们需要该 M 值来计算下一个数字时，现在我们只需直接向上查找它的位置即可: @M[@_.tail]。
然后我们用当前值的最新位置更新 @M 数组: @M[@_.tail] = $N。
用这个版本的子例程运行序列操作，我们可以在大约15秒内计算出 vanEck's[10_000]，而不是60秒。性能的四倍提升总是令人欣喜的，但我们可以做得更好。
我们只是将前面的整个序列传递进来（作为 @_），这样我们就可以访问最终的值（@_.tail）和它发生时的 N 的当前值（@.end）。但是，我们可以，直接传入那个最终值。而且 N 的值只是在每次调用时递增，所以我们可以在另一个状态变量中琐碎地跟踪它。
这看起来像这样:
# Version 5...
sub next-vanEck's ($Aₙ) {
state ($N, @M);
$N++;
my $M = @M[$Aₙ] // $N;
@M[$Aₙ] = $N;
return $N - $M;
}
因为子例程现在只接受一个参数 $Aₙ（是的，Raku 允许在标识符中使用下标字母数字）。每次序列操作符产生新的值时，它现在只向代码对象传递到目前为止序列的最终值。
我们还通过每次调用子例程时递增$N来跟踪当前索引。
和以前一样，我们确定M值（现在是：@M[$Aₙ]），然后更新它，然后返回新计算的下一个值。
但是，由于序列运算符不再需要为它产生的每一个新数字将整个 sequence-so-far 传入子例程，因此每次调用 next-vanEck's 的成本明显下降。有了这个版本的子例程，我们计算 vanEck's[10_000] 的速度比之前快了大约100倍，大约0.15秒。或者在大约1.5秒内找到 vanEck's[100_000]。或者在大约15秒内找到 vanEck's[1_000_000]。这不仅比之前的方法快了一大截，现在的复杂度完全不同了：显然是 O(N) 线性时间，而不是 O(N²) 二次元。
然而，这种性能上的巨大改进并不是免费的。@M 数组的长度始终和序列本身一样长，约为 97%，虽然略显稀疏，但它可能只需要约 85% 的空间。尽管如此，这意味着这个解决方案的内存占用量与版本1相比实际上增加了一倍。在大多数情况下，这是一个完全可以接受的权衡：内存相对便宜；时间是无价的。
但我们是否也可以用一条语句来编写这个版本的代码呢？当然，我们可以。
再一次，我们只需将子例程的代码块内联:
constant vanEck's = 0, { state ($N, @M);
$N++;
my $M = @M[$^Aₙ] // $N;
@M[$^Aₙ] = $N;
$N - $M;
} ... ∞;
当然，如果我一开始就这么说，只是在没有任何警告和解释的情况下突然告诉你，那么你就会很有理由抱怨它的可怕和不可理解，而且（喘气！）与众不同。新概念、新方法、新工具和新语法总是充满挑战。尤其是同时使用这四种方法。
但是，当你了解了乐乐的强大和表现力，那么也许这样的解决方案就没那么可怕了，你开始明白，如何能用很像问题原始描述的东西，用很像问题原始符号的东西，写出看起来很像问题原始描述的代码，因此，对于任何已经熟悉任务域的人来说，其实更容易理解。
而且，因为在 Raku 中总是有不止一种方法，所以把那个最终版本写成还是完全可以的:
constant vanEck's = 0, &next-vanEck's ... ∞;
…将算法和优化隐藏在该子例程中。当你发现一个更聪明的方法，一个更好的算法，或者一个更有效的洛伦兹权衡时，再在子例程中改变它们。
Perl 和 Raku 都因为他们不折不扣的"不止一种方法"的理念而受到了很多抨击。但是，对我来说，这两种语言的灵活性和透明性意味着，我永远不会被不恰当的概念、低效的算法、不方便的软件工具、或者别人硬生生植入他们的"唯一正确的方法"中的固有性能限制所困扰。
而对我来说，这就使得选择 Raku 的原因…尽可能的简单。