Raku列表理解

Question

我在 Windows 10 i7 第 4 代笔记本电脑，8 GB RAM。

我想求出 1 到 1000000000 之间能被 5 整除的数字之和。

我正在尝试运行 Raku REPL 中的这段代码：

($_ if $_%5==0 for 1..1000000000).sum

代码运行ning 了 45 分钟，但仍然没有输出。我该如何克服它？

在这种情况下如何应用并发？我认为上述问题可以通过并发或任务并行来解决！！

Answer 1

比 1_000_000_000 低的值需要多长时间，比如 1_000_000？在我的机器上大约需要 3 秒。由此推断，要检查的值是原来的 1000 倍，这意味着需要大约 3000 秒。

为了加快速度，您可以使用 %%（可被整除）运算符，而不是 %（取模）：

($_ if $_ %% 5 for 1..1000000000).sum

FWIW，我希望这会更快。我会研究使 %% 更快，但恐怕您仍会查看算法的小时尺度时间。

Answer 2

How can I overcome it?

通过选择更好的算法：

让my \N = 1_000_000_000。您对价值感兴趣

[+] grep * %% 5, 1..N

与

相同

[+] map * * 5, 1..N/5

这又是

5 * [+] 1..N/5

Rakudo 足够聪明，可以在恒定时间内对一个范围求和，您将（几乎）立即得到结果。

Answer 3

它很慢，因为您正试图具体化大量项目。作为替代方案，您可以构建一个序列：(5, 10 … 1000000000).sum，但这仍然是具体化并保留大量元素，因此它仍然很慢。您可以制作一个 C 风格的循环并为每个增量添加总和，但这并不好玩（并且对于足够大的数字仍然很慢）。

你可以用数学来解决这个问题：能被 N 整除的数字是它的倍数，如果我们从这个序列中分解出 N，我们会发现你要找的所有数字的总和是 N * (1 + 2 + ... + floor 1000000000/N)。由于这是一个连续的范围，我们可以使用它的 Range.sum（它知道如何快速完成）来计算该部分。因此我们得到：

sub sum-of-stuff (\n, \d) { d * sum 1..n div d; }
say sum-of-stuff 1000000000, 5 # OUTPUT: 100000000500000000

所以这是计算问题的最快和最明智的方法，但这不是最有趣的！

您提到了并发性，所以让我们试一试这种方法。我们的问题是具体化的东西，所以我们需要想出一种方法来根据我们可用的核心数量来分块我们的原始数字范围，然后开始具体化工作并为每个单独的核心寻找乘数。然后我们将每个核心中的每个块中的东西求和，然后回到主线程并求和块的总和以获得最终答案。在代码中，它看起来像这样：

constant N = 10000;
constant DIV = 5;
constant CORES = 32;
constant batch = N div CORES;

(0, batch … N, N).rotor(2 => -1).flat.map({$^a^..$^b})
    .race(:batch :degree(CORES)).map(*.grep(* %% DIV).sum).sum.say;

batch是每个核心需要处理的chunk的大小，这是对每一位分解的所有工作的单行解释：

我们使用序列运算符创建一个0, batch, 2*batch, 3*batch的序列，依此类推，直到N。由于我们希望 N 成为其中的一部分，因此我们第二次包含它：

(0, batch … N, N)

我们现在想要的是使用那个序列创建一堆 Range 对象，我们想重复使用序列中的元素，所以我们使用 .rotor 和 batch of 2 and 1 的 backstep，然后展平子列表并使用 .map 创建 Range 对象（.map: *^..* 看起来好多了，但是唉，Whatever Stars 不想在这种安排中咖喱）：

.rotor(2 => -1).flat.map({$^a^..$^b})

现在是有趣的部分，我们使用 .race 方法创建一个 HyperSeq，因此使用我们所有的核心对其进行评估。它的 :batch 命名参数允许您指定每批处理多少个元素，它的 :degree 指定要使用多少线程。我们已经对数据进行了批处理，因此对于 :batch 我们使用 1。对于 :degree，我们使用核心数。为什么我们不告诉它对我们的东西进行批处理？因为具体化是我们的敌人，我们想在单独的线程中具体化。告诉它批量处理会在一个线程中具体化所有内容：

.race(:batch :degree(CORES))

现在我们拿到了 HyperSeq，我们可以映射它。每个项目都是我们的 Range 大小的对象，回想一下。所以我们会在上面调用 .grep，寻找可以被我们想要的除数整除的数字，然后我们会调用 .sum:

.map(*.grep(* %% DIV).sum)

最上面的最后一颗樱桃，我们要对每个chunk求和并打印结果，所以调用

.sum.say;

多田！

您也可以用这种方式重写有趣的部分，并使用 Promises 代替 .race:

say sum await (0, batch … N, N).rotor(2 => -1).flat.map:
    { start sum grep * %% DIV, $^a^..$^b }

相似但更短一些。过去用来为我们制作 Ranges 的地图现在也启动了一个 Promise（使用 start 关键字），它对块进行 greps 和求和。在该行的开头，我们添加了 await 以等待所有承诺的结果，然后汇总结果。

它仍然很慢，无法解决您原来的问题，因此为什么您应该改用一个好的算法 ;)

干杯。

Raku列表理解

Raku list comprehension

list-comprehension

raku