Häufigkeitsverteilung von int Werten

[Kolja (Gast)]

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?

[Dr. Sommer (Gast)]

uint16_t array [1024];
uint16_t h [1025] = {};

for (size_t i = 0; i < 1024; ++i) {
  ++h [array [i]];
}

uint16_t max1 = 0;
uint16_t max2 = 0;

for (size_t i = 1; i < 1025; ++i) {
  if (h[i] > h[max1]) {
    max2 = max1;
    max1 = i;
  } else if (h[i] > h[max2]) {
    max2 = i;
  }
}

printf ("Die beiden größten Werte sind %" PRIu16 " und %" PRIu16 "\n", max1, max2);

[edgar S. (hbl333)]

Spieglein Spieglein an der Wand
Wer ist der häufigste im Land

[Kolja (Gast)]

Hallo Dr.Sommer

So ganz kann ich deinen Code noch nicht nachvollziehen.

Gehe ich denn recht in der Annahme, das er mir die beiden größten Werte
und nicht die beiden häufigsten Werte ausgibt?

[Dr. Sommer (Gast)]

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

[Peter D. (peda)]

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

Sicher?
Wieviel RAM hat der denn?

[Falk B. (falk)]

Es gibt auch "große" Arduinos mit ARM-Prozessor, z.B. den Due mit 96kB 
RAM.

http://www.arduino.cc/en/Main/ArduinoBoardDue

[Kolja (Gast)]

Ist n ESP8266-12e
Ich glaube bis array[3][3000] hat es funktioniert.

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

[Flauschig-weicher Qualitätsgarant (Gast)]

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

[Der Andere (Gast)]

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.

[blechiger Dampftroll (Gast)]

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