题
我正在解决projecteuler.net上的问题来学习如何在Erlang中编程,并且我在创建一个素数生成器时遇到了最困难的时候,它可以在不到一分钟的时间内创建所有低于200万的素数。使用顺序风格,我已经编写了三种类型的生成器,包括埃拉托斯特尼筛法,但它们的性能都不够好。
我认为并发筛子会很好用,但我收到了 bad_arity 消息,我不确定为什么。关于为什么我会遇到这个问题或者如何正确编码有什么建议吗?
这是我的代码,注释掉的部分是我试图使事情并发的地方:
-module(primeserver). -compile(export_all). start() -> register(primes, spawn(fun() -> loop() end)). is_prime(N) -> rpc({is_prime,N}). rpc(Request) -> primes ! {self(), Request}, receive {primes, Response} -> Response end. loop() -> receive {From, {is_prime, N}} -> if N From ! {primes, false}; N =:= 2 -> From ! {primes, true}; N rem 2 =:= 0 -> From ! {primes, false}; true -> Values = is_not_prime(N), Val = not(lists:member(true, Values)), From ! {primes, Val} end, loop() end. for(N,N,_,F) -> [F(N)]; for(I,N,S,F) when I + S [F(I)|for(I+S, N, S, F)]; for(I,N,S,F) when I + S =:= N -> [F(I)|for(I+S, N, S, F)]; for(I,N,S,F) when I + S > N -> [F(I)]. get_list(I, Limit) -> if I [I*A || A [] end. is_not_prime(N) -> for(3, N, 2, fun(I) -> List = get_list(I,trunc(N/I)), lists:member(N,lists:flatten(List)) end ). %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end), %%SeedList = [A || A %% lists:foreach(fun(X) -> %% Pid ! {in_list, X} %% end, SeedList) %% end, L). %%wait(I,N) -> %% List = [I*A || A lists:member(X,List) %% end.
解决方案
“badarity”错误意味着您尝试使用错误数量的参数调用“fun”。在这种情况下...
%%L = for(1,N, fun() -> 产卵(fun(I) -> 等待(I,N) 结束) 结束),
for/3 函数期望 arity 1 的 fun,spawn/1 函数期望 arity 0 的 fun。试试这个:
L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),
传递给spawn的乐趣继承了其环境的所需部分(即I),因此无需显式传递它。
虽然计算素数总是很有趣,但请记住,这不是 Erlang 旨在解决的问题。Erlang 是为大规模 Actor 式并发而设计的。它很可能在所有数据并行计算的例子上表现得相当糟糕。在很多情况下, ML 中的顺序解决方案 速度如此之快,任何数量的内核都不足以让 Erlang 赶上,例如 F# 和 .NET 任务并行库 对于此类操作来说,肯定会是更好的工具。
其他提示
我使用 Go 和通道编写了一个埃拉托色式并发素数筛。
这是代码: http://github.com/aht/gosieve
我在这里写了一篇博客: http://blog.onideas.ws/eratosthenes.go
该程序可以在大约 10 秒内筛选出前一百万个素数(所有素数最多为 15,485,863)。筛子是并发的,但算法主要是同步的:goroutine(“参与者”——如果你愿意的话)之间需要太多的同步点,因此它们无法并行地自由漫游。
另一种可供考虑的替代方案是使用概率素数生成。Joe 的书中有一个这样的例子(“主服务器”),我认为它使用 Miller-Rabin...
您可以找到四种不同的 Erlang 实现来查找素数(其中两个基于埃拉托斯特尼筛法) 这里. 。此链接还包含比较 4 种解决方案性能的图表。
埃拉托斯特尼筛法相当容易实现,但正如您所发现的那样,它并不是最有效的。您尝试过阿特金筛吗?
两个快速单进程 Erlang 素数生成器;sprimes 在大约 2.7 秒内生成 2m 以下的所有素数,fprimes 在我的计算机上生成大约 3 秒(配备 2.4 GHz Core 2 Duo 的 Macbook)。两者都基于埃拉托斯特尼筛法,但由于 Erlang 最适合列表而不是数组,因此两者都保留一个非消除素数列表,检查当前头的整除性并保留已验证素数的累加器。两者都还实现了一个质数轮来对列表进行初始缩减。
-module(primes).
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).
sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)];
sieve(L, _) -> L.
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))].
wheel([X|Xs], _Js, M) when X > M ->
lists:reverse(Xs);
wheel([X|Xs], [J|Js], M) ->
wheel([X+J,X|Xs], lazy:next(Js), M);
wheel(S, Js, M) ->
wheel([S], lazy:lazy(Js), M).
fprimes(N) ->
fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N).
fprimes([H|T], A, Max) when H*H =< Max ->
fprimes(filter(H, T), [H|A], Max);
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L).
filter(N, L) ->
filter(N, N*N, L, []).
filter(N, N2, [X|Xs], A) when X < N2 ->
filter(N, N2, Xs, [X|A]);
filter(N, _N2, L, A) ->
filter(N, L, A).
filter(N, [X|Xs], A) when X rem N /= 0 ->
filter(N, Xs, [X|A]);
filter(N, [_X|Xs], A) ->
filter(N, Xs, A);
filter(_N, [], A) ->
lists:reverse(A).
懒惰:懒惰/ 1和懒惰:下一个/ 1指的是伪懒惰无限列表的简单实现:
lazy(L) ->
repeat(L).
repeat(L) -> L++[fun() -> L end].
next([F]) -> F()++[F];
next(L) -> L.
通过筛子生成素数并不是并发的好地方(但它可以使用并行性来检查整除性,尽管该操作还不够复杂,不足以证明我迄今为止编写的所有并行过滤器的额外开销是合理的)。
`
欧拉计划问题(我想说的是前 50 个问题中的大多数,如果不是更多的话)主要是关于蛮力,以及在选择边界时的独创性。
请记住测试任何 N 是否为素数(通过暴力),您只需要查看它是否可以被任何素数整除到 Floor(sqrt(N)) + 1,而不是 N/2。
祝你好运
我喜欢欧拉计划。
关于素数生成器的主题,我是埃拉托色尼筛法的忠实粉丝。
对于 2,000,000 以下的数字,您可以尝试简单的 isPrime 检查实现。我不知道你会如何在 erlang 中做到这一点,但逻辑很简单。
For Each NUMBER in LIST_OF_PRIMES
If TEST_VALUE % NUMBER == 0
Then FALSE
END
TRUE
if isPrime == TRUE add TEST_VALUE to your LIST_OF_PRIMES
iterate starting at 14 or so with a preset list of your beginning primes.
c# 在远低于 1 分钟的时间内运行了 2,000,000 个这样的列表
编辑: 顺便说一句,埃拉托斯特尼筛法可以轻松实现并且运行速度很快,但是当您开始进入庞大的列表时,它就会变得笨拙。最简单的实现,使用布尔数组和 int 值,运行速度非常快。问题是您开始遇到值大小和数组长度的限制。-- 切换到字符串或位数组实现会有所帮助,但您仍然面临以大值迭代列表的挑战。
这是一个VB版本
'Sieve of Eratosthenes
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of two (4, 6, 8 etc.).
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
'6. All the remaining numbers in the list are prime.
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
Dim thePrimes As New List(Of Integer)
Dim toNum As Integer = MaxNum, stpw As New Stopwatch
If toNum > 1 Then 'the first prime is 2
stpw.Start()
thePrimes.Capacity = toNum 'size the list
Dim idx As Integer
Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of 2, 3, 5.
For idx = 0 To toNum
If idx > 5 Then
If idx Mod 2 <> 0 _
AndAlso idx Mod 3 <> 0 _
AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
Else
thePrimes.Add(idx)
End If
Next
'mark 0,1 and 4 as non-prime
thePrimes(0) = -1
thePrimes(1) = -1
thePrimes(4) = -1
Dim aPrime, startAT As Integer
idx = 7 'starting at 7 check for primes and multiples
Do
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
'not equal to -1 the number is a prime
aPrime = thePrimes(idx)
'get rid of multiples
startAT = aPrime * aPrime
For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
Next
End If
idx += 2 'increment index
Loop While idx < stopAT
'6. All the remaining numbers in the list are prime.
thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
stpw.Stop()
Debug.WriteLine(stpw.ElapsedMilliseconds)
End If
Return thePrimes
End Function