mikrocontroller.net

Forum: Compiler & IDEs Häufigste Zahl im Array finden


Autor: Suchender (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Suchender (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm. das klingt nicht schlecht. Werd ich mich mal an die Umsetzung 
machen.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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

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

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Horst (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Alexander Schmidt (esko) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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];}
   }

Autor: der mechatroniker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Suchender (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
die oben genannte Methode mit dem Vorsortieren funktioniert perfekt.

Nun habe ich dem Hardware-Bitschubser im Bus einen Strich durch die 
Rechnung gemacht. duck

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

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.