Background
During an interview last month, the interviewer asked me this question, and I couldn't answer it well at the time. Later, I thought about it seriously and decided to document it in this article.
Sorting Algorithm
The first intuitive answer would be "quick sort." After systematically learning sorting algorithms, we all know that quicksort is a very fast sorting method. We first sort the data, then extract the top 1000 numbers. However, if you only give that answer in an interview, you'll likely not proceed to the next rounds. This approach is convenient when the input data size is small, but as the data scale grows (100 million in this problem), the memory requirements for execution also increase. In quicksort, the time complexity is O(n log n). To sort 100 million integers simultaneously, they need to be loaded into memory. Assuming each int type occupies 4 bytes, 100 million integers would require 400MB of memory. Although modern computers have far more than 400MB of available memory, when the data scale expands to 10 billion or even 100 billion, the memory requirement rises to 4GB and 40GB, severely impacting the algorithm's availability and scalability. Moreover, in such cases, performing a full sort would require resorting to algorithms like external sort, bitmap sort, radix sort, or bucket sort to address memory limitations. Additionally, the problem only asks for the top 1000 data points; sorting all elements is clearly unnecessary.
I wrote a simple demo program with the following code:
#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
Elimination Method
To avoid the unnecessary sorting in the above algorithm, we can select the first k (= 1000) elements from the array to be sorted and build a min-heap. Then, starting from the k+1 element, compare it with the smallest element m in the container. If it is greater than m, replace m and adjust the min-heap.
The algorithm is as follows:
- Select the first K elements and build a min-heap.
- Starting from the K+1 element, compare it with the top element of the heap. If it is larger than the top element, replace the top element and adjust the heap.
- Repeat step 2 until the array is fully traversed.
- The elements in the heap are the top K largest elements.
The code is as follows:
#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
As we know, the underlying implementation of set in the standard library is a red-black tree (a balanced binary search tree). I wondered if we could use the set container to get the top k elements. If duplicate elements are allowed, use multiset instead of set.
The code is as follows:
#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
Summary
From the experiments above, we can see that using the elimination method with a min-heap data structure to get the top k elements is the most efficient, followed by using the set container, and finally using a sorting algorithm.
Reference
Finding the Top 100 Numbers from 100 Million Numbers (Top K Problem) - CSDN