0

整数を移動するための効率的なアルゴリズムを作成する必要があります。

たとえば、平均 100 アイテム。したがって、100 個の数字が来ると、1..100 個の数字の平均..

私は1つの解決策を考えましたが、最小数を保存できるようにすることはできません(病棟の後、マイクロプロセッサで行う必要がありますが、最初にC/C++で効率的です):

ステップ 1: 1..100 の数値を保存し、平均を取る ステップ 2: 1 を 101 に置き換え、平均をとる: 101,2,3...100 ステップ 3: 2 を 102 に置き換え、平均を取る: 101,102,3, 4...100

しかし、少ない除算演算子も使用する必要があるため、効率的ではありません。

誰でも私を助けてください。

4

2 に答える 2

2

あなたの基本的なアプローチは良いです: 100 個の要素を持つ循環バッファーを使用します。重要な洞察: 「2 を 102 で置き換える」段階にあるとします。2 は 50 で、102 は 70 です。合計は +20 の差で変わります。新しい合計を 100 で割るだけで、新しい合計が得られます。すべての要素を再度追加せずに平均します。

除算が非常に遅く、全体的なパフォーマンスに重大で問題のある違いをもたらす可能性はほとんどありませんが、試すことができることはいくつかあります(ただし、測定してください - 正確なハードウェアによっては、実際には速度が低下する可能性があります)。

  • 数値の範囲が小さい場合、値から値の 100 分の 1 までのルックアップ テーブル (つまり、配列) を作成し、これらのスケーリングされた値を合計に追加/削除することで、平均を直接維持できます。

  • float 型または double 型を使用してシステムが高速かどうかを確認します (直観に反して、一部のシステムはそうです)

  • http://embeddedgurus.com/stack-overflow/2009/06/division-of-integers-by-constants/(((((uint32_t)A * (uint32_t)0x47AF) >> 16U) + A) >> 1) >> 6からのように、「ネット上で 100 で除算するためのいくつかの奇妙な「レシピ」があります。

于 2013-07-08T02:16:55.610 に答える
1

移動平均を行う最も簡単な方法は、移動合計を使用することです。n[0] から n[99] までの数字を合計して開始します。平均は、この合計を 100 で割ったものです。次の合計については、n[0] を減算し、n[100] を加算します。もう一度100で割って平均。

合計に丸め誤差がないため、これは整数で最もうまく機能します。浮動小数点を使用すると、エラーが蓄積され、進むにつれて悪化します。

正の整数を使用している場合は、ウィンドウ サイズを 2 のべき乗にすることで除算をなくすことができます。

逆数を掛けて除算をなくすこともできます。100で割る代わりに、1/100を掛けます。整数を扱う場合は、固定小数点を使用する必要があるかもしれません。また、注意しないとビットが不足する可能性もあります。

于 2013-07-08T03:05:32.703 に答える