从整数向量中获取平均值

Question

我一直无法找到从C++整数向量中获取平均值的方法。

我不可能开始添加所有值，因为我可能会超过可以接受的最大整数值。

如何高效快速地计算？ C++语言中是否有任何标准库可以做到这一点？

- dimitris93

---

你可以使用 double 进行累加。由于整数的平均值不一定是整数，因此似乎你需要浮点数。 - 5gon12eder

那么就不要累加到一个 int 中（例如使用 uint64_t）。 - Oliver Charlesworth

如果您的向量包含32位整数，可以使用int64_t。如果您有64位整数，则可以使用__int128_t或等效类型（假设您的编译器提供它）。 - Cornstalks

伙计们，如果你需要对100万个整数求平均值，在使用long（或者说是long long）时，它会溢出。而使用双精度浮点数时，则会导致平均值的精度严重下降。他确实需要更好的解决方法... - Christophe

@Christophe - 如果我们所说的“整数”是指“int”，那么1百万不会溢出。 - Oliver Charlesworth

Answer 1

使用std::accumulate和足够宽的整数类型进行求和是常用的方法：

double avg1(std::vector<int> const& v) {
    return 1.0 * std::accumulate(v.begin(), v.end(), 0LL) / v.size();
}

如果这个求和超过了整型的范围（23百万个整数的平均值至少得是4.01x10¹¹，也就是说，它甚至无法适应一个int32_t...所以你完全没问题，但如果你有更多数量级的数字或者使用更大的int类型，就需要使用常见的“在线”算法来计算平均值：

double avg2(std::vector<int> const& v) {
    int n = 0;
    double mean = 0.0;
    for (auto x : v) {
        double delta = x - mean;
        mean += delta/++n;
    }
    return mean;
}

这不会溢出，也不太容易失精，但由于需要多次额外的除法计算，可能会更加昂贵。

- Barry

---

有没有一个资源可以分析avg2的误差传播？我很难理解这会对带有双重“T init”的naive std::accumulate有什么影响。使用双精度16-17位数字和32位整数10位数字，64位整数约20位数字。 - Captain Giraffe

@CaptainGiraffe jstor 或者 tandf。 - Barry

@CaptainGiraffe - 想象一下一个有2^53个条目的向量，每个条目的值都为1（也可以想出需要更少条目的例子...） - Oliver Charlesworth

@OliverCharlesworth 那个向量的计算代价太高了。=) - Captain Giraffe

@CaptainGiraffe - 的确如此！但是这说明了一个问题 - 一旦输入值低于累加器的ULP，它们就不会起到贡献作用。 - Oliver Charlesworth

Answer 2

我一直无法找到在C++中从整数向量中获取平均值的方法。我不可能开始添加所有值，因为我可能会超过接受的最大整数值。如何高效快速地计算？在C++中有任何标准库吗？

有很多关于查找总和的讨论，这可能太大，即使是uint64_t也无法表示。

所以按照这个建议，不要担心...

我使用过并且推荐一个名为"gmpxx.h"的多精度C++库，对其印象非常好。

我已经用它完成了几个有趣的任务，包括生成一个大的斐波那契数列，似乎没有任何努力。它易于使用，而且出人意料地快速，我在网上找到了如何使用的示例。

代码片段：

mpz_class  n;   // a multi-precision integer, 
n = 1;          // easy initialize
size_t F = 1000; 
for (size_t i=1; i<=F; ++i)
   n = n * i;
// show
std::string Fstr = digiComma(n);  // inserts comma's
std::cout << "\n" << F << "! = " << Fstr
          << "\n" << digitCnt(Fstr) << " bytes " <<  std::endl;

我的输出是一个2568个字符（>1900个数字），逗号分隔的大整数值，处理时间小于20毫秒。

1000！= 402,387,260,077,093,773,543,702,433,923,003,985,719,374,864,210,714,632,543,799, 910,429,938,512,398,629,020,592,044,208,486,969,404,800,479,988,610,197,196,058, 631,666,872,994,808,558,901,323,829,669,944,590,997,424,504,087,073,759,918,823, 627,727,188,732,519,779,505,950,995,276,120,874,975,462,497,043,601,418,278,094, 646,496,291,056,393,887,437,886,487,337,119,181,045,825,783,647,849,977,012,476, 632,889,835,955,735,432,513,185,323,958,463,075,557,409,114,262,417,474,349,347, 553,428,646,576,611,667,797,396,668,820,291,207,379,143,853,719,588,249,808,126, 867,838,374,559,731,746,136,085,379,534,524,221,586,593,201,928,090,878,297,308, 431,392,844,403,281,231,558,611,036,976,801,357,304,216,168,747,609,675,871,348, 312,025,478,589,320,767,169,132,448,426,236,131,412,508,780,208,000,261,683,151, 027,341,827,977,704,784,635,868,170,164,365,024,153,691,398,281,264,810,213,092, 761,244,896,359,928,705,114,964,975,419,909,342,221,566,832,572,080,821,333,186, 116,811,553,615,836,546,984,046,708,975,602,900,950,537,616,475,847,728,421,889, 679,646,244,945,160,765,353,408,198,901,385,442,487,984,959,953,319,101,723,355, 556,602,139,450,399,736,280,750,137,837,615,307,127,761,926,849,034,352,625,200, 015,888,535,147,331,611,702,103,968,175,921,510,907,788,019,393,178,114,194,545, 257,223,865,541,461,062,892,187,960,223,838,971,476,088,506,276,862,967,146,674, 697,562,911,234,082,439,208,160,153,780,889,893,964,518,263,243,671,616,762,179, 168,909,779,911,903,754,031,274,622,289,988,005,195,444,414,282,012,187,361,745, 992,642,956,581,746,628,302,955,570,299,024,324,153,181,617,210,465,832,036,786, 906,117,260,158,783,520,751,516,284,225,540,265,170,483,304,226,143,974,286,933, 061,690,897,968,482,590,125,458,327,168,226,458,066,526,769,958,652,682,272,807, 075,781,391,858,178,889,652,208,164,348,344,825,993,266,043,367,660,176,999,612, 831,860,788,386,150,279,465,955,131,156,552,036,093,988,180

2568字节

实际用时0m0.013秒

用户用时0m0.004秒

系统用时0m0.000秒

那么uint64_t有多大呢？我认为可以容纳的最大斐波那契数是Fib(93)。

- 2785528

---

这个工具是整数精确的，没有浮点/双精度近似，我怀疑它没有任何限制，只有你的内存。 - 2785528

这是C++，但是它有一些来自C语言的影响。它是一个“标准库”吗？我认为是的，但你在问这个问题。 - 2785528

GMP库（GNU多精度库）-- 初版发布于1991年，已有25年历史。最新稳定版本为6.1.0（发布于2015年11月1日，4个月前）。 - 2785528

Answer 3

诀窍在于您不必存储向量的整个总和。您可以在迭代过程中进行整数除法，并将余数存储以添加到下一个值。

这使得可以创建非常内存高效的算法。我没有进行基准测试，但对于具有硬件除法模块的处理器应该是可以的。

这里提供了一种解决方案，只要每个向量元素的el + vector.size()适合ACCU_T，就不应该溢出。如果使用处理器溢出标志，应该可以消除此限制。

template<typename T, typename ACCU_T = uintmax_t>
T vec_average(const std::vector<T> &vec)
{
    const ACCU_T size = (ACCU_T)vec.size();
    T avg = 0;
    ACCU_T accu = 0;
    for (const T &el : vec)
    {
        accu += (ACCU_T)el;
        avg += (T)(accu / size);
        accu %= size;
    }
    return avg;
}

它不使用任何浮点数或大数。 accu 变量在函数结束时的值为 sum(vec) % vec.size()。

---

是的，这里有一个适用于GCC和Clang的版本，不应该对任何无符号整数造成溢出。

（这里的确切限制是el + vector.size()不能比ACCU_T能容纳的两倍还要大。）

template<typename T, typename ACCU_T = uintmax_t>
T vec_average(const std::vector<T> &vec)
{
    const ACCU_T size = (ACCU_T)vec.size();
    const T overflowAvg = (T)((ACCU_T(-1)) / size);
    const ACCU_T overflowAccu = overflowAvg * size;
    T avg = 0;
    ACCU_T accu = 0;
    for (const T &el : vec)
    {
        if (__builtin_add_overflow(accu, (ACCU_T)el, &accu))
        {
            avg += overflowAvg;
            accu -= overflowAccu;
        }
        avg += (T)(accu / size);
        accu %= size;
    }
    return avg;
}

- Piotr Siupa