#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> #include…
- User
#include #include #include #include #include #include <sys/time.h> #include <omp.h>
using namespace std;
void merge(vector &arr, int low, int mid, int high) { int n1 = mid - low + 1; int n2 = high - mid; vector L(n1), R(n2);
for (int i = 0; i < n1; i++) L[i] = arr[low + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = low; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; }}
void parallelMergeSort(vector &arr, int low, int high) { int mid; if (low < high) { mid = low + (high - low) / 2; #pragma omp parallel sections { #pragma omp section parallelMergeSort(arr, low, mid); #pragma omp section parallelMergeSort(arr, mid + 1, high); } merge(arr, low, mid, high); } }
void parallelQuickSort(vector &arr, int left, int right) { if (left < right) { int pivot = arr[left + (right - left) / 2]; int i = left, j = right; while (i <= j) { while(arr[i] < pivot) i++; while(arr[j] > pivot) j--; if(i <= j) { swap(arr[i], arr[j]); i++; j--; } } #pragma omp parallel sections { #pragma omp section { parallelQuickSort(arr, left, j); } #pragma omp section { parallelQuickSort(arr, i, right); } } } }
void parallelCountingSort(vector &arr, int maxValue) { vector count(maxValue + 1, 0); vector output(arr.size());
#pragma omp parallel for for (auto num : arr) { #pragma omp atomic count[num]++; } for (int i = 1; i <= maxValue; ++i) { count[i] += count[i - 1]; } for (int i = (int)arr.size() - 1; i >= 0; --i) { output[count[arr[i]] - 1] = arr[i]; #pragma omp atomic count[arr[i]]--; } arr = move(output);}
void runParallelSort(void (*sortFunc)(vector &, int, int), vector &data, const vector &thread_counts) { double totalTime, avgTime; vector temp; for (int numThreads : thread_counts) { totalTime = 0.0; for (int i = 0; i < 5; ++i) { // 5 runs temp = data; // Copy the original data totalTime += measureTime(sortFunc, temp, numThreads); } avgTime = totalTime / 5; cout << "Threads: " << numThreads << ", Avg Time: " << avgTime << " seconds." << endl; } }
void runParallelCountingSort(vector &data, const vector &thread_counts, int maxValue) { double totalTime, avgTime; vector temp; for (int numThreads : thread_counts) { totalTime = 0.0; for (int i = 0; i < 5; ++i) { temp = data; totalTime += measureTime([maxValue](vector &a, int, int) { parallelCountingSort(a, maxValue); }, temp, numThreads); } avgTime = totalTime / 5; cout << "Threads: " << numThreads << ", Avg Time: " << avgTime << " seconds." << endl; } }
double measureTime(std::function<void(vector &, int, int)> sortFunc, vector &data, int numThreads) { omp_set_num_threads(numThreads); struct timeval start, end; gettimeofday(&start, NULL); sortFunc(data, 0, data.size() - 1); gettimeofday(&end, NULL); double elapsed = (end.tv_sec - start.tv_sec) + ((end.tv_usec - start.tv_usec) / 1000000.0); return elapsed; }
double measureTime(void (*sortFunc)(vector &, int, int), vector &data, int numThreads) { omp_set_num_threads(numThreads); struct timeval start, end; gettimeofday(&start, NULL); sortFunc(data, 0, data.size() - 1); gettimeofday(&end, NULL); double elapsed = (end.tv_sec - start.tv_sec) + ((end.tv_usec - start.tv_usec) / 1000000.0); return elapsed; } int main() { int choice; const int MAX_VALUE = 1000; // Range: 0 to 1000
int N=1_000_000_000; cout << "Choose sorting algorithm:" << endl; cout << "1 - Parallel Merge Sort" << endl; cout << "2 - Parallel Quick Sort" << endl; cout << "3 - Parallel Counting Sort" << endl; cout << "Selection: "; cin >> choice; vector<int> data(N), temp; srand(static_cast<unsigned>(time(0))); generate(data.begin(), data.end(), [&] { return rand() % (MAX_VALUE + 1); }); vector<int> thread_counts = {1, 2, 4, 6, 8, 10, 12, 14, 16}; double totalTime, avgTime; switch (choice) { case 1: cout << "Running Parallel Merge Sort:" << endl; runParallelSort(parallelMergeSort, data, thread_counts); break; case 2: cout << "Running Parallel Quick Sort:" << endl; runParallelSort(parallelQuickSort, data, thread_counts); break; case 3: cout << "Running Parallel Counting Sort (for MAX_VALUE = " << MAX_VALUE << "):" << endl; runParallelCountingSort(data, thread_counts, MAX_VALUE); break; default: cerr << "Invalid choice." << endl; return 1; } return 0;}
correct this code
- Assistant
Your code looks mostly fine, but there are a few issues and considerations to keep in mind. I'll provide corrections as well as potential optimizations and best practices for parallel programming using OpenMP.
-
Considering the size of
N = 1_000_000_000, thevector<int> data(N)statement will try to allocate a significant amount of memory. Ensure that your computer has enough memory to handle this or reduceNaccordingly. -
Use of
rand()is not thread-safe. For large data sizes, consider usingmt19937withuniform_int_distributionfrom<random>for better randomness and thread-safety. -
Ensure OpenMP is enabled in your compilation. Using the appropriate compiler flag (e.g.,
-fopenmpwith GCC or Clang). -
#pragma omp parallel sectionscreates a limited amount of parallelism and isn't the best choice for recursive algorithms due to potential imbalances. Consider using#pragma omp taskfor the recursive calls instead. -
Validate your sorting algorithm with a smaller dataset to check if it's sorting correctly before running it on large datasets.
-
measureTimefunction withstd::function<void(vector<int>&, int, int)>is unnecessary since you already have an overload with the function pointer. Instead, you can use template function formeasureTimeto support any callable type. -
For
parallelCountingSort, be sure to handle negative numbers or adjust the algorithm as needed.
Here's a revised version of your code:
#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> #include <ctime> #include <sys/time.h> #include <omp.h> #include <random> #include <functional> using namespace std; // ... [Keep all the sorting function definitions as you have them] ... // Template measureTime function that can handle any callable type template <typename SortFunction> double measureTime(SortFunction sortFunc, vector<int> &data, int numThreads) { omp_set_num_threads(numThreads); struct timeval start, end; gettimeofday(&start, NULL); sortFunc(data); gettimeofday(&end, NULL); double elapsed = (end.tv_sec - start.tv_sec) + ((end.tv_usec - start.tv_usec) / 1000000.0); return elapsed; } int main() { // ... [No changes in the beginning of main] ... Generate random data with thread-safe random number generation std::mt19937 rnd(static_cast<unsigned>(time(0))); std::uniform_int_distribution<int> dist(0, MAX_VALUE); generate(data.begin(), data.end(), [&]() { return dist(rnd); }); // ... [Remainder of main function as you have it] ... switch (choice) { case 1: cout << "Running Parallel Merge Sort:" << endl; runParallelSort([&](vector<int> &vec) { parallelMergeSort(vec, 0, vec.size() - 1); }, data, thread_counts); break; // ... [Handle other cases similarly] ... } return 0; }Take extra caution with parallel algorithms, especially for very large
N, and ensure that you test and validate the functionality on a smaller scale before scaling up. Also, be aware that parallelism introduces overhead and may not always lead to speedup, particularly for small problem sizes or when not properly optimized. -
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.