"라이브"스트림의 간단한 이동 평균 - 빠른 구현

Question

내 거래 신청에는 주가가 "라이브 틱"합니다. 나는 SMA를 유지할 필요가있다. 나는 SMA가 20 개의 양초 (각 양초의 지속 시간은 10 초)를 원한다고 가정합시다.

1. 내가 "닫기"현재의 촛불과 마지막 10 초 동안 평균 가격을 저장 :이

   10 초마다 나는 여기서 "체크 포인트"를 가지고 있다는 것을 의미한다. 평균은 (최대 - 최소)/2

2. "시작"새 촛불을 시작하고 마지막으로 가격을 저장하십시오.
3. "오래된"촛불을 정리합니다.

모든 틱 :

1. 나는 현재의 "형성"촛불의 "마지막"가격을 업데이트하고 SMA를 다시 계산.

따라서 어떤 틱에서도 SMA를 "다시 계산"해야합니다. 대부분의 경우 마지막 촛불의 가격 만 변경됩니다 (마지막으로 가격 사용). 10 초에 한 번 조금 더 추가 작업이 필요합니다. 나는 오래된 촛불의 평균을 잊어 버리고 "방금 만든 촛불"의 평균을 "저장"해야합니다.

지연을 최소화하면서 구현하는 방법을 제안 할 수 있습니까? 낮은 대기 시간이 가장 중요합니다.

Answer 1

나는이 접근이인지 확실하지 않다 찾고 있지만 여기는 매우 빠른 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-일이 아니다 : 위에서 언급 한 바와 같이, 괜찮은 대안입니다 .마지막 N 일 동안 ~ 87 %의 가중치를 갖는 가중 이동 평균이므로 N 일이 거의 비슷합니다. 컴파일러 최적화에

참고 :

여러 계산은 하나의 CPU 사이클에서 휘저어 될 수 SSE 또는 AVX 옵션을 켜면 사용할 수 이러한 알고리즘의 엄청난 속도 향상을 가능하게 할 것이다 경우주의 마십시오.

Answer 2

그래서 고정 된 크기의 대기열이 필요합니다. 새 항목을 효율적으로 추가하고 가장 오래된 항목을 제거하여 (누적 합계에서 제거). 왜 안돼 std::queue?

이것은 다양한 컨테이너 위에있을 수 있지만 실제로는 20 개의 요소 만 있으면 vector이 잘 수행 될 것으로 생각됩니다. (항목을 제거하면 다른 모든 항목을 하나씩 아래로 이동해야하지만 연속적으로 움직이는 메모리 블록은 빠릅니다.) 성능을 양면 큐 또는 목록과 비교할 수 있습니다.

(? 대답은 각 "촛불"를 저장 무엇에 따라 달라질 수 있습니다 - 단 하나의 플로트/더블/INT, 또는 더 복잡한 구조)

Answer 3

내 구현. .H :

#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; 
     } 
    } 
}