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

所以这就是：我正在尝试计算所有素数的总和低于两百万(对于 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倍.仍需要一些见解:)

好的,在编辑之前问题只是算法(imho).
正如您所注意到的,检查数字是否先用较小的素数进行分割会更有效;在有限集合中,有更多的数字被3整除,而不是32147.

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

现在,在你改变之后确实存在一些prolog问题：
你使用append / 3. append / 3非常慢,因为你必须遍历整个列表才能将元素放在最后.
相反,你应该使用差异列表,这使得元素在尾部非常快.

现在,差异清单是什么？而不是创建一个普通的列表[1,2,3],你创建这个[1,2,3 | T].请注意,我们将尾部未实例化.然后,如果我们想在列表的末尾添加一个元素(或更多),我们可以简单地说T = [4 | NT].真棒？

下面的解决方案(以相反的顺序累积素数,当素数> sqrt(N),要追加的差异列表时停止)对于20k素数需要0.063,对于2m素数需要17秒,而原始代码需要3.7秒用于20k和追加/ 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).

另外,考虑在生成它们时添加数字以避免额外的o(n)因为sumlist / 2最后,你总是可以实现在多项式时间(XD)下运行的AKS算法