Комментарии 23
Можно ли избавиться от проблемы номер два? Пишите ваши предложения в комментариях.
Кольцевой буфер же.
Вы правы, но не совсем. Текущая реализация это и есть кольцевой буффер. Вопрос в том, как сделать ее быстрее, а именно без использования shift операции. Либо же вообще отказаться от такого подхода и каким-то другим образом хранить числа для атомарных перерасчетов суммы.
Текущая реализация это и есть кольцевой буффер.
Нет. В кольцевом буфере не делается shift/push, а двигается указатель.
Указатель в массиве на 0й элемент вы имеете в виду? Если нет, приведите пример реализации абстрактно или на JS
Указатель в массиве на 0й элемент вы имеете в виду?
Да.
Это один из хороших вариантов решения проблемы. Спасибо. И как и любой "ускоряющий" механизм, дает нагрузку на память. (К сожалению не смог найти картинку где диаграммами показано что увеличение производительности чаще всего приводит к увеличению потребляемой памяти)
И как и любой "ускоряющий" механизм, дает нагрузку на память.
В каком месте, если у вас всегда выделено одно и то же количество памяти, и вам ничего не надо (де)аллоцировать?
Он, наоборот, требует одной-двух "лишних" операций (сложение по модулю), но на фоне операций с выделением памяти это обычно мелочи по стоимости.
На JS нельзя сдвинуть указатель на первый элемент массива напрямую, придется записывать в массив все поступающие значения и отдельно хранить индекс "начала" и сдвигать его при добавлении элемента. Получается в памяти будут вообще все данные.
А написание структуры, которая отличается от стандартного массива и реализует какую-то более продвинутую логику, сопряжено с использованием `new` оператора, что убьет производительность.
В классическом кольцевом буфере сдвигают не данные а индекс последнего элемента. При этом данные никуда не сшифтятся. Новый элемент кладётся на место изгнанного.
Мне кажется, вы немного не понимаете, как работает кольцевой буфер. Рассмотрим пример размером 4, последние записанные элементы 18, 22, 64, 3. Мы где-то в середине работы, буфер давно и прочно заполнен (это чтобы не рассматривать edge case в начале).
buf = int[4];
...
// buf = [64, 3, 18, 22]
i = 1; //последний добавленный элемент был 3
//добавляем новый элемент, 100
i = (i + 1) mod 4;
buf[i] = 100
// buf = [64, 3, 100, 22]
//добавляем новый элемент, 200
i = (i + 1) mod 4;
buf[i] = 200
// buf = [64, 3, 100, 200]
//добавляем новый элемент, 300
i = (i + 1) mod 4;
buf[i] = 300
// buf = [300, 3, 100, 200]
Никаких выделений памяти.
А как вы решаете проблему накопления ошибки машинной точности?
Не было цели определить погрешность, да и данные, с которыми работает алгоритм, не имеют большой точности вычислений, ограничиваются двумя тремя разрядами после запятой. Так что влияние погрешностей крайне мало.
Достаточно хранить сумму, перебирать массив, в каждой итерации к хранимой сумме прибавлять текущий элемент data[i] и вычитать из нее элемент data[i-period].
Данные заранее не известны. И не хранятся вообще нигде. Вся суть поточных вычислений в том, что данные обрабатываются при поступлении. Каждое входное значение имеет собственную временную метку. Для избежания ошибок «заглядывание в будущее» вычисления строго выполняются только для текущего момента времени, или условно текущего если это симуляция. Таким образом, учитывая особенности скользящего среднего, о которых говорит выше @fivehouse
Нет, постойте, кто-то реально городит тут ужас, что у вас описан в "классический подход"?
Если все и так в массиве, то нафига slice, если совершенно очевидно, что можно просто вычесть элемент, выходящий из окна и добавить элемент входящий? Никаких аллокаций памяти и во много раз меньше арифметических действий.
Потом, если нужна потоковая обработка, то используется кольцевой буфер вместо shift и push. Это же элементарная вещь, которая должна сразу же приходить в голову, если хоть раз в жизни читалась хоть какая-то книжка по этим самым "никому не нужным" алгоритмам.
Кольцевой буфер — это массив длинной с окно, который заполняется по кругу. Каждый раз, когда вы записиываете новое число, вы старое вычитаете из суммы, а новое прибавляете.
Но у этого быстрого метода есть один подводный камень. Из-за постоянных прибавлений и вычитаний может накапливатся ошибка, если используются числа с плавающей точкой.
Чтобы это исправить — надо параллельно с заполнением окна считать заново его сумму. Когда указатель перескакивает в начало кольцевого буфера надо переписать аккумулятор подсчитанной суммой всего окна.
(не пишу на js, вот код на С++. Переписывается в потоковую обработку элементарно.)
std::vector<double> MovingAverage(const std::vector<double> &values, int window)
std::vector<double> answer;
std::vector<double> array(window); // циклический буфер, инициализированный нулями.
int cur = 0;
double window_sum = 0.0;
double acc_sum = 0.0;
for (auto value in values) {
acc_sum += value;
acc_sum -= array[cur];
array[cur] = value;
window_sum += value;
cur++;
if (cur == window) {
cur = 0;
acc_sum = window_sum;
window_sum = 0.0;
}
answer.push_back(acc_sum / window);
}
return answer;
}Метод ровно один раз выделяет память размером с окно и, независимо от длины окна всегда выполняет константное количество действий для каждого входного элемента.
Быстрая математика для графиков, на примере вычисления среднего