用于生成素数的并行算法(可能使用Hadoop的map reduce)

Question

生成素数是一个玩具问题,我经常不时尝试,特别是在尝试新的编程语言,平台或风格时.

我正在考虑尝试使用Hadoop(Map Reduce)编写素数生成算法或素数测试算法.

我想我会发布这个问题,以获得提示,参考,算法,方法.

虽然我的主要兴趣是基于Map Reduce的算法,但我不介意查看新的Hadoop编程模型或者例如查看使用PiCloud

我在Prime数字生成中似乎有一些有趣的问题:这里,这里和这里,但没有任何与Parallel方法相关的问题引起了我的注意.

提前致谢.

Answer 1

这是一个基于映射和缩减(折叠)的算法.它表达了Eratosthenes的筛子

     P = {3,5,7,...}\U {{ p ²,p ² + 2p,p ² + 4p, ...} | p in P }

对于奇数素数(即没有2).折叠树无限深化,如下所示:

其中每个素数标记该素数的奇数倍流,例如7:49,49 + 14,49 + 28, ...,它们都被合并以获得所有复合数,然后在素数中找到素数.复合数之间的差距.它位于Haskell中,因此时间由惰性评估机制隐含地处理_{(以及算法调整,其中每个比较节点总是通过左边的第一个数字而不需要右边的数字,因为它保证是无论如何更大)}.

可以使用赔率而不是奇数素数作为多次生成的种子,以简化事物(具有明显的性能影响).

这项工作自然可以分为连续素数的正方形之间的片段.Haskell代码如下,但我们也可以将其视为可执行伪代码_{(其中:是列表节点惰性构造函数,函数调用f(x)是写入的f x,括号仅用于分组)}:

primes = 2 : g []
  where
    g ps = 3 : minus [5,7..] (_U [[p*p, p*p+2*p..] | p <- g ps])
    _U ((x:xs):t) = x : union xs (_U (pairs t))
    pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union  xs (y:ys) 
    EQ -> x : union  xs    ys 
    GT -> y : union (x:xs) ys

minus (x:xs) (y:ys) = case compare x y of
    LT -> x : minus  xs (y:ys) 
    EQ ->     minus  xs    ys 
    GT ->     minus (x:xs) ys

这里有一个讨论.更复杂的,懒惰的调度是在这里.另外这个苏答案显示在发电机方面(相关)Haskell代码大致翻译; 这是 Python中的一个.