algoritmust keresek - létezik-e - átlag számítás csak utolsó érték megtartásával

Algoritmusok

(Valószínűleg borzalmasan fogalmazok, terminológia szempontjából kövezzetek meg :) . )

Adott x db szám, és szeretnék egy átlagot (számtani közepet), anélkül, hogy tárolnom kellene az adatgyűjtés végéig az összes számot. Kevés matematikai tudásom alapján megoldhatónak tűnt, rosszul megfogalmazva: csak az átlagot tárolom, és az új adattal annak számolom ki az átlagát, és azt tárolom tovább. Így mindig csak egy számot kell tárolnom.

Próbáltam gyorsan egy egyszerű tesztet csinálni, lehet az jobban érthető egyeseknek, összehasonlítottam a két algoritmust, nem ugyan az az eredmény jön ki, de egymáshoz "nagyjából" közeli.

Kérdések: van-e ilyen algoritmus, és jó irányba próbálkoztam?

- - - - -

$nums = array();

for ($i = 0; $i < 100; $i++){
    $nums[] = rand(0,1000);
}

$sum = 0;
foreach ($nums as $num){
    $sum += $num;
}
$avg = $sum / count($nums);
unset($sum);
var_dump($avg);
unset($avg);

$first = 1;
foreach ($nums as $num){
    if ($first){
        $avg = $num;
        $first = 0;
    } else {
        $avg = ( $avg + $num ) / 2 ;
    }
}
var_dump($avg);

( persicsb | 2021. 04. 26., h – 13:19 )

Amit te keresel, az a futóátlag.
Van vele probléma a lebegőpontos számítás korlátai miatt.

De az a lényege, hogy:
- tárolod, hogy hány mért érteket láttál eddig

- mi ezeknek az összege

Amikor bejön egy új érték, akkor a countert megnöveled, és az összeget is. Az átlag természetesen összeg / mért értékek száma.

Hülye voltam, ez is elég elegáns megoldás, összeget és darabszámot tárolni. Egyébként addig eljutottam, hogy valószínűleg kerekítési hibák lehetnek, a lebegőpontosság miatt, kb. mire leírtad lett egy gyanum, nem hiszem, hogy feloldható lesz általam :). De amit írsz megoldást tökéletesnek tűnik, kicsit memória igényesebb a szumma miatt, de egye fene.

Ha nem válaszolnék kommentben, hát küldj privátot!

Nem. Amit te írsz, az a futóátlag. Amit ő keres, azt mozgóátlagnak hívják tudtommal, bár lehet nem emlékszek rá pontosan, vagy nem ez a magyar neve. Természetesen a futóátlag jobb megoldás, pontosabb átlagot ad. De mindkettő elég egyszerűen kivitelezhető.

“A computer is like air conditioning – it becomes useless when you open Windows.” (Linus Torvalds)

( gelei v | 2021. 04. 26., h – 13:20 )

Szerintem nem elég az átlagot letárolni, kell az is, hogy eddig hány inputod volt. Ha mondjuk 1000 érték átlaga 5, és a következő input 10, akkor nem igaz, hogy az új átlag 7,5. 

Most így hirtelen, ha van n számod, aminek az átlaga k, akkor a következő x input után az új átlag = (n*k+x)/(n+1)

( Nyosigomboc v | 2021. 04. 26., h – 13:23 )

Az osszeget es a darabszamot nyilvantartod. Ha uj szam jon, az osszeget noveled vele, a darabszamot inkrementalod, es az uj atlag a ketto hanyadosa (osszeg/darabszam). Arra persze figyelni kell, hogy az osszeget eleg nagy szamkent abrazoljuk.

Amugy ha ilyesmi feladat van, altalaban ablakos csuszoatlag kell nekem, es egy sima alulatereszto szurovel szoktam megoldani. Az uj ertek az elozo ertek es az uj szam valamilyen sulyozott szamtani kozepe. (pl. potmetert teker a felhasznalo, de zajos a jel) Igy eleg az aktualis erteket szamontartani.

import math

#based on code and maths from here: https://en.wikipedia.org/wiki/Low-pass_filter

def get_alpha(sampling_freq,filter_freq):
  """Calculates an alpha value for a low pass filter.
  sampling_freq and filter_freq are given in Hz
  """
  delta_t=1.0/sampling_freq
  temp=2.0*math.pi*delta_t*filter_freq
  alpha=temp/(temp+1)
  return alpha
  
def get_filter_freq(sampling_freq,alpha):
  return (sampling_freq*alpha)/(2*math.pi*(1-alpha))
  
def low_pass_filter(alpha,value,prev_value):
  return alpha*value+(1-alpha)*prev_value

A strange game. The only winning move is not to play. How about a nice game of chess?

A mozgóátlag meg a futóátlag nem ugyanaz, erre figyeljünk oda!

A mozgóátlag esetén az átlag alapjául szolgáló sokaság folyamatosan változik úgy, hogy kerülnek belüle ki is elemek.

A futóátlag pedig egy minimalizált memóriahasználatú átlagszámítás a teljes addig megfigyelt sokaságra.

( pink v | 2021. 04. 26., h – 17:53 )

Az átlag tulajdonképpen összeg. Csak le van normálva a minták számával.
Én úgy szoktam, hogy összegzem az eddigi adatokat és az adatok számát (sum és n), és amikor épp kell az átlag, elosztom.
Túlcsordulás az egyetlen ellenséged, de ma, a sokbites korban nekem ez a viszonylag kicsi számokkal nem akkora gond.

Ja de én direkt az összeget tárolom, mert így nem szenvedek mindig kerekítési pontatlanságot.
Nem annyi és nem olyan nagy számot szoktam átlagolni, hogy a túlcsordulás veszélye fennálljon.
Valamint az átlagra nem is minden minta után van szükségem. Így egy csomó számolást megspórolok. Nincs szorzás és osztás, csak összeadás egy normál mintaérkezéskor.

( locsemege v | 2021. 04. 27., k – 11:40 )

Látom, már mindenki mindent leírt, de ha valamiféle aluláteresztő szűrés a cél, ahol a régebbi értékek súlya azoktól távolodva exponenciálisan csökken, s a legfrissebb értékek súlya relatív nagyobb, akkor semmiképp sem feledkeznék meg az exponenciális átlagolásról. :)

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

A mozgóablakos átlagolás is aluláteresztő szűrés.
Egyébként jól mondod, helye van itt megemlíteni az exponenciális átlagolást is.

Fel kell hívni a figyelmet viszont arra, hogy a mozgó ablakos és a kumulálódó átlagolások között különbség van, nem ugyanarra jók.

A kumulálódónál a modell konstans várható értéket feltételez, azaz DC jelet (nyilván zajjal terhelve).
A mozgó ablakos átlagolásoknál pedig egy ,,lassan változó", zajjal terhelt jelet feltételez a modell.

Hát ja, meg amire futásidőd van. Mert ha ömlik be DMA-n az A/D konverterről a mintavételezett adat, s röptében kell ezzel valamit kezdeni, akkor az exponenciális átlagolás törésponti frekvenciája is abból adódik ki, ami nagyjából épp megfelel, és össze tudod rakni egy shiftelésből, összeadásból, meg egy 3-mal való osztásból az egészet. Tapasztalat. :)

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Persze. Az exponenciálist is nyilván ablakozod. Mikrokontrollerben én is ad-hoc módon valósítom meg ezeket, ahogyan kiadja. Célnak általában megfelel; a szellemiség a lényeg. Ööö akarom mondani a jelmodell.

Vannak speciális esetek, amikor jön az adat, de nem mindig van szükséged az átlagra, csak egyszer-egyszer. Azt is megoldom sima összegzéssel és mintaszámolással, hogy ne kelljen gyakran szorozni-osztani.
Adott n értékenként pedig le lehet kumulálni, amit utána egy súllyal veszek figyelembe (általában az addigi n, vagy ha feledtetni akarom a múltat, akkor <n).

A kumulálódónál a modell konstans várható értéket feltételez, azaz DC jelet (nyilván zajjal terhelve).

Most veszem észre, mit írtál, és egy pillanatig még el is hittem neked! :) Az exponenciális szűrő sima egytárolós tag, tehát a Laplace-transzformáltja valami 1/(1 + sT), ha jól gondolom. Szóval leköveti az a lassú változásokat törésponti frekvenci alatt. A gyorsakra meg csillapít -20 dB/dekáddal töréspont fölött.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Akkor egyetértünk. Ebben van a nagyszerűsége. Nem kell ablakozni, a múlt exponenciálisan, aszimptotikusan enyészik nullává. Ráadásul a számábrázolás miatt idővel - na jó, mintával - tényleg teljesen el fog tűnni a múlt.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

( locsemege v | 2021. 04. 27., k – 12:09 )

Most látom, az, amit itt php-ban írtál, az épp exponenciális átlagolás. Lehet azért ezt egy picikét lassítani is, pl:

$avg = ( 2 * $avg + $num ) / 3 ;

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE