# Untitled

a guest
Nov 28th, 2016
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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++) {
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.
75.     recursive_bisection(sorted_idx1, k1);
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. }