并发素数生成器

Question

我正在解决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.

Answer 1

另一种可供考虑的替代方案是使用概率素数生成。 Joe 的书中有一个这样的例子（“主服务器”），我认为它使用 Miller-Rabin...

Answer 2

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

Answer 3

“badarity”错误意味着您尝试使用错误数量的参数调用“fun”。 在这种情况下...

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

for/3 函数需要一个 fun arity 1 的 fun，spawn/1 函数期望 arity 0 的 fun。请尝试这样做：

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

传递给 spawn 的 fun 继承其环境的所需部分（即 I），因此无需显式传递它。

虽然计算素数总是很有趣，但请记住，这不是 Erlang 旨在解决的问题。 Erlang 是为大规模 Actor 式并发而设计的。 它很可能在所有数据并行计算的例子上表现得相当糟糕。 在许多情况下，ML 中的顺序解决方案速度非常快，以至于任何数量的核心都不足以让 Erlang 赶上，例如 F# 和 .NET 任务并行库 对于此类操作无疑是更好的工具。

Answer 4

我使用 Go 和通道编写了一个埃拉托色式并发素数筛。

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

我在这里写了关于它的博客：< a href="http://blog.onideas.ws/eratosthenes.go" rel="noreferrer">http://blog.onideas.ws/eratosthenes.go

该程序可以筛选出前一百万个素数（15,485,863 以内的所有素数）大约需要 10 秒。 筛子是并发的，但算法主要是同步的：goroutines（“参与者”——如果你喜欢的话）之间需要太多的同步点，因此它们不能并行地自由漫游。

Answer 5

您可以找到四种不同的 Erlang 实现来查找素数（其中两个基于埃拉托斯特尼筛法）此处。 此链接还包含比较 4 种解决方案性能的图表。

Answer 6

埃拉托斯特尼筛法相当容易实现，但正如您所发现的那样，它并不是最有效的。 您尝试过阿特金筛吗？

阿特金筛@维基百科

Answer 7

两个快速单进程 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.

通过筛子生成素数并不是并发的好地方（但它可以使用并行性来检查整除性，尽管该操作不是足够复杂，足以证明我迄今为止编写的所有并行过滤器的额外开销是合理的）。

`

Answer 8

我喜欢欧拉计划。

关于素数生成器的主题，我是埃拉托色尼筛法的忠实粉丝。

对于 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 值，运行速度非常快。 问题是您开始遇到值大小和数组长度的限制。 -- 切换到字符串或位数组实现会有所帮助，但您仍然面临着以大值迭代列表的挑战。

Answer 9

欧拉计划问题（我想说的是前 50 个问题中的大多数，如果不是更多的话）主要是关于蛮力，以及在选择边界时的独创性。

请记住测试任何 N 是否为素数（通过暴力），您只需要查看它是否可以被任何素数整除到 Floor(sqrt(N)) + 1，而不是 N/2。

祝你好运

Answer 10

这是一个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