如何使用std :: accumulate和lambda计算平均值？

Question

我有一个标准库的容器存储大数值，它们非常大以至于如果将它们相加可能会导致溢出。假设这个容器是这样的：

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

我想用std::accumulate计算这个容器的平均值，但我不能把所有数字加起来。我将使用 v[0]/v.size() + v[1]/v.size() + ... 来计算它。所以我设置了：

auto lambda = ...;
std::cout << std::accumulate(v.begin(), v.end(), 0, lambda) << std::endl;

以下是我迄今为止尝试过的内容，其中->表示输出：

lambda = [&](int a, int b){return (a + b)/v.size();};  ->  1
lambda = [&](int a, int b){return a/v.size() + b/v.size();};  ->  1
lambda = [&](int a, int b){return a/v.size() + b;};  ->  10

如何获得正确的平均值，使输出为5？

- EMBLEM

---

"5" 不是正确的答案。 - Ben Voigt

如果你正在使用整数除法，那么就是这样。 - EMBLEM

在计算平均值时不使用整数除法。如果和 std::accumulate 一起使用，情况会更糟——它会破坏你的部分总和。如果您希望最终结果按整数除法规则四舍五入，请在问题中明确说明（那么您就不是在求平均值）。否则，每个读者都会认为您使用整数除法是一个 bug。 - Ben Voigt

Answer 1

不应使用整数来存储结果：

传递给函数accumulate的返回类型：
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op ); 取决于第三个参数的类型：(T init) 因此，您必须在那里放置0.0以获得结果为double。

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
using namespace std;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int main()
{
    auto lambda = [&](double a, double b){return a + b / v.size(); };
    std::cout << std::accumulate(v.begin(), v.end(), 0.0, lambda) << std::endl;
}

- AdamF

---

@rpattabi，您能详细说明一下如何在没有返回类型的情况下重现警告吗？我无法做到。 - AdamF

你的 lambda 函数的第二个类型不是指向向量元素的类型吗？也就是说，auto lambda = [&](double a, int b){//... - Chris_128

它不能被转换为int，因为这样除法就不正确了。如果您想将其作为int传递，则应稍后将其强制转换为double：auto lambda = [&](double a, int b) {return a + (double)b / v.size(); }; - AdamF

好的建议。请考虑在您的答案中使用 static_cast<double>(b)。我认为这比当前的答案更好，因为它清楚地显示了 lambda 表达式的哪个参数来自累加器的传递和哪个是向量的元素。此外，它明确地显示了正在进行转换，并且不会在 lambda 表达式的参数中隐式地进行转换。 - Chris_128

如果 v 是全局的，你不需要在 lambda 函数中捕获任何东西。实际上，在你的例子中，lambda 函数没有捕获任何东西。 - Axel Krypton

Answer 2

这种方法可能不太完美，但它可以在容器中没有 size() 方法的情况下正常工作：

auto lambda = [count = 0](double a, int b) mutable { return a + (b-a)/++count; };

这利用了新的C++14功能“initialized captures”在lambda中存储状态。 （您可以通过捕获额外局部变量来实现相同的事情，但它的作用域是局部作用域，而不是lambda的生命周期。）对于旧版本的C ++，您可以将“count”放入结构体的成员变量中，并将lambda体放置为其“operator()（）”实现。

为了防止舍入误差的积累（或至少大大减少），可以采取以下措施：

auto lambda = [count = 0, error = 0.0](double a, int b) mutable {
   const double desired_change = (b-a-error)/++count;
   const double newa = a + (desired_change + error);
   const double actual_change = newa - a;
   error += desired_change - actual_change;
   return newa;
};

- Ben Voigt

---

使用这个近似公式处理大数据集是很好的选择，因为原始公式中 double 类型的精度可能不够。 - AdamF

@AdamF：可以跟踪错误项，以防止舍入误差累积。 - Ben Voigt

太好了。在之前的评论中，我也想承认你的第一个公式：）我用过几次，它很强大，我们甚至不需要将整个数组保存在内存中。 - AdamF

@BenVoigt 很好的回答！你应该提到 lambda 捕获表达式只在 C++14 中有效。 - vsoftco

@vsoftco：我一直打算这样做，但后来对舍入误差产生了兴趣。谢谢你提醒我。 - Ben Voigt

使用误差项大致相当于使用两倍的精度。减少误差的另一种方法是减少表达式树的深度。accumulate使用左折叠，这是最坏的情况（线性深度）。 - Arne Vogel

Answer 3

您的“平均值”是lambda的第一个参数，因此以下内容是正确的。

lambda = [&](int a, int b){return a + b/v.size();};

- Ken Bloom

---

整数四舍五入会不会有问题？ - dwcanillas

Answer 4

我还没有看到这种解决方案，它不需要传递向量的大小，因为使用v.begin()和v.end()已经控制了范围：

double mean = accumulate(v.begin(), v.end(), 0., [](double x, double y) { return x+y; }) / v.size();

可以用std::distance(start,end)替换v.size()来进一步改进。

- slrx

Answer 5

你使用的三个lambda函数不够优秀。

lambda = [&](int a, int b){return (a + b)/v.size();};  ->  1
lambda = [&](int a, int b){return a/v.size() + b/v.size();};  ->  1
lambda = [&](int a, int b){return a/v.size() + b;};  ->  10

这里使用的参数a在给定时间点上承载向量特定索引的平均值。例如，当'b'的值为1时，'a'的值为0.0，当'b'在那一瞬间变为2时，它应该是'0.1'。 因此很明显，在每次调用lambda函数时，'a'都不需要被v.size()除。

针对所述情况的正确lambda函数如下：

lambda = [&](double x,double y){return x+y/v.size();}

这里我们通过引用捕获，只是因为我们需要 v.size() 的值，如果预先知道 vector 的大小，可以事先传递其大小的值。

工作的程序是

    #include<iostream>
    #include<numeric>
    #include<vector>
    using namespace std;

    int main(){
        vector<int> v(10);
        iota(v.begin(),v.end(),1);
        double x=accumulate(v.begin(),v.end(),0.0,[&](double x,double y) {return x+y/v.size();});
        cout << x << endl;
    }

附言：'iota'用于以递增的方式初始化范围，在此处它将向量从1到10进行初始化

- Pyder

Answer 6

显然你不需要这么麻烦，但是你可以创建一个简单的“统计计算器”

struct StatsCalculator
{
   size_t count;
   double sum;
   double sumSq;
   
   double mean() const { return count ? sum/count : NaN(); }
   double variance() const { return count ? (sumSq-sum*sum/count)/count : NaN();  }
   std::tuple<double,double> meanAndVariance() { return { mean(), variance() }; 
   void addValue( double val ) { ++count; sum += val; sumSq += val*val; }
};

那么你的lambda怎么样？在迭代之前创建StatsCalculator实例，然后

auto myLambda = [](StatsCalculator* calculator, int value)
   { calculator->addValue(static_cast<double>(value)); return calculator; }

然后进行迭代：

StatsCalculator calc;
double mean = std::accumulate(y.begin(), y.end(), &calc, myLambda)->mean();

当然，您可以请求平均值和方差的元组。

- CashCow