我想一个并发的Sieve会很好用,但是我得到了bad_arity消息,我不确定为什么。有关我为什么有这个问题或如何正确编码它的任何建议?
这是我的代码,注释掉的部分是我尝试使事情并发的地方:
L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),
传递给spawn的乐趣继承了其环境中所需的部分(即I),因此无需显式传递它。
虽然计算质数总是很有趣,但请记住,Erlang并不是为解决这种问题而设计的。 Erlang是为大规模的actor-style并发性而设计的。它在所有数据并行计算示例上的表现可能都不太好。在许多情况下,使用ML等顺序解决方案会非常快,以至于任何数量的核心都不足以使Erlang赶上,并且例如F#和.NET任务并行库肯定是这些操作的更好工具。
两个快速的单进程 Erlang 素数生成器;sprimes 在约 2.7 秒内生成小于 2m 的所有素数,在我的电脑上(Macbook,2.4 GHz Core 2 Duo)fprimes 大约需要 3 秒。两者都基于埃拉托斯特尼筛法,但由于 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).
lazy:lazy/1和lazy:next/1是伪懒惰无限列表的简单实现:
lazy(L) ->
repeat(L).
repeat(L) -> L++[fun() -> L end].
next([F]) -> F()++[F];
next(L) -> L.
通过筛法生成质数并不是一个很适合并发的地方(但可以在检查可除性时使用并行性,尽管该操作不足以证明所有我迄今为止编写的并行过滤器的额外开销)。
`
埃拉托斯特尼筛法相当易于实现,但正如你所发现的那样,并不是最有效的。你尝试过阿特金筛法吗?
我喜欢欧拉计划。
关于素数生成器,我非常喜欢厄拉多塞筛法。
对于小于 200 万的数字,你可以尝试简单的 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分钟的时间内轻松地运行200万个列表。
编辑:附带说明,埃拉托斯特尼筛法可以轻松实现并且运行速度快,但是当你开始处理大型列表时就会变得难以控制。最简单的实现方法是使用布尔数组和int值来快速运行。问题在于您开始达到值的大小限制以及数组长度限制。 - 切换到字符串或位阵列实现有所帮助,但是仍然需要面对迭代大型列表的挑战。
Project Euler问题(我会说前50个问题中的大部分,如果不是更多)主要是关于暴力求解,再加上在选择边界时的一点巧思。
记得测试任何一个N是否为质数(通过暴力方法),你只需要看它是否被任何小于等于floor(sqrt(N)) + 1的质数整除,而不是N/2。
祝好运
这是一个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