mikrocontroller.net

Forum: Compiler & IDEs die 5 kleinsten werte rausfiltern


Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich bekomme ca. 1000 float Messwerte pro Sekunde. In einem array möchte 
ich mir die 5 kleinsten Werte dieser 1000 Werte ablegen. Wie könnte man 
das in C am effektivsten lösen?

Michael

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Müde zusammengehackt und ohne Gewähr. Und nicht für alle Fälle geeignet 
(z.B wenn ein Messwert gleich X ist und alle 999 anderen Messwerte 
gleich Y) denke ich. Gehe jetzt ins Bett, N8

float results[5];
float data;
float current_smallest = MAXFLOAT;
unsigned char index = 0;
unsigned int i = 0;

while(i < 1000)
{
  receive_new_value(data); /* neuen Messwert einlesen */
  if( data < current_smallest)
  {
    current_smallest = data;
    results[index] = data;
    if(index == 4)
      index = 0;
    else
      index++;
  }

  i++;
}

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael schrieb:
> Hallo,
>
> ich bekomme ca. 1000 float Messwerte pro Sekunde. In einem array möchte
> ich mir die 5 kleinsten Werte dieser 1000 Werte ablegen. Wie könnte man
> das in C am effektivsten lösen?

Was ist wenn Messwerte doppelt auftreten?

Benötigst du dann die 5 kleinsten Messwerte die unterschiedliche Werte 
haben oder die 5 tatsächlich kleinsten Werte?

Bsp für 2

Deine Messreihe sei

   4 5 2 4 5 2

sind die beiden kleinsten Werte  2 2
oder sind sie                    2 4

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

es sollten die 5 kleinsten sein, in deinem Beispiel: 2 2

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael schrieb:
> Hallo,
>
> es sollten die 5 kleinsten sein, in deinem Beispiel: 2 2

Würd ich dann so machen

Ein kleines Array mit 5 Einträgen.
Aufgabe des Arrays: die 5 Werte halten, wobei die 5 Werte in diesem 
Array aufsteigend sortiert sind.
Das 5erArray mit Werten füllen, die größer als der maximal vorkommende Wert in den Daten ist

for( i = 0; i < 1000; ++i )
{
  if( daten[i] >= 5erArray[4] )  // Trivial-vortest
    continue;

  for( j = 4; j > 0; --j )
  {
    if( daten[i] <= 5erArray[j] )
      // Einschubstelle gefunden
      // Im 5-er Array alle Werte von j bis 3 um 1 Position
      // nach hinten verschieben
      // Neuer Wert kommt an 5-erArray[j]
      break;
  }
}


So in etwa.

Was natürlich auch zu überlegen wäre, wenn du den Platz hast: sortieren 
und die ersten 5 nehmen.

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Karl Heinz,

besten Dank, so funktioniert das jetzt ganz gut.

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

da ist doch noch ein Fehler bei meiner Umsetzung.
Es sind zu wenig Punkte nach der Berechnung in der Liste.
In meinem Beispiel sind 47 Koordinaten kleiner MAXDIST, es sind aber nur 
14 in der LIste.
void NearestWP (void)
{
  #define LISTSIZE  100
  #define MAXDIST    60000  //Meter

  char line[60];
  unsigned char j,k;
  float results[LISTSIZE][2];
  float distance;
  unsigned short waypoints, i, nbPoints=0;

  for (j=0; j<LISTSIZE; j++)
  {
    results[j][0] = MAXDIST;
    results[j][1] = 0;
  }

  waypoints = fsaccess_file_get_size(waypointfile)/sizeof(WAYPOINT);

  for(i=0; i < waypoints; i++)
  {
    read(waypointfile,(unsigned char *) &WayPoint, sizeof(WAYPOINT));
    distance = coord2strecke(Gps.lat,Gps.lon,WayPoint.latitude,WayPoint.longitude);//Distanz von aktueller Position zum Wegpunkt

    if( distance > results[LISTSIZE-1][0] )  continue;

      nbPoints++;

      for( j = 0; j < nbPoints; j++ )
      {
        if( distance < results[j][0] )
        {
          // Im Array alle Werte bis j um 1 Position nach hinten verschieben
          k = MIN(LISTSIZE-1,nbPoints);
          //k = (LISTSIZE-1);
        while( k > j)
        {
          results[k-1][0] = results[k][0];
          results[k-1][1] = results[k][1];
          k--;
        }
          // Neuer Wert kommt an Array[j]
          results[j][0] = distance;
        results[j][1] = i;
        break;
        }
      }
  }
  for(j=0; j<nbPoints; j++)
  {
    seek(waypointfile,results[j][1]*sizeof(WAYPOINT),FS_SEEK_SET);
    read(waypointfile,(unsigned char *) &WayPoint, sizeof(WAYPOINT));
    distance = coord2strecke(Gps.lat,Gps.lon,WayPoint.latitude,WayPoint.longitude);
    sprintf (line,"\nWP%d:%s %.1fkm\n",j+1,WayPoint.name,distance/1000);
    usart_puts(USART1, line);
  }
  seek(waypointfile,0,FS_SEEK_SET);
}

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael schrieb:

>     if( distance > results[LISTSIZE-1][0] )  continue;
>

Die ganze Idee an diesem Shortcut ist es, die Vergleichsschleife 
einzusparen. Wenn du 5 Punkte bisher gefunden hast, mit den Distanzen 
10, 11, 12, 13, 14 und du hast eine neue Distanz 25, also einem Wert, 
der größer ist als das bisherige Maximmum aller kleinsten Distanzen, 
dann kann diese Distanz nicht in das Minimalarray gehören. Daher ist 
dann der folgende Vergleichs und Suchlauf überflüssig. Es handelt sich 
daher um einen quick&dirty Vortest, der nur dazu da ist, schnell zu 
entscheiden, ob diese zu testende Distanz überhaupt eine Chance hat 
irgendetwas in den bisher gefundenen Minima zu bewirken.
Wieviele Einträge umfasst den eigentlich das results Array zu jedem 
beliebigen Zeitpunkt. Nun, die Anzahl davon steht in nbPoints.

>       nbPoints++;

Warum rückst du hier ein?

Im Ernst: das kann nicht stimmen.
Stell dir einfach mal vor, was ganz am Anfang passiert.
Das results array ist leer.
Wenn du jetzt an dieser Stelle nbPoints erhöhst, dann versucht der 
folgende Programmteil die Distanz mit einem imaginären Punkt zu 
vergleichen, der noch gar nicht in der Liste ist.


Darf ich vorschlagen, dass du deine Kennzahlen einfach einmal drastisch 
runterfährst (es macht keinen Sinn erste Tests mit Unmengen an Daten zu 
fahren) und dann das Zeugs im Debugger mal durchzusteppen.
Am besten konstruierst du dir ein Beispiel auf dem Papier und schaust 
dir am Papier an was eigentlich rauskommen müsste (und auch warum). Dann 
vergleichst du, was dein Programm macht (durchaus auch im Debugger) und 
warum. Dann wirst du auch deine Fehler finden.

Aber mit 1000 Datensätzen von denen 100 gesucht werden kann man nicht 
vernünftig debuggen. Dazu reichen 10 Datensätze von denen 3 oder 4 
gesucht werden allemal.

>         // Im Array alle Werte bis j um 1 Position nach hinten verschieben
>          k = MIN(LISTSIZE-1,nbPoints);
>          //k = (LISTSIZE-1);
>        while( k > j)
>        {
>          results[k-1][0] = results[k][0];
>          results[k-1][1] = results[k][1];
>          k--;
>        }

Ähm. Nach hinten schieben. ... Wieso dann k-1? Hinten ist bei einem 
Array k+1

Autor: Michael (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ok, ich habs gefunden.
while( k > j)
        {
          results[k][0] = results[k-1][0];
          results[k][1] = results[k-1][1];
          k--;
        }


Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.