这个素数相关谓词的瓶颈是什么? [英] What is the bottleneck in this primes related predicate?

问题描述

所以这里是:我正在尝试计算低于 200 万的所有素数的总和(对于 这个问题)，但我的程序很慢.我确实知道算法本身非常糟糕并且是蛮力的，但它似乎比我应该的要慢.
在这里，我将搜索限制为 20,000，这样结果就不会等待太久.
我不认为这个谓词很难理解，但我还是会解释一下:我计算所有低于 20,000 的素数的列表，然后对它们求和.和部分很好，素数部分真的很慢.

So here it is : I'm trying to calculate the sum of all primes below two millions (for this problem), but my program is very slow. I do know that the algorithm in itself is terribly bad and a brute force one, but it seems way slower than it should to me.
Here I limit the search to 20,000 so that the result isn't waited too long.
I don't think that this predicate is difficult to understand but I'll explain it anyway : I calculate the list of all the primes below 20,000 and then sum them. The sum part is fine, the primes part is really slow.

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 失败了?

I'd like some insight about why it is so slow. Is it a good implementation of the stupid brute force algorithm, or is there some reason that makes Prolog fall?

我已经找到了一些东西，通过附加新的素数而不是让它们在列表的头部，我的素数在开始时出现得更频繁，所以它快了 3 倍.不过仍然需要一些见解:)

EDIT : I already found something, by appending new primes instead of letting them in the head of the list, I have primes that occur more often at start so it's ~3 times faster. Still need some insight though :)

推荐答案

好的，在编辑之前问题只是算法(恕我直言).正如您所注意到的，首先检查数字是否除以较小的素数会更有效；在有限集中，能被 3 整除的数比被 32147 整除的数多.

OK, before the edit the problem was just the algorithm (imho). As you noticed, it's more efficient to check if the number is divided by the smaller primes first; in a finite set, there are more numbers divisible by 3 than by 32147.

另一个算法改进是在质数大于数字的平方根时停止检查.

Another algorithm improvement is to stop checking when the primes are greater than the square root of the number.

现在，在您进行更改后，确实存在一些序言问题:你使用追加/3.append/3 非常慢，因为您必须遍历整个列表才能将元素放在末尾.相反，您应该使用差异列表，这使得将元素放在尾部非常快.

Now, after your change there are indeed some prolog issues: you use append/3. append/3 is quite slow since you have to traverse the whole list to place the element at the end. Instead, you should use difference lists, which makes placing the element at the tail really fast.

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

Now, what is a difference list? Instead of creating a normal list [1,2,3] you create this one [1,2,3|T]. Notice that we leave the tail uninstantiated. Then, if we want to add one element (or more) at the end of the list we can simply say T=[4|NT]. awesome?

以下解决方案(以相反的顺序累积素数，当素数>sqrt(N)时停止，要追加的差异列表)对于 20k 素数需要 0.063，对于 2m 素数需要 17 秒，而您的原始代码对于 20k 和追加/3 版本 1.3 秒.

The following solution (accumulate primes in reverse order, stop when prime>sqrt(N), difference lists to append) takes 0.063 for 20k primes and 17sec for 2m primes while your original code took 3.7sec for 20k and the append/3 version 1.3sec.

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)

also, considering adding the numbers while you generate them to avoid the extra o(n) because of sumlist/2
in the end, you can always implement the AKS algorithm that runs in polynomial time (XD)

这篇关于这个素数相关谓词的瓶颈是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！