這個素數相關謂詞的瓶頸是什麼？

所以在這裏，它是：我想要計算如下兩百萬元（爲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

你應該只*** ***數字複合，***不能刪除***他們，否則你將無法正確計數，將被迫測試分隔每個孤立，或比較它們與生成的倍數 - 仍然比在一個給定的偏移量處標記數字更糟糕。當然，使用複合詞作爲數組替代品是一個巨大的性能增強器，在這裏。 –

這個素數相關謂詞的瓶頸是什麼？

回答

相關問題