병렬 알고리즘 (parallel algorithm)

정렬 알고리즘은 최고 O(n long n)실행 속도를 가질 수 있다. 하지만 병렬화된 퀵 정렬 알고리즘을 사용하면 O(n)시간에 배열을 정렬할 수 있다. 성능과 확장성에 좋은 알고리즘이다.

병렬 알고리즘은 설계하기가 어렵고 올바르게 동작하는지, 어느 정도의 속도 향상을 얻을 수 있는지 정확하게 파악하기도 어렵다. 속도 향상이 선형적이지 않다는 것이다. (한 개의 코어에서 두 개의 코어로 알고리즘을 돌린다고 하더라도 두 배로 빨라지는 것이 아니다.) 병렬화를 관리하는 데 들어가는 부담 과 로드 밸런싱 등의 여러 이유 때문이다.

맵리듀스

맵리듀스 알고리즘(mapReduce algorithm)은 분산 알고리즘 (distributed algorithm)의 하나이다. 아파치 하둡과 같은 오픈 소스 툴을 통해 사용할 수 있다.

데이터가 엄청나게 많은 테이블에서 복잡한 SQL쿼리를 돌리는 경우, 또는 아주 많은 일련의 작업을 수행해야 하는 경우 실행 시간을 단축시키고 싶을 떄 유용하다.

맵 함수(map function)과 리듀스 함수(reduce function)라는 두 개의 개념을 이용하여 만들어졌다.

맵 함수

배열을 입력으로 받아서 모든 원소에 같은 함수를 적용한다.

• 예시 :

## case 1
## 배열의 모든 원소의 값을 두 배로 만드는 경우
arr1 = [1,2,3,4,5]
arr2 = map(lambda x:2*x, arr1) 

## case 2
## 일련의 URL을 넣어주면 각 페이지를 다운로드 해서 그 내용을 arr2에 저장하는 경우 
arr1 = # list of URLs
arr2 = map(download_page, arr1)

'''
하나의 URL을 작업하는데는 얼마 걸리지 않겠지만 URL이 1000개로 많아진다면 시간이 오래 소요된다.
만약 100대의 컴퓨터가 있다면 map함수는 이 작업을 모든 컴퓨터에 골고루 배분한다. 
이것이 맵 리듀스에서 맵 함수의 개념이다.
'''

리듀스 함수

리스트 전체의 원소를 하나의 원소로 축소(reduce)하는 것이 핵심이다. 맵 함수가 하나의 배열에서 같은 크기의 다른 배열을 얻었다면, 리듀스에서는 이 배열을 하나의 원소로 변형한다.

• 예시

arr1 = [1,2,3,4,5]
reduce(lambda x,y: x+y, arr1)

# 이 경우에는 배열에 있는 모든 원소를 더한다.

맵리듀스는 이 두 가지의 개념을 이용해 여러 대의 컴퓨터에 분산되어 있는 데이터에 대한 질의를 수행한다. 데이터가 수십억개의 레코드로 이로우져 있더라도 일반 DB에서 몇 시간이 걸리는 작업을 단 몇 분만에 수행할 수 있다.

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘