분치 알고리즘: 대규모 계산 프레임워크인 MapReduce의 분치 사상을 이야기하다

MapReduce는 Google 빅데이터 처리 3중 하나이며, 나머지 2대는 GFS와 Bigtable

분리 알고리즘 이해하기

원문제를 n개의 규모가 비교적 작고 구조와 원문제가 비슷한 자문제로 나누어 이 자문제들을 귀속적으로 해결한 다음에 그 결과를 합쳐서 원문제의 해답을 얻는다
분할 알고리즘은 문제를 처리하는 사상이고 귀속은 프로그래밍 기교이다. 분할 알고리즘의 귀속 실현에서 각 층의 귀속은 이런 세 가지 조작과 관련된다.

분해: 원문제를 일계열자문제로 분해

해결: 각 하위 문제를 차례로 해결하고 하위 문제가 충분하면 직접 구해

합병: 하위 문제의 결과를 원문제로 합병

분치 알고리즘 응용 예 분석

질서도로 한 조의 데이터의 질서 정도를 나타내고 역순도는 한 조의 데이터의 무질서 정도를 나타낸다.
만약에 우리가 n개의 데이터를 가지고 있다면 데이터가 작은 것에서 큰 것으로 배열되기를 기대한다면 완전 질서정연한 데이터의 질서도는 n(n-1)/2이고 역질서도는 0이다. 반대로 역순서로 배열된 데이터의 질서도는 0이고 역질서도는 n(n-1)/2이다.
2, 4, 3, 1, 5, 6 역순 대 개수: 4
(2,1) (4,3) (4.1) (3,1)
어떻게 프로그래밍을 해서 한 그룹의 데이터의 질서 대 개수나 역순 대 개수를 구합니까?
분치 알고리즘을 적용하여 수조 A의 역순 대 개수를 구하고 수조를 앞뒤 반으로 나누어 A1A2의 역순 대 개수 K1K2를 계산한 다음에 A1A2의 역순 대 개수 K3를 계산한다. 수조 A의 역순 대 개수 = K1+K2+K3
어떻게 두 개의 하위 문제 A1 A2 사이의 역순 대 개수를 신속하게 계산해 냅니까?
병합 정렬은 두 개의 질서정연한 소수조를 하나의 질서정연한 수조로 합치는 작업이다. 실제로 이 병합 과정에서 이 두 소수조의 역순 대 개수를 계산할 수 있다.매번 합병 작업을 할 때마다 역순대 개수를 계산하고 계산된 역순대 개수를 합치면 그 다음에 수조의 역순대 개수를 구한다.

private int num = 0 ; // 

public int count (int[] a ,int n){
	num = 0 ;
	mergeSortCounting(a , 0 ,n-1);
	return num;
}

private void mergeSortCounting(int[] a ,int p ,int r){
	if (p >= r) return;
	int q = (p+r) / 2;
	mergeSortCounting(a,p,q);
	mergeSortCounting(a , q+1 ,r);
	merge(a , p , q , r);
}

private void merge(int[] a ,int p ,int q, int r){       // merge(int[] a ,int low ,int middle, int high)
	int i = p , j = q+1 , k = 0 ;
	int[] tmp = new int[r-p+1];
	while(i<=q && j <=r){
		if(a[i] <= a[j]){
			tmp[k++] = a[i++];
		}else{
			num += (q-i+1);   //  p-q ， a[j] 
			tmp[k++] = a[j++];
		}
	}
	while (i <= q){  // 
		tmp[k++] = a[i++];
	}
	while (j <= r){     // 
		tmp[k++] = a[j++];
	}
	for(i = 0 ; i <= r-p ;++i){         // tmp a
		a[p+i] = tmp[i];
	}
}

분산 치료 알고리즘에 대한 일반적인 질문:

2차원 평면에 n개의 점이 있는데 어떻게 두 거리가 가장 가까운 점 쌍을 신속하게 계산합니까?

두 개의 n*n의 행렬 A, B가 있는데 어떻게 두 행렬의 곱셈 C=A*B를 신속하게 구해낼 수 있습니까?

분치 사상이 해량의 데이터 처리에서의 응용

데이터 양이 메모리에 담을 수 없을 정도로 많은 문제를 해결하고 분치 사상을 이용하여 대량의 데이터 집합을 어떤 방법에 따라 몇 개의 작은 데이터 집합으로 나누고 각각의 작은 데이터 집합을 단독으로 메모리에 불러와 해결한 다음에 작은 데이터 집합을 빅데이터 집합으로 통합하면 메모리 제한을 극복할 수 있을 뿐만 아니라 다중 스레드나 다중 프로세서 처리도 이용하여 속도를 높일 수 있다.
예를 들어 10GB의 주문 순서를 정하면 먼저 주문서를 한 번 스캔하고 금액에 따라 10GB 파일을 몇 개의 금액 구간으로 구분할 수 있다. 예를 들어 1~100 101~200 사이에 다른 파일에 넣는 것이다. 이런 추측에 따라 모든 작은 파일은 메모리에 단독으로 불러올 수 있고 마지막에 질서정연한 작은 파일을 합치면 마지막 질서정연한 주문 데이터이다.

왜 MapReduce의 본질은 분치 사상이라고 말합니까?

만약 처리할 데이터가 1T, 10T, 100T라면 집단을 이용하여 병행 처리하는 것이 대세이다
MapReduce 프레임워크는 하나의 작업 스케줄러일 뿐입니다. 데이터와 데이터 사이에 관계 작업이 존재하는 것을 처리하는 것 외에 파일에 있는 단어가 나타나는 빈도를 통계할 수 있습니다. 그리고 꺼지지 않은 사람의 안개를 처리할 수 있습니다. 예를 들어 웹 페이지 분석, 단어 구분 등입니다.