Parallel::BinSorter

Section: C Library Functions (3) Updated: Thu Apr 7 2011 Local index Up

NAME

Parallel::BinSorter -

SYNOPSIS

Public Member Functions

BinSorter (const std::vector< KeyType > &d)

void binsort (const unsigned int nbins, KeyType max, KeyType min)

unsigned int sizeof_bin (const unsigned int bin) const

Private Types

typedef std::vector< KeyType >::const_iterator IterType

Private Attributes

const std::vector< KeyType > & data

std::vector< IterType > bin_iters

Detailed Description

template<typename KeyType> class Parallel::BinSorter< KeyType >

Perform a parallel sort using a bin-sort method.

Definition at line 38 of file parallel_bin_sorter.h.

Member Typedef Documentation

template<typename KeyType> typedef std::vector<KeyType>::const_iterator Parallel::BinSorter< KeyType >::IterType [private]

Definition at line 41 of file parallel_bin_sorter.h.

Constructor & Destructor Documentation

template<typename KeyType > Parallel::BinSorter< KeyType >::BinSorter (const std::vector< KeyType > &d)

Definition at line 41 of file parallel_bin_sorter.C.

References Parallel::BinSorter< KeyType >::data, and Parallel::Utils::is_sorted().

                                                          :
  data(d)
{
  // Assume (& libmesh_assert) we are working with a sorted range

  // Ah...  is_sorted is an STL extension!
  //libmesh_assert (std::is_sorted (data.begin(), data.end()));

  // Home-grown is_sorted
  libmesh_assert (Parallel::Utils::is_sorted (data));
}

Member Function Documentation

template<typename KeyType > void Parallel::BinSorter< KeyType >::binsort (const unsigned intnbins, KeyTypemax, KeyTypemin)

Definition at line 56 of file parallel_bin_sorter.C.

References Parallel::Histogram< KeyType >::build_histogram(), Parallel::Histogram< KeyType >::get_histogram(), Parallel::Histogram< KeyType >::make_histogram(), Parallel::Histogram< KeyType >::n_bins(), Parallel::Utils::to_double(), and Parallel::Histogram< KeyType >::upper_bound().

Referenced by Parallel::Sort< KeyType >::binsort().

{
  libmesh_assert (min < max);
  
  // Build a histogram in parallel from our data.
  // Use this to create quasi-uniform bins.
  Parallel::Histogram<KeyType> phist (data);
  phist.make_histogram (nbins*50, max, min);
  phist.build_histogram ();

  const std::vector<unsigned int>& histogram =
    phist.get_histogram();


  // Now we will locate the bin boundaries so
  // that each bin is roughly equal size
  {
    // Find the total size of the data set
    unsigned int local_data_size = data.size();
    unsigned int global_data_size = local_data_size;

    Parallel::sum(global_data_size);
    
    std::vector<unsigned int> target_bin_size (nbins, global_data_size / nbins);
    
    // Equally distribute the remainder
    for (unsigned int i=0; i<(global_data_size % nbins); i++)
      ++target_bin_size[i];
    
    // Set the iterators corresponding to the bin boundaries
    {
      std::vector<double> bin_bounds (nbins+1);
      bin_iters.resize  (nbins+1, data.begin());
      
      // Set the minimum bin boundary iterator
      bin_iters[0]  = data.begin();
      bin_bounds[0] = Parallel::Utils::to_double(min);
      
      // The current location in the histogram
      unsigned int current_histogram_bin = 0;

      // How much above (+) or below (-) we are from the
      // target size for the last bin.
      // Note that when delta is (-) we will
      // accept a slightly larger size for the next bin,
      // the goal being to keep the whole mess average
      int delta = 0;
      
      // Set the internal bin boundary iterators
      for (unsigned int b=0; b<nbins; ++b)
        {
          // The size of bin b.  We want this to
          // be ~= target_bin_size[b]
          int current_bin_size = 0;
          
          // Step through the histogram until we have the
          // desired bin size     
          while ((current_bin_size + histogram[current_histogram_bin] + delta) <= target_bin_size[b])
            {
              // Don't index out of the histogram!
              if ((current_histogram_bin+1) == phist.n_bins())
                break;
              
              current_bin_size += histogram[current_histogram_bin++];
            }
          
          delta += current_bin_size - target_bin_size[b];
          
          // Set the upper bound of the bin
          bin_bounds[b+1] = phist.upper_bound (current_histogram_bin);    
          bin_iters[b+1]  = std::lower_bound(bin_iters[b], data.end(), 
                                             Parallel::Utils::to_key_type<KeyType>(bin_bounds[b+1]));
        }

      // Just be sure the last boundaries point to the right place
      bin_iters[nbins]  = data.end();
      bin_bounds[nbins] = Parallel::Utils::to_double(max);
    }
  }
}

template<typename KeyType > unsigned int Parallel::BinSorter< KeyType >::sizeof_bin (const unsigned intbin) const [inline]

Definition at line 71 of file parallel_bin_sorter.h.

Referenced by Parallel::Sort< KeyType >::binsort().

{
  libmesh_assert ((bin+1) < bin_iters.size());

  // The size of the bin is defined by the distance between
  // its bounding iterators
  return std::distance (bin_iters[bin], bin_iters[bin+1]);
}