Häufigkeitsverteilung von int Werten

Kolja Gast #4549007
Lesenswert?
• ▲
▼ 
Moin

Leider finde ich keinen direkten Befehl für Arduino / ESP,
der mir die beiden am häufigsten vorkommenden Werte aus einem Array 
wiedergibt.

Das Array hast 2 x 1000 Zeilen und die Werte gehen von 0-1024.
Was ja jetzt nich so viel ist.

Hat da jemand ne Idee oder Erfahrung?
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Dr. Sommer Gast #4549014
Lesenswert?
• ▲
▼ 
1
uint16_t array [1024];

2
uint16_t h [1025] = {};

3


4
for (size_t i = 0; i < 1024; ++i) {

5
  ++h [array [i]];

6
}

7


8
uint16_t max1 = 0;

9
uint16_t max2 = 0;

10


11
for (size_t i = 1; i < 1025; ++i) {

12
  if (h[i] > h[max1]) {

13
    max2 = max1;

14
    max1 = i;

15
  } else if (h[i] > h[max2]) {

16
    max2 = i;

17
  }

18
}

19


20
printf ("Die beiden größten Werte sind %" PRIu16 " und %" PRIu16 "\n", max1, max2);
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Dr. Sommer Gast #4549081
Lesenswert?
• ▲
▼ 
Kolja schrieb:
> Gehe ich denn recht in der Annahme, das er mir die beiden größten Werte
> und nicht die beiden häufigsten Werte ausgibt?

Er speichert die Häufigkeit der Werte im Array h und gibt dann davon die 
Position der zwei größten Werte aus, und damit die beiden häufigsten 
Werte im Original-Array. Hab mich auch vertan, 1024 sollte natürlich 
2000 sein. Der Text in der Ausgabe ist natürlich Quatsch, es sollte 
heißen "die beiden häufigsten Werte"...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Flauschig-weicher Qualitätsgarant Gast #4549138
Lesenswert?
• ▲
▼ 
Du brauchst leider entweder Platz (Histogramm) oder Zeit (sortieren; 
ohne Kopie natürlich nur, wenn die ursprüngliche Ordnung irrelevant 
ist).
Es gibt einen schönen, einfachen Algorithmus von Bob Boyer (A Linear 
Time Majority Vote Algorithm), aber der funktioniert hier auch in einer 
modifizierten Form nicht, da das jeweilige Element mindestens n/2 mal 
vorkommen muss.

Kolja schrieb:
> Aber kann man den Platz auch wieder freigeben?
> Z.B. um an einer anderen Stelle ein anderes array zu initialisieren?

Ich kenne mich mit der Arduino-Umgebung nicht aus, aber vielleicht hilft 
das hier weiter:

http://arduino.land/FAQ/content/4/26/en/how-to-use-dynamic-memory.html
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Der Andere Gast #4549148
Lesenswert?
• ▲
▼ 
Array sortieren, dann linear durchgehen und die Anzahl jeweils gleicher 
Elemente zählen und die beiden Elemente, die am häufigsten vorkommen 
sowohl von ihrem Wert als ihrer Häufigkeit merken.

Oder so wie Dr Sommer das macht.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
blechiger Dampftroll Gast #4549505
Lesenswert?
• ▲
▼ 
> Leider finde ich keinen direkten Befehl für Arduino / ESP, der mir die beiden am 
häufigsten vorkommenden Werte aus einem Array wiedergibt.


Danke fuer einen tollen Vorschlag fuer die naechste Version von 
"muss-haben" Library, die dann als 25GB Package daherkommt.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren