Line data    Source code

       1             : // The libMesh Finite Element Library.
       2             : // Copyright (C) 2002-2025 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>  // is_sorted, 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>
      38      697941 : BinSorter<KeyType,IdxType>::BinSorter (const Parallel::Communicator & comm_in,
      39             :                                        const std::vector<KeyType> & d) :
      40             :   ParallelObject(comm_in),
      41      697941 :   data(d)
      42             : {
      43       15230 :   libmesh_assert (std::is_sorted (data.begin(), data.end()));
      44      697941 : }
      45             : 
      46             : 
      47             : 
      48             : template <typename KeyType, typename IdxType>
      49      697941 : void BinSorter<KeyType,IdxType>::binsort (const IdxType nbins,
      50             :                                           KeyType max,
      51             :                                           KeyType min)
      52             : {
      53       15230 :   libmesh_assert_less (min, max);
      54             : 
      55             :   // Build a histogram in parallel from our data.
      56             :   // Use this to create quasi-uniform bins.
      57      728401 :   Parallel::Histogram<KeyType,IdxType> phist (this->comm(), data);
      58      697941 :   phist.make_histogram (nbins*50, max, min);
      59      697941 :   phist.build_histogram ();
      60             : 
      61       15230 :   const std::vector<IdxType> & histogram =
      62             :     phist.get_histogram();
      63             : 
      64             : 
      65             :   // Now we will locate the bin boundaries so
      66             :   // that each bin is roughly equal size
      67             :   {
      68             :     // Find the total size of the data set
      69      697941 :     IdxType local_data_size = cast_int<IdxType>(data.size());
      70      697941 :     IdxType global_data_size = cast_int<IdxType>(local_data_size);
      71             : 
      72      697941 :     this->comm().sum(global_data_size);
      73             : 
      74      713171 :     std::vector<IdxType> target_bin_size (nbins, global_data_size / nbins);
      75             : 
      76             :     // Equally distribute the remainder
      77     3395912 :     for (IdxType i=0; i<(global_data_size % nbins); i++)
      78     2699869 :       ++target_bin_size[i];
      79             : 
      80             :     // Set the iterators corresponding to the bin boundaries
      81             :     {
      82      697941 :       std::vector<double> bin_bounds (nbins+1);
      83      697941 :       bin_iters.resize  (nbins+1, data.begin());
      84             : 
      85             :       // Set the minimum bin boundary iterator
      86      697941 :       bin_iters[0]  = data.begin();
      87      697941 :       bin_bounds[0] = Parallel::Utils::to_double(min);
      88             : 
      89             :       // The current location in the histogram
      90       15230 :       IdxType current_histogram_bin = 0;
      91             : 
      92             :       // How much above (+) or below (-) we are from the
      93             :       // target size for the last bin.
      94             :       // Note that when delta is (-) we will
      95             :       // accept a slightly larger size for the next bin,
      96             :       // the goal being to keep the whole mess average
      97       15230 :       int delta = 0;
      98             : 
      99             :       // Set the internal bin boundary iterators
     100     7884912 :       for (IdxType b=0; b<nbins; ++b)
     101             :         {
     102             :           // The size of bin b.  We want this to
     103             :           // be ~= target_bin_size[b]
     104       30460 :           int current_bin_size = 0;
     105             : 
     106             :           // Step through the histogram until we have the
     107             :           // desired bin size
     108   368853120 :           while ((current_bin_size +
     109   367375810 :                   cast_int<int>(histogram[current_histogram_bin]) +
     110   368914040 :                   delta) <= cast_int<int>(target_bin_size[b]))
     111             :             {
     112             :               // Don't index out of the histogram!
     113   722754362 :               if ((current_histogram_bin+1) == phist.n_bins())
     114       15230 :                 break;
     115             : 
     116     3015540 :               current_bin_size += histogram[current_histogram_bin++];
     117             :             }
     118             : 
     119     7186971 :           delta += current_bin_size - static_cast<int>(target_bin_size[b]);
     120             : 
     121             :           // Set the upper bound of the bin
     122     7217431 :           bin_bounds[b+1] = phist.upper_bound (current_histogram_bin);
     123     7217427 :           bin_iters[b+1] =
     124     7186971 :             std::lower_bound(bin_iters[b], data.end(),
     125     7217427 :                              Parallel::Utils::Convert<KeyType>::to_key_type(bin_bounds[b+1]));
     126             :         }
     127             : 
     128             :       // Just be sure the last boundary points to the right place
     129      713171 :       bin_iters[nbins]  = data.end();
     130             :       // This gets destructed here anyway
     131             :       // bin_bounds[nbins] = Parallel::Utils::to_double(max);
     132             :     }
     133             :   }
     134      697941 : }
     135             : 
     136             : }
     137             : 
     138             : 
     139             : // Explicitly instantiate for int, double
     140             : template class LIBMESH_EXPORT Parallel::BinSorter<int, unsigned int>;
     141             : template class LIBMESH_EXPORT Parallel::BinSorter<double, unsigned int>;
     142             : #ifdef LIBMESH_HAVE_LIBHILBERT
     143             : template class LIBMESH_EXPORT Parallel::BinSorter<Parallel::DofObjectKey, unsigned int>;
     144             : #endif
     145             : 
     146             : } // namespace libMesh