Question

Im trying to return a QVector from a function which is supposed to calculate the moving average. My question is how to make the function more efficient. The math is fine, Im more wondering if I do something wrong in returning the QVector. Here is the Code I have so far:

QVector<double> moving_exponential_average(const QVector<double>& a, double lambda) {
        if(lambda <0 ) {
            lambda = 0;
        }
        if(lambda >1) {
            lambda = 1;
        }
        QVector<double> b;
        b.reserve(a.size());

        b.append(a[0]);
        double l_inv = 1-lambda;
        for(unsigned int i = 1; i < a.size(); ++i) {
            b.append(a[i]*lambda+l_inv*b[i-1]);
        }
        return b;
    }

I use the default constructor to keep the QVector from setting a default value. I tried the same thing with resize which is much slower. Do you have any suggestions how this can be optimized?

Regards

No correct solution

OTHER TIPS

QVector implementation shares its data ( http://qt-project.org/doc/qt-5.0/qtcore/implicit-sharing.html#implicitly-shared ) so you do nothing wrong.

QVector is a shared class. Copying is a constant operation and should be really fast.

You are allocating a new QVector for every call. An alternative could be that you supply an input vector and the output vector to the function:

void moving_exponential_average(const QVector<double> &a, QVector<double> &b, double lambda)
{
    //store result in b vector
    //do not use append but use the [] operator, like
    b[0] = a[0];
    ...
    b[i] = a[i] * lambda + l_inv * b[i - 1];
}

QVector<double> a;
QVector<double> b;  //make same size as a
//then repeatedly call
while (notDone) {
    update(a);
    moving_exponential_average(a, b, lambda);
}

With this code, the result vector is allocated only once.

Since you claim that the "return" takes longest, the problem may not be in the function itself, but at the site where the returned value is used.

Alas, here's where your code wastes time:

  1. In allocation of the QVector each time the average is invoked. Presumably it's called repeatedly, so there's no need to have it allocate a new vector each time.

  2. In QVector::operator[]. It has a bit more overhead than plain array access because there's this pesky isDetached call done on every call to operator[].

  3. In QVector::append. Not only does it call isDetached, but also it checks and modifies the length as well.

Note that there's absolutely nothing wrong with returning of your value. It's a trivial operation and takes next to no time. You're doing it OK when it comes to return - and return only. But you don't show us how you use the returned value, so I can't tell you if maybe you're doing something wrong there.

To prevent repeated allocations and operator[] overhead, you could use a class that keeps a vector ready for reuse, and use a pointer-to-vector's-data instead of using the vector directly.

To make it go any faster would probably require the use of SIMD intrinsics.

class Averager {
  QVector<double> m_result;
  Q_DISABLE_COPY(Averager)
public:
  QVector<double> movingExponentialAverage(const QVector<double> & a, double lambda) {
    if (lambda < 0) lambda = 0; else if (lambda > 1) lambda = 1;
    m_result.resize(a.size());
    double * b = m_result.data();
    double lInv = 1-lambda;
    for(int i = 1; i < a.size(); ++i) {
      b[i] = a[i] * lambda + b[i-1] * l_inv;
    }
    return m_result;
  }
};

void test() {
  Averager avg; 
  QVector<double> src;
  while (true) {
    update(src);
    const QVector<double> & dst = avg.movingExponentialAverage(src, 0.2);
    ...
  } 
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top