quicksort.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
00033 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
00034
00035 #include <parallel/parallel.h>
00036 #include <parallel/partition.h>
00037
00038 namespace __gnu_parallel
00039 {
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 template<typename RandomAccessIterator, typename Comparator>
00050 typename std::iterator_traits<RandomAccessIterator>::difference_type
00051 parallel_sort_qs_divide(RandomAccessIterator begin,
00052 RandomAccessIterator end,
00053 Comparator comp, typename std::iterator_traits
00054 <RandomAccessIterator>::difference_type pivot_rank,
00055 typename std::iterator_traits
00056 <RandomAccessIterator>::difference_type
00057 num_samples, thread_index_t num_threads)
00058 {
00059 typedef std::iterator_traits<RandomAccessIterator> traits_type;
00060 typedef typename traits_type::value_type value_type;
00061 typedef typename traits_type::difference_type difference_type;
00062
00063 difference_type n = end - begin;
00064 num_samples = std::min(num_samples, n);
00065
00066
00067 value_type* samples =
00068 static_cast<value_type*>(::operator new(num_samples
00069 * sizeof(value_type)));
00070
00071 for (difference_type s = 0; s < num_samples; ++s)
00072 {
00073 const unsigned long long index = static_cast<unsigned long long>(s)
00074 * n / num_samples;
00075 ::new(&(samples[s])) value_type(begin[index]);
00076 }
00077
00078 __gnu_sequential::sort(samples, samples + num_samples, comp);
00079
00080 value_type& pivot = samples[pivot_rank * num_samples / n];
00081
00082 __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
00083 pred(comp, pivot);
00084 difference_type split =
00085 parallel_partition(begin, end, pred, num_threads);
00086
00087 ::operator delete(samples);
00088
00089 return split;
00090 }
00091
00092
00093
00094
00095
00096
00097
00098
00099 template<typename RandomAccessIterator, typename Comparator>
00100 void
00101 parallel_sort_qs_conquer(RandomAccessIterator begin,
00102 RandomAccessIterator end,
00103 Comparator comp,
00104 thread_index_t num_threads)
00105 {
00106 typedef std::iterator_traits<RandomAccessIterator> traits_type;
00107 typedef typename traits_type::value_type value_type;
00108 typedef typename traits_type::difference_type difference_type;
00109
00110 if (num_threads <= 1)
00111 {
00112 __gnu_sequential::sort(begin, end, comp);
00113 return;
00114 }
00115
00116 difference_type n = end - begin, pivot_rank;
00117
00118 if (n <= 1)
00119 return;
00120
00121 thread_index_t num_threads_left;
00122
00123 if ((num_threads % 2) == 1)
00124 num_threads_left = num_threads / 2 + 1;
00125 else
00126 num_threads_left = num_threads / 2;
00127
00128 pivot_rank = n * num_threads_left / num_threads;
00129
00130 difference_type split =
00131 parallel_sort_qs_divide(begin, end, comp, pivot_rank,
00132 _Settings::get().sort_qs_num_samples_preset,
00133 num_threads);
00134
00135 #pragma omp parallel sections num_threads(2)
00136 {
00137 #pragma omp section
00138 parallel_sort_qs_conquer(begin, begin + split,
00139 comp, num_threads_left);
00140 #pragma omp section
00141 parallel_sort_qs_conquer(begin + split, end,
00142 comp, num_threads - num_threads_left);
00143 }
00144 }
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155 template<typename RandomAccessIterator, typename Comparator>
00156 void
00157 parallel_sort_qs(RandomAccessIterator begin,
00158 RandomAccessIterator end,
00159 Comparator comp,
00160 thread_index_t num_threads)
00161 {
00162 _GLIBCXX_CALL(n)
00163
00164 typedef std::iterator_traits<RandomAccessIterator> traits_type;
00165 typedef typename traits_type::value_type value_type;
00166 typedef typename traits_type::difference_type difference_type;
00167
00168 difference_type n = end - begin;
00169
00170
00171 if (num_threads > n)
00172 num_threads = static_cast<thread_index_t>(n);
00173
00174 parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
00175 }
00176
00177 }
00178
00179 #endif