quicksort.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 2, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/quicksort.h
00032  *  @brief Implementation of a unbalanced parallel quicksort (in-place).
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
00039 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
00040 
00041 #include <parallel/parallel.h>
00042 #include <parallel/partition.h>
00043 
00044 namespace __gnu_parallel
00045 {
00046   /** @brief Unbalanced quicksort divide step.
00047    *  @param begin Begin iterator of subsequence.
00048    *  @param end End iterator of subsequence.
00049    *  @param comp Comparator.
00050    *  @param pivot_rank Desired rank of the pivot.
00051    *  @param num_samples Choose pivot from that many samples.
00052    *  @param num_threads Number of threads that are allowed to work on
00053    *  this part.
00054    */
00055   template<typename RandomAccessIterator, typename Comparator>
00056     typename std::iterator_traits<RandomAccessIterator>::difference_type
00057     parallel_sort_qs_divide(RandomAccessIterator begin,
00058                 RandomAccessIterator end,
00059                 Comparator comp, typename std::iterator_traits
00060                 <RandomAccessIterator>::difference_type pivot_rank,
00061                 typename std::iterator_traits
00062                 <RandomAccessIterator>::difference_type
00063                 num_samples, thread_index_t num_threads)
00064     {
00065       typedef std::iterator_traits<RandomAccessIterator> traits_type;
00066       typedef typename traits_type::value_type value_type;
00067       typedef typename traits_type::difference_type difference_type;
00068 
00069       difference_type n = end - begin;
00070       num_samples = std::min(num_samples, n);
00071 
00072       // Allocate uninitialized, to avoid default constructor.
00073       value_type* samples =
00074     static_cast<value_type*>(::operator new(num_samples
00075                         * sizeof(value_type)));
00076 
00077       for (difference_type s = 0; s < num_samples; ++s)
00078     {
00079       const unsigned long long index = static_cast<unsigned long long>(s)
00080         * n / num_samples;
00081       ::new(&(samples[s])) value_type(begin[index]);
00082     }
00083 
00084       __gnu_sequential::sort(samples, samples + num_samples, comp);
00085 
00086       value_type& pivot = samples[pivot_rank * num_samples / n];
00087 
00088       __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
00089         pred(comp, pivot);
00090       difference_type split = parallel_partition(begin, end, pred, num_threads);
00091 
00092       ::operator delete(samples);
00093 
00094       return split;
00095     }
00096 
00097   /** @brief Unbalanced quicksort conquer step.
00098    *  @param begin Begin iterator of subsequence.
00099    *  @param end End iterator of subsequence.
00100    *  @param comp Comparator.
00101    *  @param num_threads Number of threads that are allowed to work on
00102    *  this part.
00103    */
00104   template<typename RandomAccessIterator, typename Comparator>
00105     void
00106     parallel_sort_qs_conquer(RandomAccessIterator begin,
00107                  RandomAccessIterator end,
00108                  Comparator comp,
00109                  thread_index_t num_threads)
00110     {
00111       typedef std::iterator_traits<RandomAccessIterator> traits_type;
00112       typedef typename traits_type::value_type value_type;
00113       typedef typename traits_type::difference_type difference_type;
00114 
00115       if (num_threads <= 1)
00116     {
00117       __gnu_sequential::sort(begin, end, comp);
00118       return;
00119     }
00120 
00121       difference_type n = end - begin, pivot_rank;
00122 
00123       if (n <= 1)
00124     return;
00125 
00126       thread_index_t num_threads_left;
00127 
00128       if ((num_threads % 2) == 1)
00129     num_threads_left = num_threads / 2 + 1;
00130       else
00131     num_threads_left = num_threads / 2;
00132 
00133       pivot_rank = n * num_threads_left / num_threads;
00134 
00135       difference_type split =
00136     parallel_sort_qs_divide(begin, end, comp, pivot_rank,
00137                 _Settings::get().sort_qs_num_samples_preset,
00138                 num_threads);
00139 
00140 #pragma omp parallel sections num_threads(2)
00141       {
00142 #pragma omp section
00143     parallel_sort_qs_conquer(begin, begin + split,
00144                  comp, num_threads_left);
00145 #pragma omp section
00146     parallel_sort_qs_conquer(begin + split, end,
00147                  comp, num_threads - num_threads_left);
00148       }
00149     }
00150 
00151 
00152 
00153   /** @brief Unbalanced quicksort main call.
00154    *  @param begin Begin iterator of input sequence.
00155    *  @param end End iterator input sequence, ignored.
00156    *  @param comp Comparator.
00157    *  @param n Length of input sequence.
00158    *  @param num_threads Number of threads that are allowed to work on
00159    *  this part.
00160    */
00161   template<typename RandomAccessIterator, typename Comparator>
00162     void
00163     parallel_sort_qs(RandomAccessIterator begin,
00164              RandomAccessIterator end,
00165              Comparator comp, typename std::iterator_traits
00166              <RandomAccessIterator>::difference_type n,
00167              int num_threads)
00168     {
00169       _GLIBCXX_CALL(n)
00170 
00171       typedef std::iterator_traits<RandomAccessIterator> traits_type;
00172       typedef typename traits_type::value_type value_type;
00173       typedef typename traits_type::difference_type difference_type;
00174 
00175       if (n == 0)
00176     return;
00177 
00178       // At least one element per processor.
00179       if (num_threads > n)
00180     num_threads = static_cast<thread_index_t>(n);
00181 
00182       parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
00183     }
00184 
00185 } //namespace __gnu_parallel
00186 
00187 #endif

Generated on Fri Jan 23 20:12:16 2009 for libstdc++ by  doxygen 1.5.6