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

Question

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

10

最近我在玩欧拉计划中的第14个问题：在范围1-1,000,000内，哪个数字生成的 Collatz序列最长？

我知道必须使用备忘录技术以获得合理的时间，下面这段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

问题

我是不是在两者之间翻译有误，或者差异是启动虚拟机等无法调和的问题？

是否有聪明的技巧/习语可以应用于Raku代码，将其速度显著提高？

附言

当然，这并不是关于这个特定的Euler project问题；我更广泛地感兴趣的是是否有适用于Raku的任何神奇加速秘籍我不知道。

- grobber

也许获得Raku“神奇加速”的最佳方法是将其翻译成Python :-) 抱歉，我忍不住了，而且自从我使用Perl以来已经很长时间了，除了可能在代码中插入计时陷阱以查看延迟位置之外，我可能无法提供有用的答案。 - paxdiablo

很好，但这并不减弱我对这里实际发生的事情所持有的内在兴趣。 - grobber

grobber，同意，我并没有说你的问题无效，实际上它非常好。 - paxdiablo

1

@paxdiablo, .@grobber “也许获得Raku的“神奇加速”最好的方法是将其翻译成Python……我可能无法提供一个有用的答案”。 :-) 你已经做到了！ :) Raku(do)支持一个非常自动化的翻译系统。只需通过Inline直接使用现有（或新的）外语代码（无需手动翻译），就可以像使用本地Raku一样使用外国特性！所有数据、异常等都会自动编组。如果您单击链接，您将看到正在开发的Inline::Python。也许可以试试？ - raiph

可能会看到使用“use experimental:cached”功能的改进。 - Coke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brad Gilbert · Accepted Answer

我认为额外花费的时间主要是因为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
}