生成素数的并行算法(可能使用 Hadoop 的 map reduce) [英] Parallel Algorithms for Generating Prime Numbers (possibly using Hadoop's map reduce)

问题描述

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

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

我想我会发布这个问题来获取技巧、参考、算法、方法.

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

其中每个素数标记该素数的奇数倍流，例如for 7: 49, 49+14, 49+28, ... ，它们都合并得到所有合数，然后质数em> 位于合数之间的间隙中.它在 Haskell 中，所以时间由惰性求值机制 _{隐式处理(以及算法调整，其中每个比较节点总是让从左边开始的第一个数字不要求一个数字从右边开始，因为无论如何它肯定会更大)}.

Odds 可以用来代替奇素数作为生成倍数的种子，以简化事情(具有明显的性能影响).

工作自然可以分成连续素数平方之间的部分.下面是 Haskell 代码，但我们也可以把它看成一个可执行的伪代码fx，括号只用于分组):

primes = 2 : g []在哪里g ps = 3 : 减去 [5,7..] (_U [[p*p, p*p+2*p..] | p <- g ps])_U ((x:xs):t) = x : union xs (_U (pairs t))对((x:xs):ys:t)=(x:联合xs ys):对tunion (x:xs) (y:ys) = case compare x y ofLT->x : 联合 xs (y:ys)情商 ->x : 联合 xs ysGT ->y : 联合 (x:xs) ys减去 (x:xs) (y:ys) = case 比较 x yLT->x : 减去 xs (y:ys)情商 ->减去 xs ysGT ->减去 (x:xs) ys

讨论在这里.更复杂、更懒惰的调度是这里.此外，this SO answer 显示了(相关)Haskell 代码在生成器方面的近似翻译；这个在 Python 中.

Generating Prime numbers is a toy problem that I often attempt from time to time, especially when experimenting with a new programming language, platform or style.

I was thinking of attempting to write a Prime Number Generation algorithm or a Prime Number Test Algorithm using Hadoop (Map Reduce).

I thought I'd post this question to get tips, references, to algorithms, approaches.

Although my primary interest is a Map Reduce based algorithm I wouldn't mind looking at new Hadoop programming models or for example looking at using PiCloud

I have seems some interesting questions here on Prime Number Generation: here, here and here, but nothing related to a Parallel approach caught my eye.

Thanks in advance.

解决方案

Here's an algorithm that is built on mapping and reducing (folding). It expresses the sieve of Eratosthenes

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

for the odd primes (i.e without the 2). The folding tree is indefinitely deepening to the right, like this:

where each prime number marks a stream of odd multiples of that prime, e.g. for 7: 49, 49+14, 49+28, ... , which are all merged to get all the composite numbers, and then primes are found in the gaps between the composite numbers. It is in Haskell, so the timing is taken care of implicitly by the lazy evaluation mechanism _{(and the algorithmic adjustment where each comparing node always lets through the first number from the left without demanding a number from the right, because it is guaranteed to be bigger anyway)}.

Odds can be used instead of odd primes as seeds for multiples generation, to simplify things (with obvious performance implications).

The work can naturally be divided into segments between consecutive primes' squares. Haskell code follows, but we can regard it as an executable pseudocode too _{(where : is a list node lazy constructor, a function call f(x) is written f x, and parentheses are used for grouping only)}:

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

A discussion is here. More sophisticated, lazier scheduling is here. Also this SO answer shows approximate translation of (related) Haskell code in terms of generators; this one in Python.

这篇关于生成素数的并行算法(可能使用 Hadoop 的 map reduce)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！