RAM 크기보다 큰 데이터 정렬

Question

이것은 Google 인터뷰 질문입니다. 모든 정수 (8 바이트)를 포함하는 각각 64GB RAM을 갖춘 2 대의 컴퓨터가 전체 128GB 데이터를 정렬하면됩니다. 소량의 추가 RAM이 있다고 가정 할 수 있습니다. 이것을 확장하여 1000 대의 기계에 저장된 데이터를 정렬하십시오.

나는 외부 정렬을 제안했습니다. 우리는 전체 데이터를 청크로 나누고 병합 정렬을 사용합니다. 그것은 덩어리를 먼저 분류하고 다시 넣고 조각을 현명하게 합쳐 병합합니다. 더 좋은 방법이 있습니까? 무엇이 복잡할까요?

Answer 1

각각의 64GB는 quicksort를 별도로 사용하여 정렬 한 다음 64GB 어레이의 헤드에서 외부 메모리 유지 포인터를 사용하여 RAM1과 RAM2가 전체 데이터를 갖고 계속 증가하도록하고 포인터가 RAM1에 있으면 포인터가 RAM2에있는 포인터 값보다 작 으면 포인터가 RAM1의 끝에 도달 할 때까지 값을 RAM2로 바꿉니다.

은 모든 N RAM을 정렬하는 데 동일한 개념을 사용합니다. 쌍을 가져 와서 위의 방법으로 정렬하십시오. N/2 개의 정렬 된 RAM이 남아 있습니다. 재귀 적으로 같은 개념을 사용하십시오.

Answer 2

ChingPing은 각 하위 집합에 대해 O (n log n) 정렬을 제안한 다음 선형 병합 (요소를 교환하여)을 제안합니다. Quicksort (그리고 대부분의 n log n 종류의 문제는 n 개의 메모리가 필요하다는 것입니다.) 대신 상수 메모리를 사용하는 SmoothSort을 사용하고 O (n log n)에서 실행하는 것이 좋습니다.

최악의 경우 시나리오는 같은이 곳이다. 두 세트가 역으로 정렬

setA = [maxInt .. 1] 
setB = [0..minInt] 

을, 그러나 합병은 역순입니다

이

더 - ChingPing의 솔루션 (IMO 더 명확) 설명입니다 :

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; } 

세트가 모두 정렬되어야합니다.

Answer 3

이미 2 대의 컴퓨터 케이스에 대한 답변이 있습니다.

정렬 할 128GB의 데이터가 단일 하드 드라이브 (또는 외부 장치)에 단일 파일로 저장된다고 가정합니다. 얼마나 많은 기계 나 하드 드라이브가 사용되던간에 원본 128GB 파일을 읽고 정렬 된 128GB 파일을 쓰는 데 걸리는 시간은 동일하게 유지됩니다. 유일한 절약은 정렬 된 데이터 청크를 만드는 내부 RAM 기반 정렬 중에 발생합니다. n-1 하드 드라이브와 병합하여 남은 하드 드라이브에 단일 정렬 된 128GB 파일로 n 방향 병합을 수행하는 데 걸리는 시간은 동일하게 유지됩니다. 128GB 정렬 파일을 남은 시간에 기록하는 데 걸리는 시간으로 제한됩니다 하드 드라이브.

n 개의 컴퓨터의 경우 데이터가 128GB/n 청크로 분할됩니다. 각각의 머신은 랜덤 액세스 오버 헤드를 줄이기 위해 한 번에 64MB의 읽기 서브 덩어리를 교체 할 수 있으므로 "마지막"머신은 모든 이전 머신이 시작하기 전에 모든 덩어리를 읽을 때까지 기다리지 않습니다 .

n> = 4 인 n 개의 기계 (각각 64GB 램)와 n> = 4 인 n + 1 개의 하드 드라이브의 경우 O (n) 시간 복잡도의 기수 정렬을 각 기계가 사용하여 n 작업에서 32GB 이하의 청크를 생성 할 수 있습니다 하드 드라이브를 동시에 연결 한 다음 대상 하드 드라이브에 n 방향으로 병합합니다.

더 큰 n의 이점을 제한하는 수익률이 감소하는 지점이 있습니다. n> 16을 넘는 곳에서는 내부 병합 처리량이 디스크 I/O 대역폭보다 커질 수 있습니다.병합 프로세스가 I/O 바운드가 아닌 CPU 바운드 인 경우 I/O 시간보다 큰 병합 오버 헤드와 병렬로 청크를 만드는 데 걸리는 시간이 CPU 오버 헤드에서 균형을 유지합니다.