13

信号の移動平均を計算しようとしています。シグナル値 ( a double ) はランダムなタイミングで更新されます。時間枠での時間加重平均をリアルタイムで計算する効率的な方法を探しています。自分でもできますが、思ったより難しいです。

私がインターネット上で見つけたリソースのほとんどは、定期的なシグナルの移動平均を計算していますが、私の更新はランダムな時間です。

そのための良いリソースを知っている人はいますか?

ありがとう

4

4 に答える 4

8

秘訣は次のとおりです。を介してランダムな時間に更新を取得しますvoid update(int time, float value)。ただし、更新が時間枠から外れる時期も追跡する必要があるため、「アラーム」を設定します。このアラームtime + Nは、以前の更新が計算で再度考慮されないようにするために呼び出されます。

これがリアルタイムで発生する場合は、オペレーティングシステムに、で呼び出されるメソッドvoid drop_off_oldest_update(int time)を呼び出すように要求できます。time + N

これがシミュレーションの場合、オペレーティングシステムからのヘルプは得られないため、手動で行う必要があります。シミュレーションでは、引数として指定された時間を使用してメソッドを呼び出します（これはリアルタイムとは相関しません）。ただし、合理的な仮定は、時間引数が増加するような呼び出しであることが保証されているということです。この場合、アラーム時間値のソートされたリストを維持する必要があり、それぞれupdateのread呼び出しについて、時間引数がアラームリストの先頭よりも大きいかどうかを確認します。アラーム関連の処理（最も古い更新を削除）を実行する方が優れていますが、ヘッドを取り外し、指定された時間より前のすべてのアラームが処理されるまで再度確認してください。次に、更新呼び出しを実行します。

これまでのところ、実際の計算で何をするかは明らかだと思いますが、念のため詳しく説明します。float read (int time)値を読み取るために使用するメソッドがあると思います。目標は、この呼び出しを可能な限り効率的にすることです。したがって、メソッドが呼び出されるたびに移動平均を計算するわけではありません。read代わりに、最後の更新または最後のアラームの時点での値を事前に計算し、最後の更新からの時間の経過を考慮して、この値をいくつかの浮動小数点演算で「微調整」します。（つまり、積み上げられたアラームのリストを処理することを除いて、一定数の操作）。

うまくいけば、これは明らかです-これは非常に単純なアルゴリズムであり、非常に効率的であるはずです。

さらなる最適化：残りの問題の1つは、時間枠内に多数の更新が発生した場合、読み取りも更新も行われない時間が長くなり、読み取りまたは更新が行われることです。この場合、上記のアルゴリズムは、低下している各更新の値を段階的に更新するには非効率的です。時間枠を超えた最後の更新のみを考慮しているため、これは必要ありません。したがって、古い更新をすべて効率的に削除する方法がある場合は、それが役立ちます。

これを行うには、アルゴリズムを変更して更新のバイナリ検索を実行し、時間枠の前に最新の更新を検索します。「ドロップ」する必要のある更新が比較的少ない場合は、ドロップされた更新ごとに値を段階的に更新できます。ただし、削除する必要のある更新が多数ある場合は、古い更新を削除した後、値を最初から再計算できます。

漸増計算に関する付録：最後の更新からの時間の経過を説明するために、いくつかの浮動小数点演算によってこの値を「微調整」するという文で、上記の漸増計算の意味を明確にする必要があります。初期の非漸増計算：

皮切りに

sum = 0; 
updates_in_window = /* set of all updates within window */; 
prior_update' = /* most recent update prior to window with timestamp tweaked to window beginning */; 
relevant_updates = /* union of prior_update' and updates_in_window */,

relevant_updates次に、時間の昇順で 繰り返します。

for each update EXCEPT last { 
    sum += update.value * time_to_next_update; 
},

そして最後に

moving_average = (sum + last_update * time_since_last_update) / window_length;。

ここで、1つの更新がウィンドウから外れたが、新しい更新が到着しない場合は、次のように調整sumします。 

sum -= prior_update'.value * time_to_next_update + first_update_in_last_window.value * time_from_first_update_to_new_window_beginning;

prior_update'（タイムスタンプが最後のウィンドウの開始の開始に変更されていることに注意してください）。また、1つの更新がウィンドウに表示されても、新しい更新が削除されない場合は、次のように調整sumします。

sum += previously_most_recent_update.value * corresponding_time_to_next_update.

当然のことながら、これは大まかなスケッチですが、平均を維持して、償却ベースで更新ごとにO（1）操作になるようにする方法を示していることを願っています。ただし、前の段落でさらに最適化されていることに注意してください。また、古い回答でほのめかされた安定性の問題にも注意してください。これは、浮動小数点エラーが、アプリケーションにとって重要な完全な計算の結果からの逸脱があるように、そのような増分操作の多数にわたって蓄積する可能性があることを意味します。

于 2011-12-15T18:24:16.340 に答える
3 
#include <map>
#include <iostream>

// Sample - the type of a single sample
// Date - the type of a time notation
// DateDiff - the type of difference of two Dates    
template <class Sample, class Date, class DateDiff = Date>
class TWMA {
private:
  typedef std::map<Date, Sample> qType;
  const DateDiff windowSize; // The time width of the sampling window
  qType samples; // A set of sample/date pairs
  Sample average; // The answer

public:

  // windowSize - The time width of the sampling window
  TWMA(const DateDiff& windowSize) : windowSize(windowSize), average(0) {}

  // Call this each time you receive a sample
  void
  Update(const Sample& sample, const Date& now) {
    // First throw away all old data
    Date then(now - windowSize);
    samples.erase(samples.begin(), samples.upper_bound(then));

    // Next add new data
    samples[now] = sample;

    // Compute average: note: this could move to Average(), depending upon
    // precise user requirements.
    Sample sum = Sample();
    for(typename qType::iterator it = samples.begin();
        it != samples.end();
        ++it) {
      DateDiff duration(it->first - then);
      sum += duration * it->second;
      then = it->first;
    }
    average = sum / windowSize;
  }

  // Call this when you need the answer.
  const Sample& Average() { return average; }

};

int main () {
  TWMA<double, int> samples(10);

  samples.Update(1, 1);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(1, 2);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(1, 3);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(10, 20);
  std::cout << samples.Average() << "\n"; // 10
  samples.Update(0, 25);
  std::cout << samples.Average() << "\n"; // 5
  samples.Update(0, 30);
  std::cout << samples.Average() << "\n"; // 0
}
于 2011-12-15T22:38:35.337 に答える
3

近似に問題がなく、サンプル間に最小の時間があれば、スーパーサンプリングを試すことができます。最小値よりも短い等間隔の時間間隔を表す配列を用意し、各時間間隔で受信した最新のサンプルを格納します。間隔が短いほど、平均値は真の値に近づきます。期間は最小値の半分を超えてはなりません。そうしないと、サンプルを見逃す可能性があります。

于 2011-12-15T18:12:50.983 に答える
0

注：どうやらこれはこれにアプローチする方法ではありません。このアプローチの何が問題になっているのかを参照するために、ここに残しておきます。コメントを確認してください。

更新-オリのコメントに基づいています...しかし、彼が話している不安定さについてはわかりません。

値に対して「到着時間」のソートされたマップを使用します。値が到着したら、その値とともに到着時間をソートされたマップに追加し、移動平均を更新します。

警告これは擬似コードです：

SortedMapType< int, double > timeValueMap;

void onArrival(double value)
{
    timeValueMap.insert( (int)time(NULL), value);
}

//for example this runs every 10 seconds and the moving window is 120 seconds long
void recalcRunningAverage()
{
    // you know that the oldest thing in the list is 
    // going to be 129.9999 seconds old
    int expireTime = (int)time(NULL) - 120;
    int removeFromTotal = 0;
    MapIterType i;
    for( i = timeValueMap.begin();
    (i->first < expireTime || i != end) ; ++i )
    {
    }

    // NOW REMOVE PAIRS TO LEFT OF i

    // Below needs to apply your time-weighting to the remaining values
    runningTotal = calculateRunningTotal(timeValueMap); 
    average = runningTotal/timeValueMap.size();
}

そこに...完全に肉付けされていませんが、あなたは考えを理解します。

注意事項：私が言ったように、上記は擬似コードです。適切なマップを選択する必要があります。イテレータが無効になり、最初からやり直す必要があるため、反復するときにペアを削除しないでください。
以下のOliのコメントも参照してください。

于 2011-12-15T12:22:35.067 に答える