C++ 부스트를 위해 최소 및 최대 롤링?

Question

나는 롤링 윈도우에서 평균을 추적하기 위해 부스트 누산기를 사용하는 코드를 가지고있다. "롤링 평균"이다. 롤링 평균 이외에,이 동일한 롤링 윈도우에서 최소 및 최대를 추적하고 싶습니다.

부스트 누산기로 롤링 최소 및 롤링 최대를 계산하는 방법이 있습니까? 나는 방법을 보지 않고있다. ...

rolling_mean에 사용되는 누적기에 최소 및 최대 태그를 추가하려했지만, 원하는 것을 제공하지 못했다.

typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t; 

그러나

typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t; 

, 최소가되고 최대 전체에 걸쳐 누적 계산보다는 평균 같은 롤링 윈도우로 제한된다 여기서 제공.

부스트 documentation은 최소 및 최대가 모두 개의 샘플을 통해 계산되며 롤링 창에 국한되지 않는다고 말합니다. 그들은 샘플을 제한하거나 가중시키는 방법을 제공하지 않는 것 같습니다.

롤링 윈도우에서 평균/최소/최대를 모두보고하고 싶습니다.

현재 Boost 버전 1.48.0을 사용 중입니다. 나는 최신 버전 (1.54.0)에 대한 문서를 보았으며 거기에 구현 된 최소/최대 롤링을 보지 못했다.

sliding window minimum을 추적 할 부스트가 아닌 방법을 찾았지만, 원하는대로 표시되지 않습니다. 값이 이전/최소값보다 크거나 작기 때문에 값을 제거하고 싶지 않습니다. rolling_mean을 부정확하게 만들 수 있습니다.

Answer 1

누적 기가 최소/최대 롤링을 수행 할 수 있다고는 생각하지 않습니다.

문제는 꽤 간단합니다. 정의에 따르면 거의 축약기는 O (1) 데이터 만 사용합니다. 처리중인 데이터를 저장하지 않습니다. 숫자가 현재 최소/최대 범위를 벗어날 경우 현재 최소/최대 값을 변경하기 때문에 O (1) 데이터로 최소 또는 최대 값을 유지할 수 있습니다.

그러나 현재의 분이 창 밖으로 나올 때 새로운 최소값 (창에서 다음으로 작은 숫자)을 찾아야합니다. 물론 최대한으로.

이제는 입력이 정렬되는 경우 어떻게되는지 최소한으로 생각하십시오. 항목이 창에서 제거 될 때마다 우리는 다른 최소값을 얻습니다. 다시 말해 누적 기는 현재 최소값을 올바르게 유지하기 위해 창에 모든 데이터를 저장해야합니다. 마찬가지로, 입력이 최대 인 경우 내림차순으로 정렬됩니다.

간단히 말해서 축전기를 사용할 수 없습니다. 모든 데이터를 창에 저장해야합니다.

Answer 2

더 똑똑한 알고리즘이있을 수도 있지만 (사실 실제로있을 수 있습니다.) 머리 꼭대기에서 원형 버퍼에 창을 저장하고 필요할 때마다 최소/최대 크기를 계산합니다. 창을 변경하면 결과를 캐시하고 더티 플래그를 설정하십시오. 이것은 O (1) 누적 연산과 O (K)의 최악의 경우를 가진 amortized O (1) 추출 연산을 제공합니다. 여기서 K는 윈도우의 크기입니다.