parallel_bin_sorter.C
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2014 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"
26 #ifdef LIBMESH_HAVE_LIBHILBERT
27 # include "hilbert.h"
28 #endif
29 #include "libmesh/parallel.h"
31 
32 namespace libMesh
33 {
34 
35 
36 
37 namespace Parallel {
38 
39 template <typename KeyType, typename IdxType>
41  const std::vector<KeyType>& d) :
42  ParallelObject(comm_in),
43  data(d)
44 {
45  // Assume (& libmesh_assert) we are working with a sorted range
46 
47  // Ah... is_sorted is an STL extension!
48  //libmesh_assert (std::is_sorted (data.begin(), data.end()));
49 
50  // Home-grown is_sorted
52 }
53 
54 
55 
56 template <typename KeyType, typename IdxType>
57 void BinSorter<KeyType,IdxType>::binsort (const IdxType nbins,
58  KeyType max,
59  KeyType min)
60 {
61  libmesh_assert_less (min, max);
62 
63  // Build a histogram in parallel from our data.
64  // Use this to create quasi-uniform bins.
66  phist.make_histogram (nbins*50, max, min);
67  phist.build_histogram ();
68 
69  const std::vector<IdxType>& histogram =
70  phist.get_histogram();
71 
72 
73  // Now we will locate the bin boundaries so
74  // that each bin is roughly equal size
75  {
76  // Find the total size of the data set
77  IdxType local_data_size = libmesh_cast_int<IdxType>(data.size());
78  IdxType global_data_size = libmesh_cast_int<IdxType>(local_data_size);
79 
80  this->comm().sum(global_data_size);
81 
82  std::vector<IdxType> target_bin_size (nbins, global_data_size / nbins);
83 
84  // Equally distribute the remainder
85  for (IdxType i=0; i<(global_data_size % nbins); i++)
86  ++target_bin_size[i];
87 
88  // Set the iterators corresponding to the bin boundaries
89  {
90  std::vector<double> bin_bounds (nbins+1);
91  bin_iters.resize (nbins+1, data.begin());
92 
93  // Set the minimum bin boundary iterator
94  bin_iters[0] = data.begin();
95  bin_bounds[0] = Parallel::Utils::to_double(min);
96 
97  // The current location in the histogram
98  IdxType current_histogram_bin = 0;
99 
100  // How much above (+) or below (-) we are from the
101  // target size for the last bin.
102  // Note that when delta is (-) we will
103  // accept a slightly larger size for the next bin,
104  // the goal being to keep the whole mess average
105  int delta = 0;
106 
107  // Set the internal bin boundary iterators
108  for (IdxType b=0; b<nbins; ++b)
109  {
110  // The size of bin b. We want this to
111  // be ~= target_bin_size[b]
112  int current_bin_size = 0;
113 
114  // Step through the histogram until we have the
115  // desired bin size
116  while ((current_bin_size + histogram[current_histogram_bin] + delta) <= target_bin_size[b])
117  {
118  // Don't index out of the histogram!
119  if ((current_histogram_bin+1) == phist.n_bins())
120  break;
121 
122  current_bin_size += histogram[current_histogram_bin++];
123  }
124 
125  delta += current_bin_size - target_bin_size[b];
126 
127  // Set the upper bound of the bin
128  bin_bounds[b+1] = phist.upper_bound (current_histogram_bin);
129  bin_iters[b+1] = std::lower_bound(bin_iters[b], data.end(),
130  Parallel::Utils::to_key_type<KeyType>(bin_bounds[b+1]));
131  }
132 
133  // Just be sure the last boundaries point to the right place
134  bin_iters[nbins] = data.end();
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

Site Created By: libMesh Developers
Last modified: February 07 2014 16:57:06 UTC

Hosted By:
SourceForge.net Logo