[HADOOP] 프라임 숫자 생성을위한 병렬 알고리즘 (아마도 하둡의 맵 축소를 사용)

프라임 숫자 생성을위한 병렬 알고리즘 (아마도 하둡의 맵 축소를 사용)

프라임 숫자를 생성하는 것은 종종 새로운 프로그래밍 언어, 플랫폼 또는 스타일을 실험 할 때 자주 시도하는 장난감 문제입니다.

나는 Hadoop (Map Reduce)을 사용하여 소수 생성 알고리즘이나 소수 테스트 알고리즘을 작성하려고 시도했다.

팁, 참조, 알고리즘, 접근법을 얻기 위해이 질문을 게시 할 것입니다.

필자의 주요 관심사는 Map Reduce 기반 알고리즘이지만 새로운 Hadoop 프로그래밍 모델을 보거나 PiCloud를 사용하는 예를들 수 있습니다.

Prime Number Generation에 대한 흥미로운 질문이 여기에 있습니다. 여기, 여기, 여기 있습니다. 그러나 병렬 접근과 관련된 것은 내 눈을 사로 잡았습니다.

미리 감사드립니다.

해결법

1. ==============================

   1.다음은 매핑 및 축소 (폴딩)를 기반으로하는 알고리즘입니다. 에라 토 스테 네스의 체를 표현합니다.

   다음은 매핑 및 축소 (폴딩)를 기반으로하는 알고리즘입니다. 에라 토 스테 네스의 체를 표현합니다.

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

   홀수 소수 (즉, 2가없는 경우). 접는 나무는 다음과 같이 무기한으로 오른쪽으로 깊어집니다.

   여기서 각각의 소수는 해당 소수의 홀수 배의 스트림을 표시한다. 7 : 49, 49 + 14, 49 + 28, ...은 모두 합쳐져 모든 합성 수를 얻습니다. 그리고 나서 소수는 합성 수 사이의 틈에서 발견됩니다. 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
   

   토론이 여기에 있습니다. 더 정교하고 게으른 스케줄링이 여기에 있습니다. 또한이 SO 응답은 발전기 측면에서 (관련) 하스켈 코드의 대략적인 변환을 보여줍니다. 이 하나는 파이썬에서.

from https://stackoverflow.com/questions/12559788/parallel-algorithms-for-generating-prime-numbers-possibly-using-hadoops-map-re by cc-by-sa and MIT license