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
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
Hallo, es sollten die 5 kleinsten sein, in deinem Beispiel: 2 2
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.
Hallo Karl Heinz, besten Dank, so funktioniert das jetzt ganz gut.
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.
1 | void NearestWP (void) |
2 | {
|
3 | #define LISTSIZE 100
|
4 | #define MAXDIST 60000 //Meter
|
5 | |
6 | char line[60]; |
7 | unsigned char j,k; |
8 | float results[LISTSIZE][2]; |
9 | float distance; |
10 | unsigned short waypoints, i, nbPoints=0; |
11 | |
12 | for (j=0; j<LISTSIZE; j++) |
13 | {
|
14 | results[j][0] = MAXDIST; |
15 | results[j][1] = 0; |
16 | }
|
17 | |
18 | waypoints = fsaccess_file_get_size(waypointfile)/sizeof(WAYPOINT); |
19 | |
20 | for(i=0; i < waypoints; i++) |
21 | {
|
22 | read(waypointfile,(unsigned char *) &WayPoint, sizeof(WAYPOINT)); |
23 | distance = coord2strecke(Gps.lat,Gps.lon,WayPoint.latitude,WayPoint.longitude);//Distanz von aktueller Position zum Wegpunkt |
24 | |
25 | if( distance > results[LISTSIZE-1][0] ) continue; |
26 | |
27 | nbPoints++; |
28 | |
29 | for( j = 0; j < nbPoints; j++ ) |
30 | {
|
31 | if( distance < results[j][0] ) |
32 | {
|
33 | // Im Array alle Werte bis j um 1 Position nach hinten verschieben
|
34 | k = MIN(LISTSIZE-1,nbPoints); |
35 | //k = (LISTSIZE-1);
|
36 | while( k > j) |
37 | {
|
38 | results[k-1][0] = results[k][0]; |
39 | results[k-1][1] = results[k][1]; |
40 | k--; |
41 | }
|
42 | // Neuer Wert kommt an Array[j]
|
43 | results[j][0] = distance; |
44 | results[j][1] = i; |
45 | break; |
46 | }
|
47 | }
|
48 | }
|
49 | for(j=0; j<nbPoints; j++) |
50 | {
|
51 | seek(waypointfile,results[j][1]*sizeof(WAYPOINT),FS_SEEK_SET); |
52 | read(waypointfile,(unsigned char *) &WayPoint, sizeof(WAYPOINT)); |
53 | distance = coord2strecke(Gps.lat,Gps.lon,WayPoint.latitude,WayPoint.longitude); |
54 | sprintf (line,"\nWP%d:%s %.1fkm\n",j+1,WayPoint.name,distance/1000); |
55 | usart_puts(USART1, line); |
56 | }
|
57 | seek(waypointfile,0,FS_SEEK_SET); |
58 | }
|
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
ok, ich habs gefunden.
1 | while( k > j) |
2 | {
|
3 | results[k][0] = results[k-1][0]; |
4 | results[k][1] = results[k-1][1]; |
5 | k--; |
6 | }
|
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.