계기
지난달 면접에서 면접관이 이 질문을 했는데, 그때 제대로 답변하지 못했습니다. 이후에 이 문제에 대해 진지하게 고민해보았고, 이 글에 기록합니다.
정렬 알고리즘
가장 먼저 떠오르는 답은 퀵 정렬일 것입니다. 정렬 알고리즘을 체계적으로 배운 사람이라면 퀵 정렬이 매우 빠른 정렬 방법이라는 것을 알고 있습니다. 먼저 데이터를 정렬한 다음, 그중에서 앞의 1000개를 뽑아내는 방식입니다. 하지만 면접에서 그렇게만 답변한다면, 이후 면접은 기대하기 어려울 것입니다. 이 방법은 입력 데이터의 규모가 작을 때는 편리한 방법이지만, 데이터 규모가 커지면(문제의 1억 개) 실행에 필요한 메모리 요구량도 증가합니다. 퀵 정렬의 시간 복잡도는 O(n log n)이며, 1억 개의 정수를 동시에 정렬하려면 메모리에 읽어들여야 합니다. 각 int 타입이 4바이트를 차지한다고 가정하면, 1억 개의 정수는 400MB의 메모리가 필요합니다. 현대 컴퓨터의 사용 가능한 메모리가 400MB보다 훨씬 크지만, 데이터 규모가 10억 또는 100억으로 다시 확대되면 메모리 요구량은 4GB와 40GB로 증가하여 알고리즘의 가용성(availability)과 확장성(scalability)에 심각한 영향을 미칩니다. 또한, 이러한 상황에서 전체 정렬을 수행해야 한다면 외부 정렬, 비트맵 정렬, 기수 정렬, 버킷 정렬 등의 알고리즘을 사용하여 메모리 부족 문제를 해결해야 합니다. 동시에 문제에서는 상위 1000개의 데이터만 요구하므로, 모든 요소를 정렬하는 것은 분명히 불필요합니다.
간단한 데모 프로그램을 작성해보았습니다. 코드는 다음과 같습니다:
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
#define MAX INT32_MAX
#define MIN INT32_MIN
#define SIZE 100000000 // 100 million
#define K 1000
int main() {
auto start = chrono::high_resolution_clock::now();
// Create a random number generator
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(MIN, MAX);
// Create an array of random numbers
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
arr[i] = dis(gen);
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end - start;
cout << "Time taken to create array: " << diff.count() << " s" << endl;
start = chrono::high_resolution_clock::now();
// sorting via std::sort() - optimized quicksort
sort(arr, arr + SIZE);
end = chrono::high_resolution_clock::now();
diff = end - start;
// the arr[0]~arr[k-1] is the top k elements in arr.
cout << "Time taken to get top K elements: " << diff.count() << " s" << endl;
free(arr);
return 0;
}
# CPU: i7-8700k
# Memory: 16 GB
# OS: Ubuntu 22.10 Kinetic
Time taken to create array: 2.13481 s
Time taken to get top K elements: 22.3849 s
부분 제거법
위 알고리즘의 불필요한 정렬을 피하기 위해, 정렬할 배열에서 처음 k (= 1000)개의 요소를 선택하여 최소 힙을 구축할 수 있습니다. 그런 다음 k + 1부터 시작하여 컨테이너의 최소 요소 m과 비교하여, m보다 크면 m을 교체하고 최소 힙을 재조정합니다.
알고리즘은 다음과 같습니다:
- 처음 K개의 요소를 선택하여 최소 힙을 구축합니다.
- K+1번째 요소부터 시작하여 힙의 최상단 요소와 비교합니다. 힙 최상단 요소보다 크면 힙 최상단 요소를 교체하고 힙을 조정합니다.
- 배열을 모두 순회할 때까지 2단계를 반복합니다.
- 힙에 있는 요소가 가장 큰 K개의 요소입니다.
코드는 다음과 같습니다:
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
#define MAX INT32_MAX
#define MIN INT32_MIN
#define SIZE 100000000 // 100 million
#define K 1000
int main() {
// Create a random number generator
auto start = chrono::high_resolution_clock::now();
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(MIN, MAX);
// Create an array of random numbers
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
arr[i] = dis(gen);
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end - start;
cout << "Time taken to create array: " << diff.count() << " s" << endl;
// clock start
start = chrono::high_resolution_clock::now();
// generate a min-heap with first k elements
int *heap = new int[K];
for (int i = 0; i < K; i++) {
heap[i] = arr[i];
}
make_heap(heap, heap + K, greater<>());
for (int i = K; i < SIZE; i++) {
if (arr[i] > heap[0]) {
pop_heap(heap, heap + K, greater<>());
heap[K - 1] = arr[i];
push_heap(heap, heap + K, greater<>());
}
}
// clock end
end = chrono::high_resolution_clock::now();
diff = end - start;
cout << "Time taken to get top K elements: " << diff.count() << " s" << endl;
free(arr);
free(heap);
return 0;
}
Time taken to create array: 2.18854 s
Time taken to get top K elements: 0.178133 s
C++ STL set
표준 라이브러리의 set은 내부적으로 레드-블랙 트리(균형 이진 탐색 트리)로 구현되어 있습니다. 여기서 set 컨테이너를 사용하여 상위 k개의 요소를 얻을 수 있을지 생각해보았습니다. 중복 요소를 허용한다면 set 대신 multiset을 사용합니다.
코드는 다음과 같습니다:
#include <iostream>
#include <random>
#include <chrono>
#include <set>
using namespace std;
#define MAX INT32_MAX
#define MIN INT32_MIN
#define SIZE 100000000 // 100 million
#define K 1000
int main() {
// Create a random number generator
auto start = chrono::high_resolution_clock::now();
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(MIN, MAX);
// Create an array of random numbers
int *arr = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
arr[i] = dis(gen);
}
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end - start;
cout << "Time taken to create array: " << diff.count() << " s" << endl;
// clock start
start = chrono::high_resolution_clock::now();
// Create a set of K the largest numbers
set<int> s;
for (int i = 0; i < SIZE; i++) {
if (s.size() < K) {
s.insert(arr[i]);
} else {
if (arr[i] > *s.begin()) {
s.erase(s.begin());
s.insert(arr[i]);
}
}
}
// clock end
end = chrono::high_resolution_clock::now();
diff = end - start;
cout << "Time taken to get top K elements: " << diff.count() << " s" << endl;
// Print the set in reverse order
// for (auto it = s.rbegin(); it != s.rend(); it++) {
// cout << *it << endl;
// }
free(arr);
return 0;
}
Time taken to create array: 2.16181 s
Time taken to get top K elements: 1.68677 s
결론
위 실험을 통해 부분 제거 아이디어와 최소 힙 자료구조를 사용하여 상위 k개의 요소를 얻는 방법이 가장 효율적이며, 그다음은 set 컨테이너를 사용하는 방법, 마지막으로 정렬 알고리즘을 사용하는 방법임을 알 수 있습니다.