有没有人写过一个符合 C++ STL 的算法，它结合std::transform并std::accumulate成为一个支持一元、二元甚至（n 元！）变体的单通道算法，比如说std::transformed_accumulate？我想要这个，因为我发现这种模式在线性代数中高度可重用，例如在 (l1-) 范数计算中。l1-范数计算元素绝对值的总和。
问问题
4652 次
5 回答
11
嗯...我敢打赌，您可以通过将转换嵌入到二元谓词中来做到这一点，转换元素并在转换后累积。
struct times2accumulator {
int operator()( int oldvalue, int newvalue ) const {
return oldvalue + 2*newvalue;
}
};
int r = std::accumulate( v.begin(), v.end(), 2, times2accumulator() );
该函子相当于：
struct times2 {
int operator()( int x ) {
return 2*x;
}
};
std::vector<int> tmp; tmp.reserve( v.size() );
std::transform( v.begin(), v.end(), std::back_inserter(tmp), times2 );
int r = std::accumulate( tmp.begin(), tmp.end(), 0 );
当然这可以是通用的，只需将转换函子传递给一个通用的基本函子：
template <typename Transform>
struct transform_accumulator_t {
Transform t;
transform_accumulator_t( Transform t ) : t(t) {}
int operator()( int oldvalue, int newvalue ) const {
return oldvalue + t(newvalue);
}
};
// syntactic sugar:
template <typename T>
transform_accumulator_t<T> transform_accumulator( T t ) {
return transform_accumulator_t<T>(t);
}
int r = std::accumulate(v.begin(), v.end(), 0, transform_accumulator(times2));
您还可以概括容器中的类型......甚至创建一个更通用的 transform_accumulator ，它同时采用累加器和转换函子并按顺序应用它们。实际的实现留给读者作为练习。
于 2012-05-14T23:24:19.697 回答
2
虽然它可能不完全符合最初的意图，但std::inner_product基本上是你的二进制版本。您将一个初始值、两个范围和两个函子传递给它，并将它们应用为：
T acc = initial_value;
while (begin1 != end1) {
acc = binary_op1(acc, binary_op2(begin1, begin2);
++begin1;
++begin2;
return acc;
所以，对于你的 L1，你会按照这个一般顺序做一些事情：
norm = std::inner_product(input1.begin(), input1.end(),
input2.begin(), input2.end(),
std::plus<int>(), std::abs);
只是这不太奏效——现在，它试图传递std::abs你真正需要一个组合两个输入的二进制函数的地方，但我不确定这两个输入应该如何组合。
std::partial_sum与您的一元版本相当接近，除了在累积结果的同时，它（尝试）写出每个中间结果，而不仅仅是最终结果。为了获得最终结果，您必须编写（并传递一个实例）一种只保存一个值的无操作迭代器：
template<class T, class Dist=size_t, class Ptr = T*, class Ref = T&>
class unique_it : public std::iterator<std::random_access_iterator_tag, T, Dist, Ptr, Ref> {
T &value;
public:
unique_it(T &v) : value(v) {}
T &operator*() { return value; }
unique_it &operator++() { return *this; }
unique_it &operator+(size_t) { return *this; }
unique_it &operator++(int) { return *this; }
};
template <class T>
unique_it<T> make_res(T &v) { return unique_it<T>(v); }
有了这个，你的 L1 标准化看起来像这样：
int main(){
double result=0.0;
double inputs[] = {1, -2, 3, -4, 5, -6};
std::partial_sum(
inputs, inputs+6,
make_res(result),
[](double acc, double v) {return acc + std::abs(v);});
std::cout << result << "\t";
return 0;
}
于 2012-05-15T00:23:46.657 回答
1
我很惊讶没有人说如何用 Boost.Range 做到这一点：
accumulate(v | transformed((int(*)(int))&std::abs), 0);
其中 v 是单通范围（即任何 STL 容器）。必须指定 abs 重载，否则这将与 Haskell 一样优雅。
于 2014-10-09T21:40:36.823 回答
1
如果您想使用一些并行性，我使用 OpenMP 制作了一个快速版本：
template <class T,
class InputIterator,
class MapFunction,
class ReductionFunction>
T MapReduce_n(InputIterator in,
unsigned int size,
T baseval,
MapFunction mapper,
ReductionFunction reducer)
{
T val = baseval;
#pragma omp parallel
{
T map_val = baseval;
#pragma omp for nowait
for (auto i = 0U; i < size; ++i)
{
map_val = reducer(map_val, mapper(*(in + i)));
}
#pragma omp critical
val = reducer(val, map_val);
}
return val;
}
它很快，但肯定有优化的空间，尤其是for (auto i = 0U; i < size; ++i)我认为。（但我不知道如何使用 OpenMP 制作仅限迭代器的版本，任何帮助将不胜感激！）。
在对 1000000 个元素数组的快速测试中，计算迭代 1000 次以获得平均值，我进行了一些比较。
版本 1：
for (auto i = 0U; i < size; ++i)
val += std::pow(in[i][0], 2) + std::pow(in[i][1], 2);
编译时得分：
g++： 30秒g++ -O3: 2.6 秒
版本 2：
我认为这个版本是最优化这个计算的。（它给出了最好的结果）。
#pragma omp parallel reduction( + : val )
{
double map_val = 0.0;
#pragma omp for
for (int i=0; i < size; ++i)
{
map_val += std::pow(in[i][0], 2) + std::pow(in[i][1], 2);
}
val += map_val;
}
g++ -O3: 0.2 秒 (这是最好的)
版本 3
这个版本使用了我之前展示的 MapReduce_n 函数模板：
double val = MapReduce_n(in, size, 0.0, [] (fftw_complex val)
{
return std::pow(val[0], 2.0) + std::pow(val[1], 2.0);
}, std::plus<double>());
g++ -O3: 0.4 秒，所以不直接使用 OMP reduce 会有一点开销。然而，它不允许自定义操作符，所以在某一时刻，你（遗憾地）不得不以速度换取通用性。
于 2013-08-19T08:19:48.493 回答
1
从 C++17 开始，还有std::transform_reduce，它还具有可并行化的优点。
https://en.cppreference.com/w/cpp/algorithm/transform_reduce
于 2018-07-11T03:06:51.440 回答