Created
November 1, 2023 15:37
-
-
Save hsuan1117/8d9d5cb055bd6bae98adbfe8a8384f82 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <ctime> | |
#include <random> | |
double findMedian(std::vector<double> &arr, int l, int r) { | |
std::sort(arr.begin() + l, arr.begin() + r + 1); | |
int n = r - l + 1; | |
return arr[l + n / 2]; | |
} | |
double SELECT(std::vector<double> &arr, int l, int r, int k, int groupSize) { | |
if (l == r) { | |
return arr[l]; | |
} | |
int n = r - l + 1; | |
int numMedians = (n + groupSize - 1) / groupSize; | |
std::vector<double> medians(numMedians); | |
for (int i = 0; i < numMedians; i++) { | |
int groupEnd = std::min(l + (i + 1) * groupSize - 1, r); | |
medians[i] = findMedian(arr, l + i * groupSize, groupEnd); | |
} | |
double pivot = SELECT(medians, 0, numMedians - 1, numMedians / 2, groupSize); | |
int partitionIndex = | |
std::partition(arr.begin() + l, arr.begin() + r + 1, [pivot](double num) { return num < pivot; }) - | |
arr.begin(); | |
if (k == partitionIndex) { | |
return arr[k]; | |
} else if (k < partitionIndex) { | |
return SELECT(arr, l, partitionIndex - 1, k, groupSize); | |
} else { | |
return SELECT(arr, partitionIndex + 1, r, k, groupSize); | |
} | |
} | |
double randomizedSelect(std::vector<double> &arr, int l, int r, int k) { | |
std::random_device rd; | |
std::mt19937 gen(rd()); | |
std::uniform_int_distribution<> dis(l, r); | |
int pivotIndex = dis(gen); | |
std::swap(arr[pivotIndex], arr[r]); | |
int i = l; | |
for (int j = l; j <= r - 1; j++) { | |
if (arr[j] <= arr[r]) { | |
std::swap(arr[i], arr[j]); | |
i++; | |
} | |
} | |
std::swap(arr[i], arr[r]); | |
if (k == i) | |
return arr[i]; | |
if (k < i) | |
return randomizedSelect(arr, l, i - 1, k); | |
return randomizedSelect(arr, i + 1, r, k); | |
} | |
int main() { | |
std::ios::sync_with_stdio(true); | |
std::random_device rd; | |
std::mt19937 g(rd()); | |
int N = 10000000; // 1e8 | |
std::vector<double> arr(N); | |
for (int i = 0; i < N; ++i) arr[i] = i; | |
std::shuffle(arr.begin(), arr.end(), g); | |
int k = N / 2; | |
std::cout << "|---------|----------|--------------------|" << '\n' | |
<< "| Group | Time | result |" << '\n' | |
<< "|---------|----------|--------------------|" << '\n'; | |
int test[4] = {3, 5, 7, 9}; | |
for (int _n = 0; _n < 4; _n++) { | |
double time = 0; | |
std::vector<double> copied = arr; | |
double result; | |
for (int i = 0; i < 50; i++) { | |
printf("| %d | %.2f | %02d/50 |\r", test[_n], (time / (double) i) / CLOCKS_PER_SEC, i); | |
fflush(stdout); | |
clock_t start = clock(); | |
result = SELECT(copied, 0, N - 1, k, test[_n]); | |
clock_t end = clock(); | |
time += (end - start); | |
} | |
printf("| %d | %.2f | %d |\n", test[_n], (time / 50.0) / CLOCKS_PER_SEC, (int) result); | |
} | |
for (int _n = 0; _n < 1; _n++) { | |
double time = 0; | |
std::vector<double> copied = arr; | |
double result; | |
for (int i = 0; i < 50; i++) { | |
printf("| random | %.2f | %02d/50 |\r", (time / (double) i) / CLOCKS_PER_SEC, i); | |
fflush(stdout); | |
clock_t start = clock(); | |
result = randomizedSelect(copied, 0, N - 1, k); | |
clock_t end = clock(); | |
time += (end - start); | |
} | |
printf("| random | %.2f | %d |\n", (time / 50.0) / CLOCKS_PER_SEC, (int) result); | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment