Get the average value from a vector of Integers

user_4043556 0
Viewed 19288

I have been unable to find a way of getting the average value from a vector of integers in C++.

I can't possibly start adding all of the values because I could exceed the maximum integer accepted value.

How can I calculate this efficiently and quickly ? Are there any standard libraries in the C++ language to do that ?

vector c++
3 Answers

The trick is that you don't have to store the entire sum of the vector. You can divide integers during iteration and store the remainder to add it to the next value.

This allows to create algorithm that is very memory efficient. I didn't make a benchmark but it should be OK for processors that have hardware division module.

Here a solution that shouldn't overflow as long as el + vector.size() fits into ACCU_T for each element of the vector. It should be possible to remove this limitation if we use processor overflow flag.

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;
}

It doesn't use any floating point or big numbers. The variable of accu has a value of sum(vec) % vec.size() at the end of function.

Yep, here's a version for GCC and Clang that shouldn't overflow for any unsigned integer.

(The exact constraint here is that el + vector.size() cannot be bigger that 2 times as much as ACCU_T can fit.)

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;
}
user_30524380
Related