Skip to content

Instantly share code, notes, and snippets.

@s417-lama

s417-lama/reduce.cpp

Last active August 22, 2023 12:10
Show Gist options
  • Save s417-lama/82575d235a3c34dc61a38a7fff372126 to your computer and use it in GitHub Desktop.
Save s417-lama/82575d235a3c34dc61a38a7fff372126 to your computer and use it in GitHub Desktop.
Download ZIP
C++ generic reduction using reducer and monoid (for more flexible parallel STL)
Raw
reduce.cpp
#include <iostream>
#include <algorithm>
#include <functional>
#include <limits>
#include <utility>
#include <vector>
#include <string>
#include <random>
#include <cassert>
template <typename ForwardIterator, typename Reducer>
inline typename Reducer::accumulator_type
reduce(ForwardIterator first,
ForwardIterator last,
Reducer reducer) {
auto reduce_impl = [&](ForwardIterator f, ForwardIterator l) {
auto acc = reducer.identity();
for (auto it = f; it != l; ++it) {
reducer(acc, *it);
}
return acc;
};
auto mid = first + (last - first) / 2;
// The following two functions can be computed in parallel
auto acc1 = reduce_impl(first, mid);
auto acc2 = reduce_impl(mid, last);
// Combine results
reducer(acc1, acc2);
return acc1;
}
template <typename T>
struct default_identity_provider {
static T value() {
return T{};
}
};
template <typename T, typename BinaryOp, typename IdentityProvider = default_identity_provider<T>>
struct monoid_reducer {
using value_type = T;
using accumulator_type = T;
void operator()(accumulator_type& t1, const value_type& t2) const {
t1 = bop_(t1, t2);
}
accumulator_type identity() const {
return IdentityProvider::value();
}
private:
static constexpr auto bop_ = BinaryOp();
};
template <typename T>
struct one {
static_assert(std::is_arithmetic_v<T>);
static constexpr T value() {
return T{1};
}
};
template <typename T>
struct lowest {
static_assert(std::is_arithmetic_v<T>);
static constexpr T value() {
return std::numeric_limits<T>::lowest();
}
};
template <typename T>
struct highest {
static_assert(std::is_arithmetic_v<T>);
static constexpr T value() {
return std::numeric_limits<T>::max();
}
};
template <typename T = void>
struct min_functor {
constexpr T operator()(const T& x, const T& y) const {
return std::min(x, y);
}
};
template <>
struct min_functor<void> {
template <typename T, typename U>
constexpr auto operator()(T&& v, U&& u) const {
return std::min(std::forward<T>(v), std::forward<U>(u));
}
};
template <typename T = void>
struct max_functor {
constexpr T operator()(const T& x, const T& y) const {
return std::max(x, y);
}
};
template <>
struct max_functor<void> {
template <typename T, typename U>
constexpr auto operator()(T&& t, U&& u) const {
return std::max(std::forward<T>(t), std::forward<U>(u));
}
};
template <typename T>
using plus_reducer = monoid_reducer<T, std::plus<>>;
template <typename T>
using multiplies_reducer = monoid_reducer<T, std::multiplies<>, one<T>>;
template <typename T>
using min_reducer = monoid_reducer<T, min_functor<>, highest<T>>;
template <typename T>
using max_reducer = monoid_reducer<T, max_functor<>, lowest<T>>;
template <typename T>
struct minmax_reducer {
using value_type = T;
using accumulator_type = std::pair<T, T>;
void operator()(accumulator_type& acc, const value_type& x) const {
acc.first = std::min(acc.first, x);
acc.second = std::max(acc.second, x);
}
void operator()(accumulator_type& acc1, const accumulator_type& acc2) const {
acc1.first = std::min(acc1.first, acc2.first);
acc1.second = std::max(acc1.second, acc2.second);
}
accumulator_type identity() const {
return std::make_pair(std::numeric_limits<T>::max(), std::numeric_limits<T>::lowest());
}
};
template <typename T, typename Counter = std::size_t>
struct histogram_reducer {
using value_type = T;
using accumulator_type = std::vector<Counter>;
histogram_reducer(std::size_t n) : n_(n) {}
histogram_reducer(std::size_t n, const value_type& lowest, const value_type& highest)
: n_(n), lowest_(lowest), highest_(highest) {}
void operator()(accumulator_type& acc, const value_type& x) const {
if (lowest_ <= x && x <= highest_) {
auto delta = (highest_ - lowest_) / n_;
std::size_t key = (x - lowest_) / delta;
assert(0 <= key);
assert(key < n_);
acc[key]++;
}
}
void operator()(accumulator_type& acc1, const accumulator_type& acc2) const {
// acc1 += acc2
std::transform(acc1.begin(), acc1.end(), acc2.begin(), acc1.begin(),
[](const Counter& c1, const Counter& c2) { return c1 + c2; });
}
accumulator_type identity() const {
return std::vector<Counter>(n_, 0);
}
private:
std::size_t n_;
value_type lowest_ = std::numeric_limits<value_type>::lowest();
value_type highest_ = std::numeric_limits<value_type>::max();
};
int main() {
// monoid: (int, +, 0)
std::vector<int> v1 = {1, 2, 3, 4, 5};
int sum = ::reduce(v1.begin(), v1.end(), plus_reducer<int>{});
std::cout << sum << std::endl;
// monoid: (double, *, 1)
std::vector<double> v2 = {0.1, 0.2, 0.3, 0.4, 0.5};
double product = ::reduce(v2.begin(), v2.end(), multiplies_reducer<double>{});
std::cout << product << std::endl;
// monoid: (double, <min>, double_max)
double min = ::reduce(v2.begin(), v2.end(), min_reducer<double>{});
std::cout << min << std::endl;
// monoid: (double, <max>, double_min)
double max = ::reduce(v2.begin(), v2.end(), max_reducer<double>{});
std::cout << max << std::endl;
// minmax reducer
auto [min2, max2] = ::reduce(v2.begin(), v2.end(), minmax_reducer<double>{});
std::cout << min2 << " " << max2 << std::endl;
// string concatenation
std::vector<std::string> v3 = {"H", "e", "l", "l", "o", ", ", "world!"};
std::string concatenated = ::reduce(v3.begin(), v3.end(), plus_reducer<std::string>{});
std::cout << concatenated << std::endl;
// histogram for normal distribution
std::size_t n = 10000;
std::mt19937 engine(std::random_device{}());
std::normal_distribution<> dist(0.0, 1.0);
std::vector<double> samples(n);
for (auto&& x : samples) {
x = dist(engine);
}
int rows = 10;
int columns = 40;
auto histogram = ::reduce(samples.begin(), samples.end(), histogram_reducer<double>(rows, -3.0, 3.0));
auto max_count = ::reduce(histogram.begin(), histogram.end(), max_reducer<std::size_t>{});
for (const auto& count : histogram) {
auto n_chars = count * columns / max_count;
std::cout << std::string(n_chars, '*') << std::endl;
}
}
@s417-lama
Copy link
Author

The output will be:

15
0.0012
0.1
0.5
0.1 0.5
Hello, world!
*
*****
*************
****************************
****************************************
***************************************
****************************
**************
****
*

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment