这是来自欧拉项目的问题 36。对以 2 为底和以 10 为底的所有回文数低于 100 万的数字求和。
我最初尝试以更实用的方式解决它。
这在不到 6 秒的时间内运行。
[1..1_000_000]
.grep( * !%% 2 )
.grep( -> $x { $x == $x.flip } )
.grep( -> $y { $y.base(2) == $y.base(2).flip } )
.sum.say
令人惊讶的是，这花了 12 秒，即使我只生成奇数，因此跳过偶数测试。
(1,3 ... 1_000_000)
.grep( -> $x { $x == $x.flip } )
.grep( -> $y { $y.base(2) == $y.base(2).flip } )
.sum.say
这将在大约 3 秒内运行。
my @pals;
for (1,3 ... 1_000_000) -> $x {
next unless $x == $x.flip;
next unless $x.base(2) == $x.base(2).flip;
@pals.push($x);
}
say [+] @pals;
我还注意到使用
for (1,3 ... 1_000_000) -> $x { ...
和
for [1,3 ... 1_000_000] -> $x { ...
任何人都知道为什么流版本比迭代版本慢这么多？而且，为什么这两个 for 循环的性能会如此不同？
Jon*_*ton 12
该构造[...]是一个数组组合器。它急切地迭代在其中找到的可迭代对象，并将每个值存储到数组中。只有这样我们才能继续进行迭代。这会导致更多的内存分配并且对缓存不太友好。相比之下，括号没有任何作用（除了分组，但除此之外它们不添加任何语义）。因此：
[1..1_000_000]
.grep( * !%% 2 )
.grep( -> $x { $x == $x.flip } )
.grep( -> $y { $y.base(2) == $y.base(2).flip } )
.sum.say
将分配和设置一百万个元素数组并对其进行迭代，同时：
(1..1_000_000)
.grep( * !%% 2 )
.grep( -> $x { $x == $x.flip } )
.grep( -> $y { $y.base(2) == $y.base(2).flip } )
.sum.say
运行速度相当快，因为它不需要这样做。
此外，...运营商目前比..运营商慢得多。它并不会永远如此，只是到目前为止受到的关注要少得多。由于.grep也得到了很好的优化，因此过滤掉范围内的元素会更快 - 无论如何，现在。
最后，用==比较的（串）的结果base，并flip没有那么有效，因为它解析它们放回整数，当我们可以使用eq和比较字符串：
(1 .. 1_000_000)
.grep(* !%% 2)
.grep( -> $x { $x eq $x.flip } )
.grep( -> $y { $y.base(2) eq $y.base(2).flip } )
.sum.say
\n如果您想要更快的东西，您可以编写自己的序列生成器。
\n\ngather {\n loop (my int $i = 1; $i < 1_000_000; $i += 2) {\n take $i\n }\n}\n.grep( -> $x { $x eq $x.flip } )\n.grep( -> $y { $y.base(2) eq $y.base(2).flip } )\n.sum.say\n大约需要 4 秒。
\n\n或者为了更快，您可以自己创建 Iterator 对象。
\n\nclass Odd does Iterator {\n has uint $!count = 1;\n\n method pull-one () {\n if ($!count += 2) < 1_000_000 {\n $!count\n } else {\n IterationEnd\n }\n }\n}\n\nSeq.new(Odd.new)\n.grep( -> $x { $x == $x.flip } )\n.grep( -> $y { $y.base(2) == $y.base(2).flip } )\n.sum.say\n这只需要大约 2 秒。
\n\n当然，如果您想尽可能快地进行，请完全摆脱序列迭代。
\n\n也使用本机ints。
还缓存以 10 为基数的字符串。(my $s = ~$x)
my int $acc = 0;\nloop ( my int $x = 1; $x < 1_000_000; $x += 2) {\n next unless (my $s = ~$x) eq $s.flip;\n next unless $x.base(2) eq $x.base(2).flip;\n $acc += $x\n}\nsay $acc;\n这使它减少到大约几0.45秒钟。
（缓存.base(2)似乎没有做任何事情。）
在不直接使用操作的情况下，这可能接近最小值nqp。
我尝试编写一个本机 int 位翻转器，但它使它变慢。0.5秒。
\n（这个算法不是我想出来的，我只是将它改编到了Raku。我还添加了+>\xc2\xa0$in.msb来解决这个问题。）
我猜想spesh正在离开不需要在那里的操作。
\n或者可能JIT效果不太好。
对于大于 的值，它的性能可能会更高1_000_000。
\n(.base(2).flip是O(log\xc2\xa0n)而这是O(1)。)
sub flip-bits ( int $in --> int ) {\n my int $n =\n ((($in +& (my int $ = 0xaaaaaaaa)) +> 1) +| (($in +& (my int $ = 0x55555555)) +< 1));\n $n = ((($n +& (my int $ = 0xcccccccc)) +> 2) +| (($n +& (my int $ = 0x33333333)) +< 2));\n $n = ((($n +& (my int $ = 0xf0f0f0f0)) +> 4) +| (($n +& (my int $ = 0x0f0f0f0f)) +< 4));\n $n = ((($n +& (my int $ = 0xff00ff00)) +> 8) +| (($n +& (my int $ = 0x00ff00ff)) +< 8));\n ((($n +> 16) +| ($n+< 16)) +> (32 - 1 - $in.msb)) +& (my int $ = 0xffffffff);\n}\n\n\xe2\x80\xa6\n\n # next unless (my $s = ~$x) eq $s.flip;\n next unless $x == flip-bits($x);\n您甚至可以尝试使用多线程。
\n\n请注意，此工作量太小，无法发挥作用。
\n使用线程的开销掩盖了任何好处。
my atomicint $total = 0;\n\nsub process ( int $s, int $e ) {\n # these are so the block lambda works properly\n # (works around what I think is a bug)\n my int $ = $s;\n my int $ = $e;\n\n start {\n my int $acc = 0;\n loop ( my int $x = $s; $x < $e; $x += 2) {\n next unless (my $s = ~$x) eq $s.flip;\n next unless $x.base(2) eq $x.base(2).flip;\n $acc += $x;\n }\n $total \xe2\x9a\x9b+= $acc;\n }\n}\n\n\nmy int $cores = (Kernel.cpu-cores * 2.2).Int;\n\nmy int $per = 1_000_000 div $cores;\n++$per if $per * $cores < 1_000_000;\n\nmy @promises;\n\nmy int $start = 1;\nfor ^$cores {\n my int $end = $start + $per - 2;\n $end = 1_000_000 if $end > 1_000_000;\n\n push @promises, process $start, $end;\n\n#say $start, "\\t", $end;\n\n $start = $end + 2;\n}\n\nawait @promises;\nsay $total;\n运行时间大约是几0.63秒钟。
\n（我弄乱了该2.2值以在我的计算机上找到接近最短的时间。）