Hallo, ich hab da ein kleines Problem. Ich hab ein 6 Felder großes Array mit 8Bit Werten. D.h. ich hab maximal 6 verschiedene Werte in dem Array. Nun will ich wissen welcher Wert im Array am häufigsten vorkommt. Am einfachsten ist es natürlich ein Hilfsarray mit 256 Feldern zu erstellen und an die entsprechenden Felder immer um 1 zu inkrementieren wenn die Zahl die das Feld darstellt vorkommt. Dazu brauche ich aber ein 256 Byte großes Hilfsarray welches nicht mehr in den Speicher passt. Der µc ist voll. :-( Hat da jemand spontan ne Lösung für?
1. array sortierne. 2. array durchlaufen und die anzahl gleicher elemente zählen (anzahl und element merken 3. wenn die neue anzahl > als alte anzahl dann neue anzahl und element merken. 4. wenn array durchlaufen, steht im merker das element und die anzahl
Hmm. das klingt nicht schlecht. Werd ich mich mal an die Umsetzung machen.
>>Hmm. das klingt nicht schlecht.
Doch, tut es.
Man braucht keine großen Felder und muß auch nix sortieren.
char ch[NN]={5,12,12,6,2,1};
int k,maxx=1,maxxn,m,n;
maxxn=ch[0];
for(k=0;k<NN-1;k++){
n=1;
for(m=k+1;m<NN;m++) n+=(ch[k]==ch[m]);
if(n>maxx){maxx=n;maxxn=ch[k];}
}
printf("maxanz %d was %d\n",maxx, maxxn);
Frohe Ferien noch.
Cheers
Detlef
Detlef _a schrieb: >>>Hmm. das klingt nicht schlecht. > Doch, tut es. > > Man braucht keine großen Felder und muß auch nix sortieren. Dafür hat man dann aber auch quadratische Laufzeit :-) Gut. Bei 6 Werten spielt das keine Rolle, aber bei 1 Million schon.
> Bei 6 Werten spielt das keine Rolle, aber bei 1 Million schon.
Allerdings kann bei 1 Million Werte auch der Platz für den sortierten
Array fehlen. Außer er überschreibt den ursprünglichen Array.
Andererseits wird der Array wohl kleiner als 256 Felder bleiben, da ja
bereits da der Speicher fehlt.
Der Aufwand steigt tatsächlich deutlich schneller, weil oft in die innere for schleife gesprungen wird obwohl der entsprechende Inhalt des Arrays schon geprüft wurde. Man könnte es noch ein bisschen beschleunigen: char ch[NN]={5,12,12,6,2,1}; int k,maxx=1,maxxn,m,n; maxxn=ch[0]; for(k=0;k<NN-1;k++){ n=1; if(ch[k]==maxxn){continue;} for(m=k+1;m<NN;m++) n+=(ch[k]==ch[m]); if(n>maxx){maxx=n;maxxn=ch[k];} }
Die Laufzeit steigt dann aber immer noch quadratisch. Da ist die allererste Antwort besser, zumindest sofern man die Werte entweder nicht mehr braucht, oder nochmal genausoviel Speicher übrig hat.
die oben genannte Methode mit dem Vorsortieren funktioniert perfekt. Nun habe ich dem Hardware-Bitschubser im Bus einen Strich durch die Rechnung gemacht. duck
Karl heinz Buchegger schrieb: > Detlef _a schrieb: >>>>Hmm. das klingt nicht schlecht. >> Doch, tut es. >> >> Man braucht keine großen Felder und muß auch nix sortieren. > > Dafür hat man dann aber auch quadratische Laufzeit :-) > Gut. Bei 6 Werten spielt das keine Rolle, aber bei 1 Million schon. Ein blödes Sortierverfahren hat auch O(n^2), O(n*log(n)) kostet Codesize. Bei 6 Werten würde ich den Code kurz machen und 1 Million Werte passen auch nicht so gut in nen uC. Für große n würde ich die Methode mit dem 256er array nehmen, die hat O(n). So gibts für jeden Deckel nen Topf, das ist schön. > die oben genannte Methode mit dem Vorsortieren funktioniert perfekt. Glückwunsch, dann ist ja alles gut. Cheers Detlef
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.