我最近在玩problem 14的Euler project
: 1..1_000_000
范围内的哪个数字产生最长的Collatz sequence ?
我知道必须 memoize 的问题获得合理的时间,以及以下 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)
(改编自 here ;我更喜欢这个不使用 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
的魔法加速奥秘更感兴趣。我不知道。
最佳答案
我认为大部分额外时间是因为 Raku 具有类型检查,并且它们没有被运行时类型专门化程序删除。或者,如果它们被删除,则需要很长时间。
通常优化 Raku 代码的方法是首先使用分析器运行它:
$ raku --profile test.raku
当然,这段代码的 Segfault 会失败,所以我们不能使用它。我的猜测是大部分时间都与使用哈希有关。
如果已实现,则使用 native 整数作为键和值可能会有所帮助:
my int %cllens{int} = (1 => 1);
然后将函数声明为使用 native 大小的整数可能是一个更大的胜利。(目前这充其量只是一个小的改进。)
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
}
关于python - 为什么这个记忆化的 Euler14 实现在 Raku 中比 Python 慢得多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64851261/