16 / 16강

큰 데이터를 다루는 방법

알고리즘이 정확하고 연산 수도 적어 보이는데 느릴 수 있습니다. 데이터가 메모리에 들어가는지, 작업을 동시에 처리할 수 있는지, 결과를 주고받는 데 드는 비용은 얼마인지도 살펴봐야 합니다.

나눠서 동시에 처리하기

큰 목록의 합은 여러 구간의 합을 따로 구한 뒤 합칠 수 있습니다. 하지만 서로의 결과를 기다려야 하는 부분은 마음대로 나눌 수 없습니다.

전체 작업의 80%를 병렬화하고 20%는 순서대로 해야 한다고 합시다. 통신 비용이 없고 작업이 완벽히 나뉜다고 해도, 처리 장치 4개의 시간은 원래의 0.2 + 0.8/4 = 0.4입니다. 속도는 4배가 아니라 2.5배입니다. 이것이 암달의 법칙이 설명하는 한계입니다.

실제로는 작업 나누기, 데이터 전달, 동기화 비용도 듭니다. 아주 작은 작업을 지나치게 잘게 나누면 오히려 느려질 수 있습니다.

메모리에 다 들어가지 않는 정렬

파일이 너무 크면 한 번에 리스트로 읽을 수 없습니다. 외부 정렬에서는 다음처럼 처리합니다.

1. 메모리에 들어갈 크기로 읽습니다.
2. 각 묶음을 정렬해 저장합니다.
3. 정렬된 묶음의 앞부분을 조금씩 읽으며 합병합니다.

합병 정렬의 아이디어를 저장 장치의 제약에 맞춰 쓰는 것입니다. 이때는 비교 횟수뿐 아니라 디스크에서 읽고 쓰는 횟수도 중요한 비용입니다. B 트리처럼 여러 키를 한 노드에 모으는 구조도 블록 접근 횟수를 줄이는 목적이 있습니다.

마지막 연습: 풀이를 고르는 순서

문제를 받으면 다음 순서로 적어 보세요.

• 입력, 출력, 예외와 경계 조건
• 일단 맞는 단순한 풀이와 비용
• 입력 크기에서 그 비용을 감당할 수 있는지
• 반복 계산, 불필요한 후보, 재사용할 정렬이나 인덱스
• 풀이가 맞는 이유와 그 전제를 깨는 반례

확인 문제

정렬되지 않은 큰 파일에서 최댓값 하나만 필요합니다. 전체를 정렬하거나 메모리에 전부 올려야 할까요?