Häufigkeit von jeder Zahl in der Liste(programmieren)
Hallo! Ich hoffe, dass Sie mir weiterhelfen können. Ich muss schnell und effizient die Häufigkeit jeder Zahl in der Liste ermitteln.(Liste besteht aus 5000 elementen)
Man konnte einen Array von 0 bis max.Zahl anlegen und dann die Liste durchgehen und die Zahlen zählen. Das Problem ist, dass ich die max. Zahl nicht kenne. Und es konnte locker 9999999 sein. Es wäre dann uneffizient das Array von 0 bis 999999 anzulegen. Gibt es andere Ansätze?
Vielen Dank im Voraus.
4 Antworten
Kurze Frage: Wenn du 5000 Elemente hast, wie können es dann 9999999 sein? Tut mir leid, aber das verstehe ich nicht, so wie es da formuliert ist.
Ansonsten andere Lösung (weiß nicht ob diese Effizient ist):
(bei Code gehen keine < >, deswegen ohne Code Tag):
HashMap<K, V> map = new HashMap<K,V>();
Kennst du dich mit generischer Programmierung aus? K und V kannst du jeweils durch Klassennamen ersetzen, z.B.
HashMap<String, Integer> map = new HashMap<String, Integer>();
K ist hier der Schlüssel (Key) und V der Wert (Value).
Du könntest dann wie folgt ein Element einfügen, wenn du z.B. Wörter in einem Text zählen willst:
if (map.contains(string)) {
map.put(string, map.get(string) + 1);
}
else {
map.put(string, 1);
}
Hoffe du hast ungefähr verstanden was ich meine. Ich kenne jetzt nicht alle verfügbaren Maps und Listen, aber mit der Java API, solltest du da schnell etwas finden, was dir weiterhilft.
Grüße Carleone123
PS: Auslesen der Werte über
map.get(string);
oder mit Iterator rüberlaufen:
for (String key : map.getKeySet()) {
System.out.println("Key: " + key + " Value: " + map.get(key));
}
Sei froh dass du es in Python schreiben darfst, da ist es wenigstens nicht so hässlich wie in Java ;)
Naja…das kommt auf die Wahrnehmung drauf an.
Wenn man ein abstraktes Gemälde schön findet oder einen Schießhaufen liegt im Auge des Betrachters. Ich geh halt gerne in Kunstgallerien.
Java-Kunst ist mir irgendwie zu primitiv und plump ;)
HashMap<String, Integer> map = new HashMap<String, Integer>();
map = {}
Tja siehst du, wenn ein anderer jetzt meinen Code liest, weiß er wofür die Map da ist. Bei dir fragt er sich, was da wohl drin stehen könnte. Java ist einfach freundlicher und wer oft Refactoring fremden Codes betreibt, freut sich über eindeutigen und schönen Code.
Normalerweise benennt man seine Maps auch ein wenig eindeutiger als "map" ;)
Dann sieht man, was man damit macht.
Die Typangabe <String, Integer> sagt kaum etwas über den Sinn der Map aus, vor allem wenn man mehrere davon hat.
Statische Typisierung ist schon oft praktisch, aber es muss doch nicht gar so hässlich sein wie in Java.
In Scala ist das auch nur:
val map = HashMap[String, Int]()
Und da kann man gleich die Wertepaare als Argumente übergeben.
Normalerweise benennt man seine Maps auch ein wenig eindeutiger als "map" ;)
Echt? ;)
Nun, ich finde Java-Code schön anzuschauen, wenn er gut geschrieben ist. Aber das ist in jeder Programmiersprache so.
Bleiben wir dabei, dass jeder seine Vorlieben hat :P
Wenn man die Größe vorher nicht kennt nimmt man quasi immer ein dict (Hashmap). Das ist auch ziemlich effizient.
Ich würde für das Problem das hier vorschlagen:
def count(seq):
counts = {}
for num in seq:
count = counts.get(num, 0)
counts[num] = count + 1
return counts
Das gibt dir ein dict zurück, dass zu jeder Zahl die Anzahl enthält. Bei mir dauert das (bei deinen Angaben) 1,6ms mit Python3. Schnell genug?
Ich sehe gerade, dass es für die ganz Faulen auch schon was Fertiges gibt (ab Python 2.7)
from collections import Counter
counts = Counter(seq)
Braucht aber 2.9ms ;)
Hier eine Möglichkeit, das in Python zu machen (es gibt noch viele andere Varianten):
#!/usr/bin/python
liste = [810780978, 104547510, 784070747, 155805789, 810780978,
784070747, 810780978, 810780978, 104547510, 784070747]
zahlen = [];
for wert in liste:
if not wert in zahlen:
zahlen.append(wert);
print wert, liste.count(wert);
Die Ausgabe dieses Programmes:
810780978 4
104547510 2
784070747 3
155805789 1
Ich habe somit übrigens mein erstes Python-Programm geschrieben (hatte vorher noch nie in Python programmiert, aber viel in anderen Sprachen).
Ich habe gerade festgestellt, dass die drei von mir verwendeten Strichpunkte (am Ende der Anweisungen) allesamt überflüssig sind. Habe wohl doch zuviel in anderen Sprachen programmiert ...
Das wollte ich auch gerade sagen ;)
Die Lösung geht, aber ist schon ein wenig ineffizient, so Faktor 150 langsamer zu meiner Lösung.
Klar, danke!
Ich hatte zuvor (als ich nocht nicht wusste, welche Sprache der Fragesteller benutzt) eine Version in Perl geschrieben. Die verwendet ein assoziatives Array - analog dem Dictionary in Python:
@liste = (810780978, 104547510, 784070747, 155805789, 810780978,
784070747, 810780978, 810780978, 104547510, 784070747);
%haeufigkeit = ();
foreach $wert(@liste)
{
++$haeufigkeit{$wert};
}
foreach $wert(sort(keys %haeufigkeit))
{
printf("Zahl: %9d, Haeufigkeit: %2d\n", $wert, $haeufigkeit{$wert});
}
es können aber höchstens 5000 verschiedene zahlen sein. als könnte {0,0} = 1.zahl, {0,1} = anzahl 1. zahl, {1,0} = 2. zahl, {1,1} = anzahl 2. zahl,... sein.
Die Liste hat 5000 Elementen. Die max. Zahl kann 999999 sein. 5000 Elementen bestehen aus zufälligen Zahlen (0,1000000000)
Und ich wollte das Prinzip kennen, weil ich es nicht in Java/C++ schreiben muss,sondern in Python.