RunningMedian Lib

International Deutsch
#1

Hallo,
ich nutze die Lib RunningMedian. Im Grunde habe ich kapiert was dort geschieht
und kann es zum größten Teil auch nachvollziehen.

Wo ich überhaupt nicht mit klar komme, ist diese Zeile Code:

RunningMedian samplesTest = RunningMedian(24);

Hier wird dynamischer Speicher für das interne Array der Funktion freigehalten.
Diesen kann man in der o.g. Zeile festlegen- und auch das Maximum dafür in der
Lib vorgeben.

Wie wird dieser denn berechnet? In der Zeile steht "24", was ist das?
"int" braucht doch weniger Speicher als "float". Diese "24" muß man doch berechnen
können? Weiß jemand wie das geht?
Gruß und Dank
Andreas

#2

In RunningMedian.h findest Du

RunningMedian(const uint8_t size); // # elements in the internal buffer

Oder in RunningMedian.cpp:

RunningMedian::RunningMedian(const uint8_t size)

Also 8 Bit lang so wie byte.

#3

Hallo,
ich habe von der bit & byte Schieberei keine so große Ahnung. Wie darf ich das denn verstehen?

Ein int-Wert belegt 2 Bytes
Ein float-Wert belegt 4 Bytes

Bei 24-int-Werten müßte da dann RunningMedian(6) stehen?
Bei 24-float-Werten müßte da dann RunningMedian(12) stehen?

Oder habe ich da einen DenkFehler?
Gruß und Spaß
Andreas

#4

SkobyMobil:
Oder habe ich da einen DenkFehler?

Ja.

Ein byte-Wert belegt 1 Byte -> uint8_t
Ein int-Wert belegt 2 Bytes -> bei acht Bit µCs (ATmega328) stimmt das, nehmen wir mal an
Ein float-Wert belegt 4 Bytes

Beim Deklarieren eines Feldes wird die Anzahl der Feldelemente bestimmt, unabhängig vom benötigten Speicher.

byte meinFeldA[2];  // benötigt zwei Bytes Speicher
int meinFeldB[2];  // benötigt vier Bytes Speicher

Stolperfalle: "The sizeof operator returns the number of bytes in a variable type, or the number of bytes occupied by an array. " Für die Ermittlung der Anzahl der Feldelemente nutze ich:

uint16_t anzahlElemente = sizeof(meinFeld)/sizeof(meinFeld[0])  // Anzahl der Bytes des Feldes durch die Anzahl der Bytes des ersten Elementes

Das habe ich von jurs gelernt :slight_smile:

Den teensy 3.2 habe ich mir auch zugelegt, weil dort ein 32bit-µC werkelt. Eine Integer-Variable nimmt sich da gleich vier Bytes Speicher. Da muß man höllisch aufpassen, wenn man ein für den ATmega328 geschriebenes Programm auf dem teensy laufen lassen möchte.

#5

SkobyMobil:
Wie wird dieser denn berechnet? In der Zeile steht "24", was ist das?

Die 24 sind NICHT berechnet, sondern werden von Dir bei der Deklaration des Median-Objekts VORGEGEBEN!

Das ist die "Anzahl der Werte " (Number of samples), aus denen der Medianwert ermittelt werden soll.

Im Fall der Code Zeile "RunningMedian samplesTest = RunningMedian(24);" gibst Du also vor, dass ein Objekt mit dem Namen samplesTest verwendet werden soll, das einen Median aus 24 Werten ermitteln soll. Eigentlich gibt es das nicht, denn einen Medianwert gibt es streng genommen nur bei einer ungeraden Anzahl von Samples. Also aus 23 Samples oder 25 Samples gibt es einen Median, und bei 24 Samples hast Du ein Problem mit dem Median. Manchmal wird das Problem bei einer geraden Anzahl von Samples dadurch umgangen, dass in dem Fall der arithmetische Mittelwert aus den Nachbarwerten des nicht existierenden Medianwertes genommen wird. Wie Deine Median-Library das Problem der Medianwertermittlung bei einer geraden Anzahl von Samples angeht, weiß ich allerdings nicht, da ich diese Library nicht näher kenne.

#6

Hallo,
wie ich diesen Mist hasse, kann der Computer das nicht alleine regeln!? Kann doch sonst alles!
Ich muß mich da wirklich mal mit beschäftigen. Es geht manchmal wirklich nicht ohne.
Gruß und Dank
Andreas

#7

SkobyMobil:
… kann der Computer das nicht alleine regeln!?

Tut er doch! Er reserviert RAM, setzt einen Zeiger darauf, …

Dein Problem steckt wahrscheinlich woanders: Du kannst die Anzahl der Elemente festlegen, nicht aber den Typ, also anstelle float lieber int:

void RunningMedian::add(float value)

Wenn ich es richtig überflogen habe, ist float festgelegt.

Andreas daher also nicht auf den µC schimpfen, sondern auf Andreas, weil der die falsche Bibliothek ausgewählt hat. Also andere Bibliothek auswählen oder selber programmieren.

Ich würde es selbst machen wollen, weshalb ich keine Links zu passenden Bibliotheken habe. Im zweiten Fall könnte ich Unterstützung anbieten :slight_smile:

#8

Hallo jurs,
"Das ist die "Anzahl der Werte “”

Davon bin ich zuerst auch von ausgegangen. Dann habe ich das Ergebnis der Lib
einmal nachgerechnet- und habe etwas anderes rausbekommen.

Als ich mir die Lib dann angeschaut habe, spricht “der” von “size”- das ist für
mich in der EDV “Größe” und nicht- Anzahl.

Da ich nun unterschiedliche Ergebnisse hatte, dachte ich, ich frage hier mal.

So wie es aussieht, scheint es Anzahl zu sein, denn bei 15 float-Werten wird
noch richtig gerechnet.
Einen Rechenfehler habe ich gefunden, der läuft bei “25” nicht über- sondern
überschreibt in “0”- und verrechnet dann 0 bis 24. 1 bis 23 werden nicht
gelöscht. “24” könnte also Anzahl sein.

“Wie Deine Median-Library…das angeht”
So wie Du den Median erklärst kenne ich ihn auch. Ungrade ist es die Mitte,
gerade, das Mittel der Nachbarn.
Ich wollte den nutzen, um Ausreißer im Mittelwert zu eleminieren. Denn wenn
Median und Mittelwert zu weit auseinander liegen, dann gibt es diese.

So richtig will mir das mit der Lib aber noch nicht gefallen. Ich hatte es ja
schon probiert. Aber- ich habe ein Array-A mit “durcheinander-Werten”. Diese
Werte müssen in ein Array-B mit sortierten-Werten.

Gleich sortiert in Array-A schreiben geht nicht, ich nutze den Index als Std,
Index = 5, = 05:00h- so spare ich mir ZeitStempel und in Diagrammen berechnete
Zeitachsen. Also wie sortieren?

Das zweite der Median selbst, da müßte ich im Rechen-Duden mal nachschlagen
wie genau der definiert ist- und was ich will. Beispiel:

15 Messungen

19,0
17,9
17,3
17,0
16,7
16,4
16,2
15,9
16,0
17,2
20,3
21,4
21,6
22,3

sortiert

15,9
16,0
16,2
16,4
16,7
17,0
17,2
17,3
17,9
19,0
20,3
21,4
21,6
22,0
22,3

Median = 17,3
Mittel = 18,5

gleiche Werte 29 Messungen

0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
15,9
16,0
16,2
16,4
16,7
17,0
17,2
17,3
17,9
19,0
20,3
21,4
21,6
22,0
22,3
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0

Excel Median = 15,9
Mittel 9,6

Mein Median = 22,3 15,9

So lange kein “0”-Wert mit ins Spiel kommt, “kein” Problem.
Da muß es also ganz bestimmte Regeln geben, denn das Ergebnis muß ja
reproduzierbar und nachzuvollziehen sein. Es ist nicht so einfach, wie Anfangs
von mir gedacht.
Gruß und Spaß
Andreas

#9

Die 29 Werte hast Du nicht sortiert. Mit Sortierung ist der 15. Wert 15,9 :slight_smile:

#10

Hallo,
warum nicht? Stören Dich Nullen am Ende? Mich jetzt auch... :blush: Man!!
Gruß und Dank
Andreas

#11

SkobyMobil:
Also wie sortieren?

Ist das noch eine aktuelle Fragestellung? Wenn ja, hätte ich einen Vorschlag:

uint16_t meinFeld[] = {190, 179, 173, 170, 167, 164, 162, 159, 160, 172, 203, 214, 216, 220, 223};
// uint16_t meinFeld[] = {223, 220, 216, 214, 203, 190, 179, 173, 172, 170, 167, 164, 162, 160, 159};  // zur Kontrolle der notwendigen Sortierschritte
uint16_t tmp;
bool oneshot = true;

void setup() {
  Serial.begin(9600);
  Serial.println("Anfang");
}

void loop()
{
  if (oneshot)
  {
    oneshot = false;
    uint8_t elemente = sizeof(meinFeld) / sizeof(meinFeld[0]);
    for (uint8_t k = 0; k < elemente; k++)
    {
      Serial.print(" ");
      Serial.print(float(meinFeld[k]) / 10, 1);
    }
    Serial.println();
    for (uint8_t j = 0; (j + 1) < elemente; j++)
    {
      for (uint8_t k = 0; (k + 1) < elemente; k++)
      {
        if (meinFeld[k] > meinFeld[k + 1])
        {
          tmp = meinFeld[k];
          meinFeld[k] = meinFeld[k + 1];
          meinFeld[k + 1] = tmp;
        }
      }
      for (uint8_t k = 0; k < elemente; k++)
      {
        Serial.print(" ");
        Serial.print(float(meinFeld[k]) / 10, 1);
      }
      Serial.println();
    }
    Serial.print("Median: ");
    Serial.println(float(meinFeld[elemente / 2]) / 10, 1); // nur bei ungerader Anzahl Elenemte gültig
  }
}

Ausgabe:

Anfang
 19.0 17.9 17.3 17.0 16.7 16.4 16.2 15.9 16.0 17.2 20.3 21.4 21.6 22.0 22.3
 17.9 17.3 17.0 16.7 16.4 16.2 15.9 16.0 17.2 19.0 20.3 21.4 21.6 22.0 22.3
 17.3 17.0 16.7 16.4 16.2 15.9 16.0 17.2 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 17.0 16.7 16.4 16.2 15.9 16.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 16.7 16.4 16.2 15.9 16.0 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 16.4 16.2 15.9 16.0 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 16.2 15.9 16.0 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
 15.9 16.0 16.2 16.4 16.7 17.0 17.2 17.3 17.9 19.0 20.3 21.4 21.6 22.0 22.3
Median: 17.3

Wenn die Zahlen nicht größer 255 werden, reicht auch uint8_t für das Feld.

#12

Hallo,
die RunningMedian funktioniert auch mit float. Ich bekomme es aber nicht
nachvollzogen warum deren Werte nicht mit meinen Werten übereinstimmt. Das
könnten Rundungsfehler sein oder etwas anderes.
Dann kommt es mir so vor, als wenn sie merkwürdigen dynamischen Speicher nutzt,
das ist aber mehr geraten als wissen.

Deinen Vorschlag werde ich probieren, wenn der schon richtig sortiert, dann ist
das für mehr als die halbe Miete. Den Rest bekomme ich selbst rausgepickt.

So, das hat mir ja keine Ruhe gelassen.
Ich habe es eben mit eigenen Werten probiert. Das macht einen sehr guten
Eindruck.

Die RunningMedian fliegt raus.

Wenn ich mir Deinen Sketch anschaue, dann ist mein Ansatz zur Sortierung nicht
ganz falsch gewesen. Mir kam es nur seltsam vor, das ich jede Ziffer mit jeder
Ziffer vergleichen sollte. Aber Du machst es auch so.

Ich glaube, das hast Du ziemlich gut gemacht.
Andreas sagt Danke schön.
Gruß und Spaß
Andreas

#13

SkobyMobil:
Ich glaube, das hast Du ziemlich gut gemacht.
Andreas sagt Danke schön.

Bitte gerne :slight_smile:

Integer (2 Bytes Ganzzahlen) zu sortieren geht sicherlich schneller, als float (4 Bytes). Schon was gewonnen!

Wieviele Werte hast Du denn tatsächlich? Sortieralgorithmen gibt es ja eine ganze Menge, ich habe den simpelsten verwendet. Bei 15 Elementen ist das wohl ok, bei deutlich mehr könnte man über etwas Effizienteres nachdenken.

#14

Hallo,
grundsätzlich sind es 24 Werte die auf persönlichen Abruft sortiert werden sollten.
Es könnten einmalig auch 96 werden. Wenn ich es auf die Spitze treibe 288.
Die 96 und 288 sind und bleiben aber int.

Sinn und Zweck des Ganzen ist es Erfahrungswerte für CO2/ppm zu sammeln.
Eigentlich mit einer Mitteilungszeit < 2min. Wenn die Testphase vorbei ist, dann
reicht mir eine Mitteilungszeit von 15min (96 lfd. Werte), oder auch mit
längerer Mitteilungszeit.

Ich glaube das sollte aber schnell genug sein. Ich brauche den Median ja nur
auf Abruf. Dazu kommt dann noch Mittelwert, Max. & Min. Wenn ich es hinbekomme
auch noch welcher Wert am häufigsten vorkommt. Sind also max. 5 zu liefernde Werte.

Jetzt habe ich über die serielle mal 96 Werte probiert, das geht eigentlich
von der Zeit her. 288 wird aber eng.
Bei 720 Werten kann man das dann wohl vergessen. Das macht aber nichts, die
zeichne ich dann auf SD und verarbeite sie extern.

Man muß mal sehen, wie schnell der Mega das intern verrechnet und nur die
4/5 gesuchten Werte auf dem TFT ausgibt.

Für mich ist das schon ein riesen Schritt nach vorne.
Schönen Dank noch einmal.
Gruß und Spaß
Andreas

#15

Mit dem Flag sortiert habe ich noch als Optimierung die Anzahl der Sortierschritte auf das notwendige Maß reduziert:

uint16_t meinFeld[] = {190, 179, 173, 170, 167, 164, 162, 159, 160, 172, 203, 220, 214, 216, 223};
// uint16_t meinFeld[] = {223, 220, 216, 214, 203, 190, 179, 173, 172, 170, 167, 164, 162, 160, 159};  // zur Kontrolle der notwendigen Sortierschritte
uint16_t tmp;
bool oneshot = true, sortiert;

void setup() {
  Serial.begin(9600);
  Serial.println("Anfang");
}

void loop()
{
  if (oneshot)
  {
    oneshot = false;
    uint8_t elemente = sizeof(meinFeld) / sizeof(meinFeld[0]);
    for (uint8_t k = 0; k < elemente; k++)
    {
      Serial.print(" ");
      Serial.print(float(meinFeld[k]) / 10, 1);
    }
    Serial.println();
    for (uint8_t j = 0; (j + 1) < elemente; j++)
    {
      sortiert = true;
      for (uint8_t k = 0; (k + 1) < elemente; k++)
      {
        if (meinFeld[k] > meinFeld[k + 1])
        {
          tmp = meinFeld[k];
          meinFeld[k] = meinFeld[k + 1];
          meinFeld[k + 1] = tmp;
          sortiert = false;
        }
      }
      for (uint8_t k = 0; k < elemente; k++)
      {
        Serial.print(" ");
        Serial.print(float(meinFeld[k]) / 10, 1);
      }
      Serial.println();
      if (sortiert)
      {
        j = elemente; // genug sortiert
      }
    }
    Serial.print("Median: ");
    Serial.println(float(meinFeld[elemente / 2]) / 10, 1); // nur bei ungerader Anzahl Elenemte
  }
}
#16

agmue:
Sortieralgorithmen gibt es ja eine ganze Menge, ich habe den simpelsten verwendet.

Der Standard Sortieralgorithmus sollte Insertion Sort sein. Ist einfach zu implementieren und hat in den meisten Fällen und vor allem bei kleinen Arrays ein recht gutes Zeitverhalten

https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#C

Viele professionelle Bibliotheken verwenden Quick Sort oder Merge Sort für große Arrays und wechseln bei kleinen zu Insertion Sort. Außerdem kann man Daten auch schon sortieren während man sie einliest.

#17

Hallo,
"schon sortieren während man sie einliest"

Da hatte ich auch schon drüber nachgedacht, aber die Daten kommen mit
ZeitStempel ins Array. Index[16] gleich 16:00h. Ein Diagramm für alle Daten-, nur
die Werte immer anders skalliert.

Ich könnte mir aber ein Sortiert Array anlegen, das könnte Zeit sparen.
Jetzt habe ich 12 Datenquellen, dann müßte ich also auch 12 Sortiert Array´s anlegen.
Mit der Funktion von agmue kann ich aber auf die Werte aller
Array´s (Datenquellen) zugreifen. Da müßte man mal schauen, womit man besser
fährt.

Den zweiten Vorschlag von agmue werde ich auch einmal probieren, mal sehen
ob es wirklich etwas bringt.

Vielen Dank euch beiden.
Gruß und Spaß
Andreas

#18

Gleich beim Einlesen einsortieren habe ich mal für 10 int ausprobiert:

#define ARRAY_LEN 10
int arr[ARRAY_LEN];
uint8_t anzahl = 0;  // belegte Arraywerte

// neue Zahl sortiert im Array arr (global) einfügen 
void sortedInsert(int *arr, int zahl) {
boolean found = false;
// bei leerem Array erster Wert
  if (anzahl == 0) {
    arr[0] = zahl;
    anzahl++;
    return;
  }
  // von hinten anfangen
  for(int8_t i = anzahl -1; i >= 0; i--) {
    // Wenn größer oder gleich nach hinten schieben
    if (arr[i] >= zahl) {
        arr[i+1] = arr[i];
    }
    else {
      // gefunden -> einsetzen
      arr[i+1] = zahl;
      found = true;
      break;
    }  
  }
  // Wenn nicht gefunden, dannn ist es der niedrigste Wert
  if (!found) {
    arr[0] = zahl;
  }
  anzahl++;
}

// Hilfsfunktion
void printArr(int *arr, uint8_t anzahl) {
  Serial.print("Anzahl: ");Serial.print(anzahl);Serial.print(" Elemente: ");
  for(uint8_t i = 0; i < anzahl; i++) {
    if (i>0) {
      Serial.print(", ");
    }    
    Serial.print(arr[i]);
  }
  Serial.println(" ");
}

Gruß Tommy

#19

Hallo,
ich habe es mal probiert:
agmue-1, 96 Werte, 9600 Baud, 48sek bis Median
agmue-2, 96 Werte, 9600 Baud, 42sek bis Median

Ob das "vorher sortieren" Sinn macht, ist aber auch zweifelhaft.
Für die Suche nach dem Ausgangswert mag es einen Vorteil bringen, weil
nichts mehr sortiert werden muß.

Bei der Eingabe, wenn es dumm läuft, müssen auch 95 Werte verglichen werden.
Da könnte man das Array aber teilen, paßt der Wert in die erste Hälfte?
(Vergleich- max, min erste Hälfte, mit Wert)
Nein, dann muß er in die zweite.

Aber eine Verzögerung bei der Eingabe muß ich nicht haben- wollen.
Der Wert muß reinkommen und abgelegt werden, sofort.
Verarbeiten und ausgeben kann ich später immer noch, auch mit Verzögerung.
Gruß und Spaß
Andreas

#20

SkobyMobil:
Den zweiten Vorschlag von agmue werde ich auch einmal probieren, mal sehen
ob es wirklich etwas bringt.

Das hängt von den Daten ab. Je besser die Daten zufallsbedingt vorsortiert sind, desto früher ist die Sortierung fertig. Bei agmue-1 macht die Sortierung immer n2 Durchläufe. Die weniger Durchläufe sollten die paar Befehle mehr locker aufwiegen. Du kannst also fast nur gewinnen.