9
\$\begingroup\$

I have just started to learn C++ and wanted to improve my function. I am making a basic statistical API and am calculating an SMA (simple moving average) for some data. This function provides the correct, output but it is quite messy and convoluted I am sure.

I wanted to solve the problem before asking for help which is why it is probably such a mess, but now I have solved it I would like advice on how I can improve it.

I am using a loop within a loop to create a sub-vector which I sum and divide to get my average. I did this, because I could not work out how to get accumulate to calculate the beginning and ending values via indexing.

I also got this pop up: "The thread 0x76d0 has exited with code 0 (0x0)." I haven't really been able to find a good explanation other than it is a debug thing and you can press continue (Visual Studio).

std::vector <long double> SMA(std::vector <long double> &ARR, int lag) {
    std::vector<long double> sma_values;

    for (size_t i = 0; i < ARR.size(); ++i) {
        if (i < lag) {
            sma_values.push_back(std::numeric_limits<double>::quiet_NaN());
        }
        else {
            std::vector<long double> temp_vector;

            for (size_t n = 0; n < lag; ++n) {
                temp_vector.push_back(ARR[i - n]);
            }

            long double sum = accumulate(temp_vector.begin(), temp_vector.end(), 0.0, std::plus<long double>());
            long double average = sum / lag;
            sma_values.push_back(average);
        }
    }

    return sma_values;
}
\$\endgroup\$
2
  • 7
    \$\begingroup\$ "The thread 0x76d0 has exited with code 0 (0x0)." is not a problem--its just telling you that the program's main thread exited normally. A non-zero code would be much more likely to indicate a problem. \$\endgroup\$ Jun 4 at 2:08
  • 1
    \$\begingroup\$ You can do this with a pair of indexes (trailing and leading) representing the window position within the larger vector. Calculate the average for that window, then subtract the trailing value from the sum, increment the trailing and leading indexes, add the leading value to the sum, calculate the next average, rinse and repeat. No copying of data from one array to another, no excessive re-summing of values you've already iterated over. \$\endgroup\$
    – jwdonahue
    Jun 5 at 17:39

3 Answers 3

6
\$\begingroup\$

Suggestion 1

std::vector <long double> SMA(std::vector <long double> &ARR, int lag)

What is lag? I would rename it to requested_window_length. Also, I would rename ARR to vec.

Advice 1

std::vector<long double> temp_vector;

You don't need this. Just keep track of

  1. the current sum of a window,
  2. the current window width.

When you include each next value to the window, just subtract the leftmost value from the current window sum and add the aforementioned next value to the window sum.

Note 1

I find it strange that you prepopulate incomplete prefix SMAs with the NaN values. How about to change those placeholder values with partial SMAs?

Alternative implementation

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

std::vector<long double> SMAv2(std::vector<long double>& vec, size_t requested_window_width) {
    if (vec.size() < requested_window_width) {
        std::vector<long double> empty;
        return empty;
    }

    std::vector<long double> sma_values(vec.size() + requested_window_width - 1);
    long double window_sum = 0.0;
    size_t index = 0;
    size_t window_width = 0;

    for (; index < requested_window_width; ++index) {
        window_sum += vec[index];
        sma_values[index] = window_sum / (++window_width);
    }

    for (; index < vec.size(); ++index) {
        window_sum -= vec[index - requested_window_width];
        window_sum += vec[index];
        sma_values[index] = window_sum / window_width;
    }

    for (size_t i = 0; i < requested_window_width - 1; ++index, ++i) {
        window_sum -= vec[index - requested_window_width];
        sma_values[index] = window_sum / (--window_width);
    }

    return sma_values;
}

std::vector<long double> SMAv3(std::vector<long double>& vec, size_t requested_window_width) {
    if (vec.size() < requested_window_width) {
        std::vector<long double> empty;
        return empty;
    }

    std::vector<long double> sma_values(vec.size() - requested_window_width + 1);
    long double window_sum = 0.0;
    size_t index = 0;
    size_t output_index = 0;
    size_t window_width = 0;

    for (; index < requested_window_width; ++index) {
        window_sum += vec[index];
    }

    for (; index < vec.size(); ++index, ++output_index) {
        sma_values[output_index] = window_sum / requested_window_width;
        window_sum -= vec[index - requested_window_width];
        window_sum += vec[index];
    }

    sma_values[output_index] = window_sum / requested_window_width;
    return sma_values;
}

int main()
{
    std::vector<long double> input_vector = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0 };
    const size_t requested_window_width = 3;

    std::vector<long double> aves1 = SMA(input_vector, requested_window_width);
    std::vector<long double> aves2 = SMAv2(input_vector, requested_window_width);
    std::vector<long double> aves3 = SMAv3(input_vector, requested_window_width);

    std::cout << "OP SMA:\n";

    for (long double d : aves1) {
        std::cout << d << "\n";
    }

    std::cout << "coderodde SMAv2:\n";

    for (long double d : aves2) {
        std::cout << d << "\n";
    }

    std::cout << "coderodde SMAv3:\n";

    for (long double d : aves3) {
        std::cout << d << "\n";
    }
}

\$\endgroup\$
6
  • \$\begingroup\$ Hi thanks for your input and taking the time to read and tweak my code I really appreciate it - regarding the pre-population of nans that's what the existing software I use produces and I was just looking to replicate the results from that \$\endgroup\$
    – JPWilson
    Jun 4 at 13:40
  • \$\begingroup\$ Had the same ideas you presented in "Advice 1". However I am not sure if it could be problematic in some special cases because of floating point accuracy stuff. Though in such cases it might then also be problematic to simply adding the values in their given order. \$\endgroup\$ Jun 4 at 20:42
  • 2
    \$\begingroup\$ The "lag" of a moving average is actually a well-known, widely-recognized term of art. So, while I would normally underscore your point about using clear, recognizable names (and tend to use very long descriptive identifier names in my own code), I don't think the use of "lag" here is at all problematic or to be discouraged. And I definitely don't see how "vec" is any clearer than "ARR". Even though I don't know what "ARR" stands for either, I do know that naming a variable using an abbreviation of its type is not useful to anyone. \$\endgroup\$
    – Cody Gray
    Jun 5 at 12:54
  • \$\begingroup\$ When you include each next value to the window, just subtract the leftmost value from the current window sum and add the aforementioned next value to the window sum. - Floating point math is not strictly associative; that will give you different rounding error, and the possibility of error accumulation as you go on. (@JPWilson). \$\endgroup\$ Jun 5 at 22:46
  • \$\begingroup\$ Also, for short lags, the difference between FP add throughput vs. latency can mean it's actually faster to redo the sum. (Although maybe less so with long double on a modern x86 on C++ implementations where that's the 80-bit x87 format. Still, Zen2 for example has 5 cycle latency fadd, with 1 / clock throughput, so add and sub into a single running total would be a 10-cycle latency bottleneck for the loop. That's enough time to re-add 11 elements (with 10 FP additions), if out-of-order exec can overlap those dependency chains between outer loop iterations. \$\endgroup\$ Jun 5 at 22:48
6
\$\begingroup\$

Use const-references when you only read an argument

std::vector <long double> SMA(std::vector <long double> &ARR, int lag) {

A signature like this has the same effect as a coffee brewed by using energy drinks instead of water: it immediately gets flagged and asks for special care and awareness.

Why? Because we have a non-const reference here, ARR. A non-const reference indicates that we will use that argument as output; the function is able to communicate the changes within this functions back to the outside not only via its return value, but also via this argument.

This unfortunately also means that we cannot use temporary values, for example, which is a pitty. But if we take a look at the inner function, we see that nowhere ARR is modified. This means that your real function signature should be

//                            vvvvv
std::vector <long double> SMA(const std::vector <long double> &ARR, int lag) {

This will also ensure that you don't change ARR in this function by accident later on, as the compiler will (rightfully) yell at you.

Use a single scalar value for accumulation

            std::vector<long double> temp_vector;

            for (size_t n = 0; n < lag; ++n) {
                temp_vector.push_back(ARR[i - n]);
            }

            long double sum = accumulate(temp_vector.begin(), temp_vector.end(), 0.0, std::plus<long double>()); 
            long double average = sum / lag;

Let's have a look at the accumulate line and std::accumulate's documentation: the effects of accumulate are just like

sum = (... ((temp_vector[0] + temp_vector[1]) + temp_vector[2]) + ... ) + temp_vector[lag]

But since the temp_vector elements just stem from the original ARR, we can use that one instead:

sum = (... ((ARR[i] + ARR[i - 1]) + ARR[i - 2]) + ... ) + ARR[i - lag]

At that point, we can just get rid of temp_vector and immediately sum, as we keep the associativity of std::accumulate:

            long double sum = 0.0;

            for (size_t n = 0; n < lag; ++n) {
                sum += ARR[i - n];
            }

            const long double average = sum / lag;

But you can still use std::accumulate if you want to:

const long double sum = std::accumulate(ARR.begin() + (i - n)
                                       ,ARR.begin() + i
                                       ,0.0
                                       ,std::plus<long double>());

however, that can yield other results, since we're now summing in reverse order. Which brings us to the next topic.

Prefer easier ranges

Let's get back to the previous version:

            for (size_t n = 0; n < lag; ++n) {
                temp_vector.push_back(ARR[i - n]);
            }

First of all: if you don't need to traverse ARR backwards, then don't. Handling indices can be quite a pain. It's a lot easier to have ARR[i], ARR[i+1] in mind than ARR[i], ´ARR[i-1]`, not only for ourself, but also for the machine, as going forward through memory can be a performance improvement. Mind you, it can be an improvement; it depends on the actual hardware and compiler.

But we can also make it faster for humans to understand:

            for (size_t n = i + 1 - lag; n <= i; ++n) {
                temp_vector.push_back(ARR[n]);
            }

Similarly, you might want to move the initial lag values out of your inner loop, e.g.

    for (size_t i = 0; i < lag; ++i) {
        sma_values.push_back(std::numeric_limits<double>::quiet_NaN());              
    }

    for (size_t i = lag; i < ARR.size(); ++i) {
        ...
    }

Overall

I'd also try to improve the naming, if possible. SMA might make sense to you now, but (simple_)moving_average will make sense to you even in three months. Similar, values instead of ARR might be a better name, since it's not actually an array. Remember: the compiler doesn't care about the length of your variable's names, but you might.

With this in mind, we end up with:

std::vector<long double> moving_average(const std::vector<long double> &values, size_t lag) {
    std::vector<long double> averages;

    for (size_t i = 0; i < lag; ++i) {
        averages.push_back(std::numeric_limits<double>::quiet_NaN());              
    }

    for (size_t i = lag; i < values.size(); ++i) {
        long double sum = 0.0;

        // Still traversing backwards to preserve your original
        // accumulation, but you might want to introduce the other
        // variants
        for (size_t n = 0; n < lag; ++n) {
            sum += values[i - n];
        }

        const long double average = sum / lag;
        averages.push_back(average);
    }

    return averages;
}
\$\endgroup\$
3
  • \$\begingroup\$ Hi Thanks for this really useful thanks for taking the time to read my code and give such an insightful reply my code is now a lot more cleaner! \$\endgroup\$
    – JPWilson
    Jun 4 at 13:41
  • \$\begingroup\$ As I commented on another answer, this FP math is not strictly associative. Changing the summation order could produce different rounding. (Not typically better or worse on average unless you know something about your data.) \$\endgroup\$ Jun 5 at 22:57
  • \$\begingroup\$ @PeterCordes Exactly, which is why I kept the original order and the summation of std::accumulate and mentioned it in the answer: "that can yield other results, since we're now summing in reverse order." I'm well aware of the semantics of floating point numbers, otherwise I would not have used that many parentheses in the transformation of std::accumulate to the simple sum ;) \$\endgroup\$
    – Zeta
    Jun 6 at 6:35
3
\$\begingroup\$

Handling ends

Handling the ends of the array where "lag" overhangs the data set one must make assumptions in regard to the missing data. You can zero missing data (same as ignoring it), you can extend data (values below index 0 are the same as item[0] and same for items past the end)

Using a quiet NaN to the start does not represent the unknown nature of these values.

A moving mean should be calculated around a value, the mean of (lag - 1) / 2 values above and below an index to correctly align the result to the input. I will assume you just want super simple moving mean.

For or While?

Which loop to use is has no fixed rules in this case though I suggest you consider how noisy your code is. Generally the standard for;; is noisier than a while loop.

I much prefer while loops over for;; loops to keep noise down. Be warned while loops when first using them over for loops can neglect the increment. However good code is always tested.

Correct type

The second argument int lag represents a size and should be of type size_t. As an int you are suggesting that it could be a negative. This could make sense if you used the sign to define the direction of the calculation.

Names

There are some very poor names used in your code. Here are some suggestions.

  • lag could be just the math term k or the coders view, window, 'meanCount, mean_count, or count`

  • ARR is not an array. It represents a set of values, a better name could be values, numbers, data, ... anything but ARR. Also don't randomly capitalize a variable.

  • sma_values is closer to the mark than ARR however sma stands for Simple Moving Average and as such should be capitalized thus SMA_values.

    But SMA is redundant (we know what we are calculating. Maybe just result is what you can use.

  • The method name SMA is correctly capitalized, yet it is obscure without context, best to spell it out. Could be any of simple_moving_average, SimpleMovingAverage, or simpleMovingAverage depending on your preferred naming style. Or the simple could be dropped moving_average, MovingAverage, or movingAverage.

Be performance aware

As the size of the vector is known at the start of the function you can allocate the memory at the start reducing the overhead when adding to the vector.

The average is calculated using a divide. As the divisor is constant you can improve performance using a multiple. See rewrite's invViewf = 1.0 / viewf.

As the mean count "lag" can be much shorter than the input values length you can split the task into 2 to remove a condition inside the loop. Note this only applies if you extend the first value.

Various early exits can be found to reduce overheads. See next section.

Special states

There are several edge, error, compile states with this function that need to be addressed.

Cases where

  • view == 0 The running mean would be all quiet_NaN.

  • May be no support for quiet_NaN Assert to catch it in dev cycle.

  • view == 1 The running mean would be the same as the input. Just copy the input vector using the assignment operator.

  • values.size() == 0 Nothing to do return an empty vector.

  • Support float, double, long double, and more. Define a template function.

Rewrite

The rewrite extends the first value when calculating the starting sum.

// Extended start
template <typename T>
std::vector <T> MovingAverage(const std::vector <T> &values, size_t view) {    
    if (view == 0) { 
        assert(std::numeric_limits<T>::has_quiet_NaN);
        return std::vector<T> (values.size(), std::numeric_limits<T>::quiet_NaN()); 
    }
    std::vector<T> result;
    const size_t len = values.size();
    if (len == 0) { return result; }
    if (view == 1) { return result = values; }
    result.reserve(len);
    
    size_t i = 0;
    const T viewf = static_cast<T>(view);
    const T invViewf = 1.0 / viewf;
    T sum = values[i] * viewf;
    while (i < len) {
        sum += values[i] - values[i < view ? 0 : i - view];
        result.push_back(sum * invViewf);
        i++;
    }
    return result;
}

Double loop to avoid cost of range checks.

// Extended start
template <typename T>
std::vector <T> MovingAverage(const std::vector <T> &values, size_t view) {    
    if (view == 0) { 
        assert(std::numeric_limits<T>::has_quiet_NaN);
        return std::vector<T> (values.size(), std::numeric_limits<T>::quiet_NaN()); 
    }
    std::vector<T> result;
    const size_t len = values.size();
    if (len == 0) { return result; }
    if (view == 1) { return result = values; }
    result.reserve(len);
    
    size_t i = 0;
    const T viewf = static_cast<T>(view);
    const T invViewf = 1.0 / viewf;
    T sum = values[0] * viewf;
    while (i < view) {
        sum += values[i] - values[0];
        result.push_back(sum * invViewf);
        i++;
    }
    while (i < len) {
        sum += values[i] - values[i - view];
        result.push_back(sum * invViewf);
        i++;
    }    
    return result;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.