Sum*_*nal 9 list-comprehension perl6 raku
我是Windows 10 i7第四代笔记本电脑,内存为8 GB.
我想找出1到1000000000的数字之和,可被5整除.
我试图在perl 6 REPL中运行此代码:
($_ if $_%5==0 for 1..1000000000).sum
代码运行45分钟,仍然没有输出.我怎么能克服它？
如何在这种情况下应用并发性？我认为上面的问题可以通过并发或任务并行来解决!
Chr*_*oph 17
我怎么能克服它？
通过选择更好的算法:
我们my \N = 1_000_000_000.你对价值感兴趣
[+] grep * %% 5, 1..N
这是一样的
[+] map * * 5, 1..N/5
反过来
5 * [+] 1..N/5
Rakudo非常聪明,可以在恒定时间内对一个范围进行求和,您可以立即获得结果(几乎).
小智 11
它很慢,因为你试图重新设计物品.作为一种替代方案,你可以构建一个序列:(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是每个核心需要处理的块的大小,这里是单行的解释,它完成了每个位的所有工作:
我们使用序列运算符来创建序列0, batch, 2*batch, 3*batch等等N.既然我们想N成为它的一部分,我们第二次包括它:
(0, batch … N, N)
我们现在想要的是使用该序列来创建一堆Range对象,我们想要重复使用序列中的元素,因此我们使用.rotor批处理2和后退1,然后展平子列表并用于.map创建Range对象(.map: *^..*看起来好多了,但唉,无论星星都不想在那种安排下讨好):
.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)
最后一个樱桃,我们想要总结每个块的总和并打印结果,所以我们打电话
.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等待所有承诺的结果,然后总结结果.
它仍然很慢,并没有帮助你原来的问题,因此你应该使用一个好的算法;)
干杯.
低于1_000_000_000,比如1_000_000需要多长时间？在我的机器上大约需要3秒钟.从中推断,要检查的值是1000倍,这意味着需要3000秒.
为了加快速度,可以使用%%(可被整除)运算符,而不是%(modulo):
($_ if $_ %% 5 for 1..1000000000).sum
FWIW,我预计这会更快.我会考虑更快地制作%%,但我担心你仍然会查看算法的小时刻度.