alk0v Dec 11 2011 at 04:31

Алгоритм скользящего среднего (Simple Moving Average)

3 min

104K

Comments 15

gribozavr Dec 11 2011 at 05:15

<source=c>if(fmod(window,2)==0)
fmod для целых чисел да ещё и сравнение на строгое равенство чисел с плавающей запятой…

> C++ edition
и где тут C++? Это си, не более.

На каждый элемент результирующего массива лишние ветвления: особые случаи для начала и конца нужны только в начале и в конце, а основной объём данных должен обрабатываться без этого.

Трюк с вычитанием хорош только если вы уверены что не произойдёт никаких катастрофических округлений.

alk0v Dec 11 2011 at 13:07

признаю, по скорости работы код далеко не оптимален и оптимизировать есть куда. Совместными усилиями можем поправить ))

-1

Vladislaff Dec 11 2011 at 10:41

А зачем Вы окно изменяете?
Еще можно бы добавить как считать — задним окном, центром или наперед.
И, мне кажется, не стоит начало и конец отдельно считать, просто значения которые меньше окна не выводить вообще.

alk0v Dec 11 2011 at 13:05

по условиям задачи входной массив должен быть равен выходному, поэтому не выводить данные не получится

ryo_oh_ki Dec 11 2011 at 11:08

Подходит только для квазистатических сигналов. Представьте сигнал у которого амплитуда меняется в разы или у которого собственная частота очень близка к частоте его дискретизации.

A1ien Dec 11 2011 at 12:56

Цифровая обработка такого сигнала дрлжна вестись с оглядкоц на теорему Котельникова. Тоесть оцифровав таким образом сигнал вы должны понимать что то что вы получили в цифре может не совсем соответствовать оригиналу.

ryo_oh_ki Dec 11 2011 at 13:05

Спасибо Кэп.

Eddy_Em Dec 11 2011 at 17:33

Для сигнала с выборосами логично будет использовать сглаживание скользящей медианой. А вообще, естественно, эти «скользящие» алгоритмы применяются лишь для обработки сигналов в реальном времени, либо для обработки сигналов, у которых не прослеживается четкой структуры.

OLS Dec 11 2011 at 11:38

Мне кажется, на практике для сглаживания временного ряда чаще используют реккурентную формулу

output[i] = alpha*input[i] + (1-alpha)*output[i-1]

0<=alpha<=1

Она очень хорошо выравнивает, вычислительно проста, имеет всего 1 параметр, и этот параметр имеет четкий физический смысл в терминах теории автоматического управления.

mromanov Dec 11 2011 at 12:16

Это другой метод, не Simple Moving Average, а Exponential Moving Average.

Lockal Dec 11 2011 at 15:43

Кто-то упомянул C++? Вот мой вариант:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <queue>
#include <vector>

class MovingAverage {
    std::queue<double> window; // окно
    size_t period; // максимальный размер окна
    double sum; // сумма элементов в окне
public:
    MovingAverage(size_t period) : period(period) {}
    double operator()(double num) {
        sum += num;
        window.push(num);
        if (window.size() > period) {
            sum -= window.front();
            window.pop();
        }
        return sum / window.size();
    }
};

int main() {
    using namespace std;
    double indata[] = {1, 2, 3, 2, 4, 5, 4, 5, 4, 5, 6, 2, 5, 6, 6, 7};
    size_t size = sizeof(indata) / sizeof(double);
    vector<double> out(size);

    // применение функтора MovingAverage к исходному массиву
    transform(indata, indata + size, out.begin(), MovingAverage(5));

    // вывод результирующего массива
    copy(out.begin(), out.end(), ostream_iterator<double>(cout, "\n"));
}

Кроме того, такой функтор удобно использовать в классической ситуации, когда данные приходят в реальном времени и по новому значению нужно достроить график скользящей.

gribozavr Dec 11 2011 at 15:59

Не соответствует стандарту. std::transform не обязан в функтор кормить элементы по порядку.

Effects: Assigns through every iterator i in the range [result,result + (last1 — first1)) a new corresponding value equal to op(*(first1 + (i — result)) or binary_op(*(first1 + (i — result)), *(first2 + (i — result))).

Lockal Dec 11 2011 at 17:11

Что интересно, эта цитата из стандарта C++11 не накладывает ограничения на порядок обхода. По крайней мере не так явно, как в старой версии стандарта:

25.2.3 Transform [lib.alg.transform]
Requires: op and binary_op shall not have any side effects.

Мне не очень понятно, зачем нужно было убирать. Вот оставшиеся ограничения:

Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges [first1,last1], [first2,first2 + (last1 — first1)], and [result,result + (last1 — first1)].

Parallel STL, впрочем, пока никто не отменял, поэтому спорить не буду. Пусть будет так:

...
    std::vector<double> &out;

public:
    MovingAverage(std::vector<double> &out, size_t period) : out(out), period(period) {}

    void operator()(double num) {
        sum += num;
        window.push(num);
        if (window.size() > period) {
            sum -= window.front();
            window.pop();
        }
        out.push_back(sum / window.size());
    }

…

    vector<double> out;
    out.reserve(size);
    for_each(indata, indata + size, MovingAverage(out, 5));

Portah Feb 2 2012 at 20:37

Я начал писать статьи в разделе habrahabr.ru/blogs/bioinformatics/, в последней статье понял, что многие алгоритмы описаны на хабре, но с ходу я не знаю подходящий он или нет.

Хочу просить помощи. В этой статье habrahabr.ru/blogs/bioinformatics/137453/ приведены графики, частично похожие на приведеные здесь. Можно ли представленный тут алгоритм, или может существует другой, повернуть так, чтобы он правильно идентефицировал тип графика? Типа острые пики, пологие пики, «забор»?

UFO just landed and posted this here

Show the best of all time