libMesh
parallel_bin_sorter.C
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2017 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8 
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13 
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 
18 
19 // C++ includes
20 #include <algorithm> // std::lower_bound
21 
22 // Local includes
23 #include "libmesh/libmesh_common.h"
24 #include "libmesh/parallel.h"
25 #include "libmesh/parallel_bin_sorter.h"
26 #include "libmesh/parallel_hilbert.h"
27 #include "libmesh/parallel_histogram.h"
28 #include "libmesh/parallel_conversion_utils.h"
29 
30 namespace libMesh
31 {
32 
33 
34 
35 namespace Parallel {
36 
37 template <typename KeyType, typename IdxType>
39  const std::vector<KeyType> & d) :
40  ParallelObject(comm_in),
41  data(d)
42 {
43  // Assume (& libmesh_assert) we are working with a sorted range
44 
45  // Ah... is_sorted is an STL extension!
46  //libmesh_assert (std::is_sorted (data.begin(), data.end()));
47 
48  // Home-grown is_sorted
50 }
51 
52 
53 
54 template <typename KeyType, typename IdxType>
55 void BinSorter<KeyType,IdxType>::binsort (const IdxType nbins,
56  KeyType max,
57  KeyType min)
58 {
59  libmesh_assert_less (min, max);
60 
61  // Build a histogram in parallel from our data.
62  // Use this to create quasi-uniform bins.
64  phist.make_histogram (nbins*50, max, min);
65  phist.build_histogram ();
66 
67  const std::vector<IdxType> & histogram =
68  phist.get_histogram();
69 
70 
71  // Now we will locate the bin boundaries so
72  // that each bin is roughly equal size
73  {
74  // Find the total size of the data set
75  IdxType local_data_size = cast_int<IdxType>(data.size());
76  IdxType global_data_size = cast_int<IdxType>(local_data_size);
77 
78  this->comm().sum(global_data_size);
79 
80  std::vector<IdxType> target_bin_size (nbins, global_data_size / nbins);
81 
82  // Equally distribute the remainder
83  for (IdxType i=0; i<(global_data_size % nbins); i++)
84  ++target_bin_size[i];
85 
86  // Set the iterators corresponding to the bin boundaries
87  {
88  std::vector<double> bin_bounds (nbins+1);
89  bin_iters.resize (nbins+1, data.begin());
90 
91  // Set the minimum bin boundary iterator
92  bin_iters[0] = data.begin();
93  bin_bounds[0] = Parallel::Utils::to_double(min);
94 
95  // The current location in the histogram
96  IdxType current_histogram_bin = 0;
97 
98  // How much above (+) or below (-) we are from the
99  // target size for the last bin.
100  // Note that when delta is (-) we will
101  // accept a slightly larger size for the next bin,
102  // the goal being to keep the whole mess average
103  int delta = 0;
104 
105  // Set the internal bin boundary iterators
106  for (IdxType b=0; b<nbins; ++b)
107  {
108  // The size of bin b. We want this to
109  // be ~= target_bin_size[b]
110  int current_bin_size = 0;
111 
112  // Step through the histogram until we have the
113  // desired bin size
114  while ((current_bin_size + histogram[current_histogram_bin] + delta) <= target_bin_size[b])
115  {
116  // Don't index out of the histogram!
117  if ((current_histogram_bin+1) == phist.n_bins())
118  break;
119 
120  current_bin_size += histogram[current_histogram_bin++];
121  }
122 
123  delta += current_bin_size - target_bin_size[b];
124 
125  // Set the upper bound of the bin
126  bin_bounds[b+1] = phist.upper_bound (current_histogram_bin);
127  bin_iters[b+1] =
128  std::lower_bound(bin_iters[b], data.end(),
130  }
131 
132  // Just be sure the last boundary points to the right place
133  bin_iters[nbins] = data.end();
134  // This gets destructed here anyway
135  // bin_bounds[nbins] = Parallel::Utils::to_double(max);
136  }
137  }
138 }
139 
140 }
141 
142 
143 // Explicitly instantiate for int, double
146 #ifdef LIBMESH_HAVE_LIBHILBERT
148 #endif
149 
150 } // namespace libMesh
IdxType n_bins() const
The number of bins in the histogram.
std::vector< IterType > bin_iters
Encapsulates the MPI_Comm object.
Definition: parallel.h:657
BinSorter(const Parallel::Communicator &comm, const std::vector< KeyType > &d)
const std::vector< KeyType > & data
double upper_bound(const IdxType bin) const
The libMesh namespace provides an interface to certain functionality in the library.
void build_histogram()
Build the histogram across all processors and store the result in the input vector hist...
libmesh_assert(j)
bool is_sorted(const std::vector< KeyType > &v)
void make_histogram(const IdxType nbins, KeyType max, KeyType min)
The actual function which sorts the data into nbins.
Perform a parallel sort using a bin-sort method.
This class forms the base class for all other classes that are expected to be implemented in parallel...
const std::vector< IdxType > & get_histogram() const
static KeyType to_key_type(const double f)
const Parallel::Communicator & comm() const
void max(T &r, const Communicator &comm=Communicator_World)
IterBase * data
Ideally this private member data should have protected access.
Defines a histogram to be used in parallel in conjunction with a BinSorter.
void sum(T &r) const
Take a local variable and replace it with the sum of it&#39;s values on all processors.
void min(T &r, const Communicator &comm=Communicator_World)
double to_double(const KeyType &k)
A utility function which converts whatever KeyType is to a double for the histogram bounds...
void binsort(const IdxType nbins, KeyType max, KeyType min)
The actual function which sorts the data into nbins.