die 5 kleinsten werte rausfiltern

[Michael (Gast)]

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

[Mark B. (markbrandis)]

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++;
}

[Karl H. (kbuchegg)]

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

[Michael (Gast)]

Hallo,

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

[Karl H. (kbuchegg)]

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.

[Michael (Gast)]

Hallo Karl Heinz,

besten Dank, so funktioniert das jetzt ganz gut.

[Michael (Gast)]

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);
}

[Karl H. (kbuchegg)]

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

[Michael (Gast)]

ok, ich habs gefunden.

while( k > j)
        {
          results[k][0] = results[k-1][0];
          results[k][1] = results[k-1][1];
          k--;
        }