这个素数相关谓词的瓶颈是什么？

所以在这里，它是：我想要计算如下两百万元（为this problem）所有质数的和，但我的计划是非常缓慢的。我知道算法本身是非常糟糕的，而且是一种强力的算法，但它似乎比我应该慢的多。
在这里，我将搜索范围限制为20,000，以便结果不会等待太久。
我不认为这个谓词很难理解，但我会解释它：我计算所有素数低于20,000的列表，然后求和它们。总和部分是好的，素数部分真的很慢。这个素数相关谓词的瓶颈是什么？

problem_010(R) :- 
    p010(3, [], Primes), 
    sumlist([2|Primes], R). 
p010(20001, Primes, Primes) :- !. 
p010(Current, Primes, Result) :- 
    (
     prime(Current, Primes) 
    -> append([Primes, [Current]], NewPrimes) 
    ; NewPrimes = Primes 
    ), 
    NewCurrent is Current + 2, 
    p010(NewCurrent, NewPrimes, Result). 
prime(_, []) :- !. 
prime(N, [Prime|_Primes]) :- 0 is N mod Prime, !, fail. 
prime(ToTest, [_|Primes]) :- prime(ToTest, Primes).

我想了解一下它为什么如此之慢。这是愚蠢的蛮力算法的一个很好的实现，还是有一些原因，使Prolog下降？

编辑：我已经找到了，通过添加新的素数，而不是在列表中的头让他们，我有在启动所以它的速度更快〜3倍以上经常发生的素数。还是需要一些有识之士虽然:)

来源

2011-11-29 m09

好的，在编辑之前，问题只是算法（imho）。正如你注意到的那样，检查数字是否被第一个较小的素数分开更为有效;在一个有限集合中，有更多的数字可被3除以32147整除。

另一种改进算法是停止检查素数是否大于数字的平方根。

现在，您的更改后确实存在一些序言问题：您使用append/3。 append/3很慢，因为您必须遍历整个列表才能将元素放在最后。相反，您应该使用差异列表，这使得将元素置于尾部非常快。

现在，有什么不同之处？不是创建一个正常列表[1,2,3]，而是创建这个[1,2,3 | T]。请注意，我们让尾巴不被证实。然后，如果我们想在列表的末尾添加一个元素（或更多），我们可以简单地说T = [4 | NT]。真棒？

以下解决方案（当素数> sqrt（N），差异列表追加时停止素数）在20k素数时为0.063，在2m素数时为17sec，而原始代码在20k时需要3.7sec，并且追加/ 3版本1.3秒。

problem_010(R) :- 
    p010(3, Primes, Primes), 
    sumlist([2|Primes], R). 
p010(2000001, _Primes,[]) :- !.        %checking for primes till 2mil 
p010(Current, Primes,PrimesTail) :- 
    R is sqrt(Current), 
    (
     prime(R,Current, Primes) 
    -> PrimesTail = [Current|NewPrimesTail] 
    ; NewPrimesTail = PrimesTail 
    ), 
    NewCurrent is Current + 2, 
    p010(NewCurrent, Primes,NewPrimesTail). 
prime(_,_, Tail) :- var(Tail),!. 
prime(R,_N, [Prime|_Primes]):- 
    Prime>R. 
prime(_R,N, [Prime|_Primes]) :-0 is N mod Prime, !, fail. 
prime(R,ToTest, [_|Primes]) :- prime(R,ToTest, Primes).

此外，考虑当你生成他们避免因为最终sumlist/2
的额外的O（N）添加数字，你总是可以实现，在多项式时间内运行的AKS算法（XD ）

来源

2011-11-29 13:34:38

@false这是...有趣。事实上，它返回142913828922，虽然我会发誓它第一次返回21171191：检查它atm –

对不起，我收回了我的评论：您正在使用更大的数字！不是20001，而是2000001 – false

@false是的，我刚刚意识到它也是xp！ –

一，序言不会失败在这里。

有非常聪明的方法如何生成素数。但作为一个便宜的开始，只需按相反的顺序累积素数！（7.9s - > 2.6s）以这种方式，更小的测试更快。然后，考虑只对141以下的素数进行测试。较大的素数不能是一个因素。

然后，而不是仅仅通过数字不被2整除步进，您可以添加3，5，7

还有人对这个“问题”写论文。见，例如this paper，虽然这是一个有点诡辩讨论什么是“真正的”算法实际上是，22个世纪以前，当算盘的最新版本为庆祝Salamis tablets的。

来源

2011-11-29 13:27:28 false

是的，这是更多的算法问题，这正是我想知道的！谢谢。我会看看这篇文章。 – m09

什么是“Salaminic表”？谷歌搜索没有帮助。 :)（对于2,000,000的限制是1414 btw）。 –

@威尔斯：对不起，不知道这个形容词不存在英文，我纠正了它（包括一个链接）。 – false

首先，在使用append/3一个列表的末尾附加是相当缓慢。如果您必须，请使用差异列表。（就个人而言，我会尽量避免append/3尽可能）

其次，你prime/2在整个列表总是循环检查的首要时。这是不必要的缓慢。你可以改为检查id，你可以找到一个整数因子，直到你想检查的数字的平方根。

problem_010(R) :- 
    p010(3, 2, R). 
p010(2000001, Primes, Primes) :- !. 
p010(Current, In, Result) :- 
    (prime(Current) -> Out is In+Current ; Out=In), 
    NewCurrent is Current + 2, 
    p010(NewCurrent, Out, Result). 

prime(2). 
prime(3). 
prime(X) :- 
    integer(X), 
    X > 3, 
    X mod 2 =\= 0, 
    \+is_composite(X, 3). % was: has_factor(X, 3) 

is_composite(X, F) :-  % was: has_factor(X, F) 
    X mod F =:= 0, !. 
is_composite(X, F) :- 
    F * F < X, 
    F2 is F + 2, 
    is_composite(X, F2).

免责声明：我发现这个实现的prime/1和has_factor/2通过谷歌搜索。

该代码给出：

?- problem_010(R). 
R = 142913828922 
Yes (12.87s cpu)

这是更快代码：

problem_010(R) :- 
    Max = 2000001, 
    functor(Bools, [], Max), 
    Sqrt is integer(floor(sqrt(Max))), 
    remove_multiples(2, Sqrt, Max, Bools), 
    compute_sum(2, Max, 0, R, Bools). 

% up to square root of Max, remove multiples by setting bool to 0 
remove_multiples(I, Sqrt, _, _) :- I > Sqrt, !. 
remove_multiples(I, Sqrt, Max, Bools) :- 
    arg(I, Bools, B), 
    (
     B == 0 
    -> 
     true % already removed: do nothing 
    ; 
     J is 2*I, % start at next multiple of I 
     remove(J, I, Max, Bools) 
    ), 
    I1 is I+1, 
    remove_multiples(I1, Sqrt, Max, Bools). 

remove(I, _, Max, _) :- I > Max, !. 
remove(I, Add, Max, Bools) :- 
    arg(I, Bools, 0), % remove multiple by setting bool to 0 
    J is I+Add, 
    remove(J, Add, Max, Bools). 

% sum up places that are not zero 
compute_sum(Max, Max, R, R, _) :- !. 
compute_sum(I, Max, RI, R, Bools) :- 
    arg(I, Bools, B), 
    (B == 0 -> RO = RI ; RO is RI + I), 
    I1 is I+1, 
    compute_sum(I1, Max, RO, R, Bools).

这将运行一个数量级，比我上面给的代码快：

?- problem_010(R). 
R = 142913828922 
Yes (0.82s cpu)

来源

2011-11-29 13:31:25 twinterer

真的很不错** prime/1 **和** has_factor/2 **谓词！谢谢。 – m09

谢谢，但正如我所说，他们不是我的。我通过寻找erastothenes筛选来找到他们。但是，我在我的答案中添加了另一个版本，它不使用这些谓词，并且通过使用列表来加快速度。 – twinterer

不错的一个，我在Mat的评论后正在研究类似的东西...... – m09

考虑使用例如筛法（“Eratosthenes筛”）：首先创建列表[2,3,4,5,6，... N]，用于例子e numlist/3。列表中的第一个数字是素数，保留它。从列表的其余部分中删除其倍数。剩下的列表中的下一个数字再次是一个总数。再次消除其倍数。等等。该名单将缩小得相当迅速，并且最终只剩下素数。

来源

2011-11-29 13:33:58 mat

当我用这个强力东西来看看它是怎么回事时，我会实现它:)感谢您的建议！ – m09

你应该只*** ***数字复合，***不能删除***他们，否则你将无法正确计数，将被迫测试分隔每个孤立，或比较它们与生成的倍数 - 仍然比在一个给定的偏移量处标记数字更糟糕。当然，使用复合词作为数组替代品是一个巨大的性能增强器，在这里。 –

这个素数相关谓词的瓶颈是什么？

回答

相关问题