平均の計算をループを使わずに処理時間を短縮する

2021年3月1日Delphi,Programing,アルゴリズム,数学

タイトル通りです。
簡単に平均値の計算をする場合、大体はこんな感じの関数を使うことになるでしょう。

function Average(data : array
of
Double):Double;
var
I : Integer;
begin
Result := 0;
for I := 0
to
Length(data) -1
do
begin
Result  := Result + data[I];
end;
Result := Result / Length(data);
end;

基本的には、データ要素数分のループ処理が必要になります。
ただ、これは要素数が増えたりなんだりで当然計算回数が増えることになるので
数が多くなればなるほど負荷がかかります。
そこで、ループを使わずに平均値を出していきます。

Contents

1. 考え方
2. Delphiでの実装
3. 移動平均を考える

考え方

上記の処理は、式にして考えるとこうなります。
$\displaystyle \bar{x}_{n} = \frac{\displaystyle\sum_{n=1}^\infty x_{n}}{n}$
nの時点での平均値 $\bar{x}_{n}$ は $x_{1}$ ～ $x_{n}$ までの総和を、要素数nで割ったもの。
となります。

ここで、n+1の時を考えると、 $x_{1}$ ～ $x_{n+1}$ までの総和が必要になりますが、
過去の平均値である $\bar{x}$ がわかっている場合、 $\bar{x}_{n}×n$ が $x_{1}～x_{n}$ までの総和と等しくなるはずです。

これをふまえると
$\displaystyle \bar{x}_{n+1} = \frac{\bar{x}_{n}×n+x_{n+1}}{n+1}$
という計算でも平均値を計算することができます。

つまり、要素一つ前の平均値と、新しいデータ、ここまでの要素数がわかれば
ループを使わずとも平均値を求めることができます。
これの利点としては、当然計算回数が削減できるだけでなく、長々と配列を用意する必要もないという点です。

Delphiでの実装

type
//  ループを使用しない加算平均値算出クラス
TTscAverage = class(TObject)
private
FAverage    : Double;
FCount      : UInt32;
function GetAverageData:Double;
public
constructor Create;virtual;
procedure Clear;
procedure SetData(data:Double);overload;virtual;
procedure SetData(data:Array
of
Double);overload;virtual;
procedure GetAverage(data:Double ; var avg : Double);overload;
function GetAverage(data:Double):Double;overload;
property TotalCount : UInt32 read FCount;
property Average    : Double
read GetAverageData;
end;
implementation
constructor TTscAverage.Create;
begin
Clear;
end;
procedure TTscAverage.Clear;
begin
//  変数の初期化
TspVarInitDouble([@FAverage]);
TspVarInitUInt16([@FCount]);
end;
procedure TTscAverage.SetData(data:Double);
begin
FAverage  := ((Faverage * FCount) + data) / (FCount +1);
Inc(FCount);
end;
procedure TTscAverage.SetData(data:array
of
Double);
var
I: Integer;
begin
for I := 0
to
Length(data) -1
do SetData(data[I]);
end;
procedure TTscAverage.GetAverage(data:Double; var avg:Double);
begin
avg := GetAverage(data);
end;
function TTscAverage.GetAverage(data:Double):Double;
begin
SetData(data);
Result    := FAverage;
end;
function TTscAverage.GetAverageData:Double;
begin
Result  := FAverage;
end;

と、こんな具合です。

移動平均を考える

今まで考えてきたのは単純な加算平均ですが、移動平均でもこの考え方は使えます。
移動平均の場合は、一番古いデータを引く事が必要になるので、データを保持しておく配列は必要になります。
データ $x(n)$ で要素数m個の移動平均、 $SMA(x,m)$ は
$\displaystyle SMA(x,m)_{n+1}=\frac{SMA(x,m)_{n}×m+x_{n+1}-x_{n-m}}{m}$
となります。

これを前術の平均値算出クラスを継承して書くと

type
TTscMovingAverage = class(TTscAverage)
private
FBuffer : Array
of
Double;
FSamples: UInt16;
procedure SetSamples(samples:UInt16);
public
constructor Create(samples : UInt16);reintroduce;
procedure SetData(data : Double);override;
property Samples  : UInt16 read FSamples write SetSamples;
end;
implementation
constructor TTscMovingAverage.Create(samples:UInt16);
begin
SetSamples(samples);
inherited Create;
end;
procedure TTscMovingAverage.SetData(data:Double);
begin
if FCount >= FSamples then
begin
FAverage  := ((FAverage * FSamples) +data -FBuffer[FCount mod FSamples]) / FSamples;
end
else
begin
FAverage  := ((FAverage * FCount) +data) / (FCount+1);
end;
FBuffer[FCount mod FSamples]  := data;
Inc(FCount);
end;
procedure TTscMovingAverage.SetSamples(samples:UInt16);
begin
SetLength(FBuffer, samples);
FSamples  := samples;
Clear;
end;