为什么这个记忆化的 Euler14 实现在 Raku 中比 Python 慢得多？

Question

我最近摆弄问题14的Euler project：该范围内数1..1_000_000的最长的在Collat​​z序列？

我知道必须记忆以获得合理时间的问题，并且以下Python代码使用该技术相对快速地返回答案（记忆到字典）：

#!/usr/bin/env python

L = 1_000_000
cllens={1:1}

cltz = lambda n: 3*n + 1 if n%2 else n//2

def cllen(n):
    if n not in cllens: cllens[n] = cllen(cltz(n)) + 1
    return cllens[n]

maxn=1
for i in range(1,L+1):
    ln=cllen(i)
    if (ln > cllens[maxn]): maxn=i

print(maxn)

（从这里改编；我更喜欢这个不使用的版本max，因为我可能想摆弄它以返回最长的 10 个序列等）。

我试图将其翻译为尽可能Raku保持语义上的接近：

#!/usr/bin/env perl6
use v6;

my $L=1_000_000;
my %cllens = (1 => 1);

sub cltz($n) { ($n %% 2) ?? ($n div 2) !! (3*$n+1) }

sub cllen($n) {
    (! %cllens{$n}) && (%cllens{$n} = 1+cllen($n.&cltz));
    %cllens{$n};
}

my $maxn=1;
for (1..$L) {
    my $ln = cllen($_);
    ($ln > %cllens{$maxn}) && ($maxn = $_)
}
say $maxn

以下是我一直在运行这些的次数：

$ time <python script>
837799

real    0m1.244s
user    0m1.179s
sys     0m0.064s

另一方面，在Raku：

$ time <raku script>
837799

real    0m21.828s
user    0m21.677s
sys     0m0.228s

问题）

我是否在两者之间翻译有误，或者差异是启动 VM 等不可调和的问题吗？

是否有巧妙的调整/习惯用法可以应用于Raku代码以大大加快速度？

在旁边

自然，这不是关于这个特定Euler project问题的。我对是否有任何适合Raku我不知道的神奇加速奥秘更感兴趣。

Answer 1

我认为大部分额外时间是因为 Raku 进行了类型检查，并且它们不会被运行时类型专门程序删除。或者，如果它们被移除，则是在很长一段时间之后。

通常优化 Raku 代码的方法是首先使用分析器运行它：

$ raku --profile test.raku

当然，此代码会因段错误而失败，因此我们无法使用它。

我的猜测是大部分时间都与使用哈希有关。

如果实现了，对键和值使用本机整数可能会有所帮助：

 my int %cllens{int} = (1 => 1);

然后将函数声明为使用本机大小的整数可能是一个更大的胜利。
（目前，这充其量只是一个小改进。）

sub cltz ( int $n --> int ) {…}
sub cllen( int $n --> int ) {…}
for (1..$L) -> int $_ {…}

当然，就像我说的未实现本机散列，所以这纯粹是猜测。

您可以尝试使用 Raku 的多进程功能，但共享%cllens变量可能存在问题。

问题也可能是因为递归。（结合上述类型检查。）

如果你重写cllen它使用循环而不是递归，这可能会有所帮助。

注意：
最接近n not in cllens的可能是%cllens{$n}:!exists.
尽管这可能比仅检查值不为零要慢。

也是cellen有点可怕。我会更像这样写：

sub cllen($n) {
    %cllens{$n} //= cllen(cltz($n)) + 1
}