关于并发：并发Prime Generator

Concurrent Prime Generator

我正在研究projecteuler.net上的问题，以学习如何在Erlang中进行编程，而我最难的是创建一个素数生成器，该生成器可以在不到一分钟的时间内创建所有200万以下的素数。使用顺序样式，我已经编写了三种类型的生成器，包括Eratosthenes的Sieve，但是它们中的任何一个都不能表现良好。

我认为并发的Sieve可以很好地工作，但是我收到bad_arity消息，而且不确定为什么。关于我为什么有问题或如何正确编码的任何建议？

这是我的代码，注释掉的部分是我尝试使事情并发的地方：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

-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.

我使用Go和channel编写了Eratosthenesque并发初筛。

这是代码：http://github.com/aht/gosieve

我在这里写了关于它的博客：http://blog.onideas.ws/eratosthenes.go

该程序可以在大约10秒钟内筛选出前一百万个素数(所有素数最高为15,485,863)。筛是并发的，但是该算法主要是同步的：goroutines(" actor"，如果您愿意的话)之间需要太多同步点，因此它们不能并行自由漫游。

" badarity"错误表示您正在尝试使用错误数量的参数来调用" fun"。在这种情况下...

%% L = for(1，N，fun()-> spawn(fun(I)-> wait(I，N)end)end)，

for / 3函数期望有趣的是1，spawn / 1函数希望有趣的是0。请尝试以下操作：

1	L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),

传递给spawn的乐趣继承了环境的必要部分(即I)，因此无需显式传递它。

尽管计算素数总是很有趣，但是请记住，这不是Erlang旨在解决的问题。 Erlang是为大型actor风格的并发设计的。在所有数据并行计算示例上，它极有可能表现不佳。在许多情况下，例如ML中的顺序解决方案将是如此之快，以至于任何数量的内核都无法满足Erlang的需求，例如对于此类操作，F＃和.NET Task Parallel Library无疑是更好的工具。

您可以在此处找到四个不同的Erlang实现来查找质数(其中两个基于Eratosthenes的Sieve)。该链接还包含比较这4个解决方案的性能的图表。

要考虑的另一种选择是使用概率素数生成。在Joe的书("主要服务器")中有一个例子，我认为它使用了Miller-Rabin。

两个快速的单过程erlang素生成器； sprimes会在约2.7秒内在2m以下生成所有素数，在我的计算机(配备2.4 GHz Core 2 Duo的Macbook)上约f3秒钟生成fprimes。两者都基于Eratosthenes的Sieve，但是由于Erlang最适合列表而不是数组，因此它们都保留一个未消除质数的列表，按当前磁头检查可除性，并保留经过验证的质数的累加器。两者都还实施了原轮以初步减少清单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

-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是指伪惰性无限列表的简单实现：

1
2
3
4
5
6
7

lazy(L) ->
repeat(L).

repeat(L) -> L++[fun() -> L end].

next([F]) -> F()++[F];
next(L) -> L.

筛子的质数生成不是并发的好地方(但是它可以使用并行性检查可除性，尽管操作还不够复杂，不足以证明我到目前为止编写的所有并行过滤器的额外开销。)

素数并行算法：http://www.cs.cmu.edu/~scandal/cacm/node8.html

Eratosthenes筛网非常容易实现，但是-正如您所发现的-效率最高。您是否尝试过阿特金筛子？

阿特金筛子@维基百科

这是vb版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

'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

欧拉计划的问题(我想说的是前50个问题中的大多数，如果不是更多的话)主要是关于蛮力的问题，在选择边界时会出现一些独创性。

记住要测试N是否为素数(通过蛮力)，您只需要查看N是否可被楼数(sqrt(N))+ 1整除，而不是N / 2。

祝好运

我爱欧拉计划。

在主要发生器方面，我是Eratosthenes筛网的忠实拥护者。

对于2,000,000以下的数字，您可以尝试一个简单的isPrime check实现。我不知道您将如何使用erlang进行操作，但是逻辑很简单。

1
2
3
4
5
6
7
8
9

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运行了这样的列表

编辑：在一个侧面说明，Eratosthenes的筛子可以很容易地实现并快速运行，但是当您进入庞大的清单时变得笨拙。使用布尔数组和int值的最简单实现运行得非常快。问题在于您开始遇到限制值大小和数组长度的问题。 -切换到字符串或位数组实现很有帮助，但是您仍然面临着以较大的值遍历列表的挑战。