为什么这个 memoized Euler14 实现在 Raku 中比 Python 慢得多？

Question

我最近在玩 problem 14 of the Euler project: which number in the range 1..1_000_000 produces the longest Collatz sequence?

我知道必须 memoize 才能获得合理时间的问题，下面的一段 Python 代码 return 使用该技术可以相对快速地得到答案（记忆到字典）：

#!/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)

（改编自here；我更喜欢这个不使用max的版本，因为我可能想fiddle用它来return最长的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

问题

我是不是把两者翻译错了，或者是启动虚拟机等不可调和的问题？

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

一边

当然，这不是关于这个特定的 Euler project 问题；我更感兴趣的是是否有适合我不知道的 Raku 的魔法加速奥秘。

Answer 1

我认为大部分额外时间是因为 Raku 有类型检查，并且它们没有被运行time 类型专家删除。或者，如果他们被移除，那是在很长一段时间之后。

通常优化 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
}

为什么这个 memoized Euler14 实现在 Raku 中比 Python 慢得多？

why is this memoized Euler14 implementation so much slower in Raku than Python?

python

raku

memoization

collatz