libMesh::Parallel::BinSorter< KeyType, IdxType > Class Template Reference

#include <parallel_bin_sorter.h>

List of all members.

Public Member Functions
	BinSorter (const std::vector< KeyType > &d)
void	binsort (const IdxType nbins, KeyType max, KeyType min)
IdxType	sizeof_bin (const IdxType 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, typename IdxType = unsigned int>
class libMesh::Parallel::BinSorter< KeyType, IdxType >

Perform a parallel sort using a bin-sort method.

Definition at line 42 of file parallel_bin_sorter.h.

---

Member Typedef Documentation

template<typename KeyType, typename IdxType = unsigned int>

typedef std::vector<KeyType>::const_iterator libMesh::Parallel::BinSorter< KeyType, IdxType >::IterType [private]

Definition at line 45 of file parallel_bin_sorter.h.

---

Constructor & Destructor Documentation

template<typename KeyType , typename IdxType >

libMesh::Parallel::BinSorter< KeyType, IdxType >::BinSorter

(

const std::vector< KeyType > &

d

)

[inline, explicit]

Definition at line 40 of file parallel_bin_sorter.C.

References libMesh::Parallel::BinSorter< KeyType, IdxType >::data, and libMesh::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 , typename IdxType >

void libMesh::Parallel::BinSorter< KeyType, IdxType >::binsort	(	const IdxType	nbins,
		KeyType	max,
		KeyType	min
	)			[inline]

Definition at line 55 of file parallel_bin_sorter.C.

References libMesh::Parallel::BinSorter< KeyType, IdxType >::bin_iters, libMesh::Parallel::Histogram< KeyType, IdxType >::build_histogram(), libMesh::CommWorld, libMesh::Parallel::BinSorter< KeyType, IdxType >::data, libMesh::Parallel::Histogram< KeyType, IdxType >::get_histogram(), libMesh::Parallel::Histogram< KeyType, IdxType >::make_histogram(), libMesh::Parallel::Histogram< KeyType, IdxType >::n_bins(), libMesh::Parallel::Communicator::sum(), libMesh::Parallel::Utils::to_double(), and libMesh::Parallel::Histogram< KeyType, IdxType >::upper_bound().

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

{
  libmesh_assert_less (min, max);

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

  const std::vector<IdxType>& 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
    IdxType local_data_size = libmesh_cast_int<IdxType>(data.size());
    IdxType global_data_size = libmesh_cast_int<IdxType>(local_data_size);

    CommWorld.sum(global_data_size);

    std::vector<IdxType> target_bin_size (nbins, global_data_size / nbins);

    // Equally distribute the remainder
    for (IdxType 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
      IdxType 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 (IdxType 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 , typename IdxType >

IdxType libMesh::Parallel::BinSorter< KeyType, IdxType >::sizeof_bin

(

const IdxType

bin

)

const [inline]

Definition at line 76 of file parallel_bin_sorter.h.

References libMesh::Parallel::BinSorter< KeyType, IdxType >::bin_iters.

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

{
  libmesh_assert_less ((bin+1), bin_iters.size());

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

---

Member Data Documentation

template<typename KeyType, typename IdxType = unsigned int>

std::vector<IterType> libMesh::Parallel::BinSorter< KeyType, IdxType >::bin_iters [private]

Definition at line 67 of file parallel_bin_sorter.h.

Referenced by libMesh::Parallel::BinSorter< KeyType, IdxType >::binsort(), and libMesh::Parallel::BinSorter< KeyType, IdxType >::sizeof_bin().

template<typename KeyType, typename IdxType = unsigned int>

const std::vector<KeyType>& libMesh::Parallel::BinSorter< KeyType, IdxType >::data [private]

Definition at line 66 of file parallel_bin_sorter.h.

Referenced by libMesh::Parallel::BinSorter< KeyType, IdxType >::binsort(), and libMesh::Parallel::BinSorter< KeyType, IdxType >::BinSorter().

---

The documentation for this class was generated from the following files:

• parallel_bin_sorter.h
• parallel_bin_sorter.C