простое скользящее среднее от «живого» поток — быстрая реализация

Question

простое скользящее среднее от «живого» поток — быстрая реализация

В моем торговом приложении у меня есть «живые тики» котировок акций. Мне нужно поддерживать SMA. Давайте предположим, что я хочу SMA 20 свечей, где продолжительность каждой свечи составляет 10 секунд. Это означает, что

Каждые 10 секунд у меня есть «контрольно-пропускной пункт», где:

Я «закрываю» текущую свечу и сохраняю средний цена за последние 10 секунд. Среднее значение (максимум — мин) / 2
Я «запускаю» новую свечу и храню прошлой цена.
Я убираю «устаревшую» свечу.

Каждый тик:

Я обновляю «последнюю» цену текущей «формирующейся» свечи и пересчитываю SMA.

Так что на любой галочке мне нужно «пересчитать» SMA. В большинстве случаев меняется только цена последней свечи (потому что мы используем прошлой цена). Раз в 10 секунд мне нужно немного больше дополнительной работы — мне нужно «забыть» среднее значение устаревшей свечи и «сохранить» среднее значение «только что созданной» свечи.

Можете ли вы предложить, как реализовать это с минимальной задержкой? Низкая задержка является основным требованием.

2

algorithmic-trading c++

Решение

Другие решения

Таким образом, вам нужна очередь, в значительной степени фиксированного размера, где вы можете эффективно добавлять новые элементы и удалять самый старый элемент (чтобы удалить его из промежуточного итога). Почему бы и нет std::queue?

Это может сидеть на разных контейнерах, но если у вас действительно есть только 20 элементов, я подозреваю, vector будет хорошо работать (Для удаления элемента необходимо переместить все остальные элементы на единицу, но перемещение смежных блоков памяти происходит быстро.) Однако вы можете сравнить производительность с декой или списком.

(Ответ может зависеть от того, что вы храните для каждой «свечи» — просто один float / double / int или более сложная структура?)

0

Моя реализация.
.час:

#pragma once

#include <deque>

class MovingAverage
{
public:
MovingAverage(int length);
~MovingAverage(void);
void Add(double val);
void Modify(double value);
double Value;
std::deque<double> _candlesExceptNewest;
private:
MovingAverage(MovingAverage& rhs):
_length(rhs._length)
{
printf("MovingAverage copy-constructor mustn't be executed, exiting.");
exit(0);
}

const int _length;

int addCounter;
static const int RECALCULATE_VALUE_MASK;

double _sumExceptNewest;

double NewestCandleMedian() {
return (_newestCandleMin + _newestCandleMax) / 2;
}
void RecalculateValue();
double _newestCandleMin;
double _newestCandleMax;
};

.каст:

#include "MovingAverage.h"#include "CommonsNative.h"
const int MovingAverage::RECALCULATE_VALUE_MASK = 1024 - 1;

MovingAverage::MovingAverage(int length):
Value(quiet_NaN),
_length(length),
addCounter(0)
{
if (length < 20) {
std::cout << "Warning, MA is very short, less than 20! length = "<< length << std::endl;
}
}

MovingAverage::~MovingAverage(void)
{
}

void MovingAverage::Add(double val)
{
++addCounter;
if (addCounter & RECALCULATE_VALUE_MASK) {
_sumExceptNewest = 0;
for (double val : _candlesExceptNewest)
{
_sumExceptNewest += val;
}
}

auto curQueueSize = _candlesExceptNewest.size();
if (curQueueSize == 0) {
_newestCandleMax = _newestCandleMin = val;
}
_sumExceptNewest += NewestCandleMedian();
_candlesExceptNewest.push_back(NewestCandleMedian());
if (curQueueSize == _length) {
_sumExceptNewest -= _candlesExceptNewest.front();
_candlesExceptNewest.pop_front();
}
_newestCandleMax = _newestCandleMin = val;
RecalculateValue();
}

void MovingAverage::RecalculateValue()
{
Value = (_sumExceptNewest + NewestCandleMedian())/(_candlesExceptNewest.size() + 1);
}

void MovingAverage::Modify(double val)
{
if (_candlesExceptNewest.size() == 0) {
Add(val);
} else {
if (val > _newestCandleMax) {
_newestCandleMax = val;
}
if (val < _newestCandleMin) {
_newestCandleMin = val;
}
}
}

0

Источник

Accepted Answer

Я не уверен, что это подход, который вы ищете, но вот псевдокод для очень быстрых SMA.

Простая скользящая средняя:

Я предполагаю, что ваши данные поступают в виде некоторого потока и хранятся в непрерывной ячейке памяти (по крайней мере, с непрерывно отображаемыми адресами)

x[1] to x[2000] contain the first 2000 data points

// they don't have to be a real array, could just be a function which manages
// a 'circular' array and maps the 'locations' to real locations in memory.
// Either case, it's small enough to be fully in the cache hopefully
//
// Subsequent prices will be accessible in 'locations x[2001], etc.
// Here we are looking to calculate the MA over the latest 2000 ticks

MA2000(1,2000) = (x[1] + x[2] + ... + x[2000]) / 2000 // Usual average
// Done only once

MA2000(2,2001) = MA2000(1,2000) * 2000 + x[2001] - x[1]
MA2000(2,2001) /= 2000

Таким образом, с двумя сложениями и одним умножением (с 1/2000) вы можете генерировать последующие скользящие средние для новых тиков.

Экспоненциальная скользящая средняя:
Это достойная альтернатива, как упоминалось выше:

// For an N-day EMA
Alpha = 2 / (N+1)      // one time calculation

EMA(new) = Alpha * NewTickPrice + (1-Alpha) * EMA(old)

Здесь это не совсем N-дневная скользящая средняя. Это просто взвешенная скользящая средняя с ~ 87% веса за последние N дней, так что почти N дней больше похоже на это.

Примечание по оптимизации компилятора:

Обратите внимание, что включение опций SSE или AVX, если они доступны, приведет к значительному ускорению этих алгоритмов, поскольку в одном цикле ЦП может выполняться несколько вычислений.

3