die 5 kleinsten werte rausfiltern

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

1

float results[5];

2

float data;

3

float current_smallest = MAXFLOAT;

4

unsigned char index = 0;

5

unsigned int i = 0;

6

7

while(i < 1000)

8

{

9

  receive_new_value(data); /* neuen Messwert einlesen */

10

  if( data < current_smallest)

11

  {

12

    current_smallest = data;

13

    results[index] = data;

14

    if(index == 4)

15

      index = 0;

16

    else

17

      index++;

18

  }

19

20

  i++;

21

}

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 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.

1

Das 5erArray mit Werten füllen, die größer als der maximal vorkommende Wert in den Daten ist

2

3

for( i = 0; i < 1000; ++i )

4

{

5

  if( daten[i] >= 5erArray[4] )  // Trivial-vortest

6

    continue;

7

8

  for( j = 4; j > 0; --j )

9

  {

10

    if( daten[i] <= 5erArray[j] )

11

      // Einschubstelle gefunden

12

      // Im 5-er Array alle Werte von j bis 3 um 1 Position

13

      // nach hinten verschieben

14

      // Neuer Wert kommt an 5-erArray[j]

15

      break;

16

  }

17

}

So in etwa.

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

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.

1

>         // Im Array alle Werte bis j um 1 Position nach hinten verschieben

2

>          k = MIN(LISTSIZE-1,nbPoints);

3

>          //k = (LISTSIZE-1);

4

>        while( k > j)

5

>        {

6

>          results[k-1][0] = results[k][0];

7

>          results[k-1][1] = results[k][1];

8

>          k--;

9

>        }

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