Advertisement
Guest User

Untitled

a guest
Nov 28th, 2016
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <omp.h>
  7.  
  8. using namespace std;
  9.  
  10. #define N 500
  11. #define M 500
  12. #define STEP 0.01
  13.  
  14. #define N_DIMS 2
  15.  
  16. vector<vector<double> > points_matrix(N_DIMS, vector<double>(N * M));
  17. vector<vector<int> > graph_partition;
  18.  
  19. double find_span(vector<double> &x, vector<int> &idx)
  20. {
  21.     double max_value = x[idx[0]];
  22.     double min_value = x[idx[0]];
  23.    
  24.     #pragma omp parallel for
  25.     for (size_t i = 1; i < idx.size(); i++) {
  26.         max_value = (x[idx[i]] > max_value) ? x[idx[i]] : max_value;
  27.         min_value = (x[idx[i]] < min_value) ? x[idx[i]] : min_value;
  28.     }
  29.    
  30.     return max_value;
  31. }
  32.  
  33. vector<int> bisect(vector<int> idx)
  34. {
  35.     double max_span = 0;
  36.     size_t max_ind = 0;
  37.    
  38.     #pragma omp parallel for
  39.     for (size_t i = 0; i < points_matrix.size(); i++) {
  40.         //cout<<"Num threads"<<omp_get_num_threads()<<endl;
  41.         double cur_span = find_span(points_matrix[i], idx);
  42.         if (cur_span > max_span) {
  43.             max_span = cur_span;
  44.             max_ind = i;
  45.         }
  46.     }
  47.    
  48.     vector<int> sorted_idx = idx;
  49.  
  50.     sort(sorted_idx.begin(), sorted_idx.end(),
  51.             [&](const int& a, const int& b) {
  52.                 return points_matrix[max_ind][a] < points_matrix[max_ind][b];
  53.             }
  54.         );
  55.  
  56.     return sorted_idx;
  57. }
  58.  
  59. void recursive_bisection(vector<int> idx, int k)
  60. {
  61.     if (k < 2) {
  62.         graph_partition.push_back(idx);
  63.         return;
  64.     }
  65.    
  66.     int k1 = (k + 1) / 2;
  67.     int k2 = k - k1;
  68.  
  69.     vector<int> sorted_idx1 = bisect(idx);
  70.     vector<int> sorted_idx2(make_move_iterator(sorted_idx1.begin() + k1 * sorted_idx1.size() / k),
  71.                     make_move_iterator(sorted_idx1.end()));
  72.     sorted_idx1.erase(sorted_idx1.begin() + k1 * sorted_idx1.size() / k, sorted_idx1.end());
  73.    
  74.     #pragma omp task
  75.     recursive_bisection(sorted_idx1, k1);
  76.     #pragma omp task
  77.     recursive_bisection(sorted_idx2, k2);
  78. }
  79.  
  80. int main(int argc, char *argv[])
  81. {
  82.     for(size_t i = 0; i < N; ++i)
  83.         for(size_t j = 0; j < M; ++j) {
  84.             points_matrix[0][M * i + j] = i * STEP;
  85.             points_matrix[1][M * i + j] = j * STEP;
  86.         }
  87.  
  88.     vector<int> idx(M * N);
  89.     iota(idx.begin(), idx.end(), 0);
  90.  
  91.     double start = omp_get_wtime();
  92.     recursive_bisection(idx, atoi(argv[1]));
  93.     cout<<omp_get_wtime() - start;
  94.    
  95.     /*for(size_t i = 0; i < graph_partition.size(); ++i) {
  96.         for(size_t j = 0; j < graph_partition[i].size(); ++j)
  97.             cout << graph_partition[i][j] << " ";
  98.         cout << endl;
  99.     }*/
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement