Golang 의 동시성을 이용한 소수 찾기

개요

 

Prime number, 소수는 1과 자기자신으로만 나눠지는 수이다.

소수를 찾는 오래되고도 확실한 방법은 에라토스테네스의 체가 있다. (Prime Sieve, Sieve of Eratosthenes)

- 에라토스테네스의 체: https://www.wikiwand.com/en/Sieve_of_Eratosthenes

 

Golang 의 동시성을 이용하여 에라토스테네스의 체를 구현해보자

 

개념이 잘 이해가 안되었던 부분

 

참고 링크: https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/

 

"주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다."

 

위의 내용을 읽어도 이해가 안되었었는데 칸 아카데미 동영상을 보고서야 이해가 되었다.

칸 아카데미: https://youtu.be/klcIklsWzrY

 

N 보다 작은 소수를 모두 구해보자.

1) 2 에서 N-1 까지의 숫자들중에서  찾아야 한다.

2) 2 는 소수, 2의 배수들은 모두 소수에서 탈락이다.

3) 3 은 소수, 3의 배수들은 모두 소수에서 탈락이다.

- 여기서 중요하다. 3의 배수들을 탈락시키는데 가장 먼저 탈락시키는 숫자는 3x3 = 9 이다. - 왜냐하면 3x2, 즉, 3보다 작은 숫자만큼의 배수는 이미 다 걸러냈기 때문이다. - 따라서, 3의 배수는 9부터, 12, 15, … 로 탈락시키면 된다.

4) 4 는 2의 배수이고, 5 까지만 보다. 5의 배수는 모두 탈락인데 5x5 = 25 부터 30, 35, 40, … 순서로  탈락시키면 된다.

5) 이러한 원리로 루트 N 이상의 숫자는 걸러낼 필요가 없어지게 된다. 

 

파이썬 구현을 보자. (from 한글 Wiki)

 

1) 모든 n 을 True 로 설정하고 2) 체로 거르는 숫자의 상한인 (n의 제곱근에서 소수점 이하를 뺀 정수인) m 을 구한다.   3) 그리고 2 부터 m 까지 루프를 돌면서 - 소수이면, 소수의 제곱부터 n 까지의 소수의 배수를 False 해준다. 4) 루프를 다 돌고나면, 2부터 n 까지의 숫자들 중에서 True 인 것만 리턴한다.

 

Golang 의 동시성을 이용한 계산을 해보자

 

 

참고 링크: https://divan.dev/posts/go_concurrency_visualize/

 

Concurrency 구현

 

Concurrency() 라는 함수의 흐름을 따라가보자   1) 채널 하나를 만들고 generate() 함수에 파라미터로  넣는다.  - generate() 함수는 해당 채널로 2 부터 104729 까지 숫자를 계속 넣어줄 것이다.   2) 그리고는 0 부터 9999 까지 for 루프를 돈다. - 이것은 총 10000 개의 소수를 구하겠다는 것이다.   3) 2부터 <-ch 가 나오니 2는 소수이다. - 그리고 ch 와 새로만든 ch1 을 filter() 함수에 파라미터로 넣는다.   filter() 함수를 차근히 보자   1) in 으로 들어오는 숫자들을 prime 으로  나눈 나머지가 0인 경우를 제외하고 2) out 으로 내보내고 있다.   예를 들어, 첫번째 for 문을 도는 경우를 보면 - in 으로는 3 부터 4, 5, 6 으로 계속 들어올 것이고 - 이것을 prime 인 2로 나누어서 나머지가 없는 경우가 아니면 (= 2의 배수 아님) - 다시 out 으로 내보낸다. 3, 5, 7, 9, …. 가 될 것이다. → 이건 한마디로 아직 소수인지 아닌지 모르는 숫자들이라는 거다.     두번째 for 문 까지만 보자 - in 으로는 5부터 7, 9, 11 이 계속 들어올 것이고 - 이것을 prime 인 3 으로  나누어서 나머지가 없는 경우가 아니면 (= 3의 배수 아님) - 다시 out 으로 내보낸다 5, 7, 11, … 가 될 것이다.   이렇게 104729 까지 계속하는 것이다.   (성능은 떠나서) 생성되는 고루틴들이 동시에 들어오는  값들을 처리하고 내보내는 것이다. → Pipe line 이다! 아름답다. → 하나의 고루틴이 다 끝나고 다음 고루틴으 실행되는 것이 아니라는 것을 주목하자.

 

Sequential 한 구현

 

내용은 위 파이썬 구현과 다를 바 없다. Concurrency 한 구현과의 동작 비교를 하려 구현해둠.

 

속도 비교 - Test code

 

 

간단히 처음 찾은 값 10개와 소요시간을 체크해 보았다.

 

 

소스코드의 fmt.Print 문들을 코멘트 처리한 다음 benchmark 도 해보았다.

 

 

결론

 

에라토스테네스의 체는 동시성, 파이프라인의 아름다움을 보여주기에는 아름다운 코드였지만

실제 성능은 (10000 개 까지는) 그냥 Sequnetial 한 코드가 훨씬 빨랐다. 메모리 사용량마저 Sequential 코드가 낫다.

→ 동시성이라고 항상 좋은 건 아니다.