Häufigsten Buchstaben in einem Char-Array herrausfinden?
Hallo liebe Leser/innen, ich versche in meinem Java Programm aus einem Char Array den häufigst vorkommenden Buchstaben herrauszufinden. Hat jemand einen Tipp bzw. eine Lösung für mein Problem? Danke im voraus. Lg Varauc :)
3 Antworten
Ich würde mir ja ne HashMap<Character, Integer> anlegen, mit ner Schleife über das Array iterrieren und für jeden einzelnen Buchstaben entweder wenn er noch nicht in der HashMap ist ihn einfügen oder wenn er bereits enthalten ist den gemapten Wert um inkrementieren.
Danke, das kann ich mal schauen. Muss mich dann mal bisschen im Maps einlesen. ;) Aber werde es mal versuchen.
Bei kurzen Strings ist die Antwort von blackst0rm sehr gut, aber bei langen Strings wird es mit einer HashMap zu sehr gemeinen Performance-Problemen kommen.
Die folgende Lösung ist wesentlich effizienter, wenn du sehr sehr lange Texte verarbeiten möchtest, aber für kurze Texte ein absoluter Overkill:
class MostCommon {
public static char mostCommon(char arr[]) {
long positions[] = new long[Character.MAX_VALUE];
for (char c : arr) {
if (Character.isLetterOrDigit(c)) {
++positions[c];
}
}
long highest = 0L;
char result = '\0';
for (int i = 0, len = positions.length; i < len; ++i) {
if (highest < positions[i]) {
highest = positions[i];
result = (char)i;
}
}
return result;
}
public static void main(String[] args) {
String s = "Das ist das Haus vom Nikolaus.";
char ca[] = s.toCharArray();
System.out.println("<" + mostCommon(ca) + ">");
}
}
Hängt halt immer davon ab, ob du nur eine Zeile Text verabeiten willst, oder ob du über einen Terabyte an Wikipedia-XML abhandeln willst. :)
Bei kurzen Texten, nimm einfach eine HashMap! :)
PS: Ich sehe gerade, dass man die Character.isLetterOrDigit() Abfrage eigentlich in die unere Schleife verschieben könnte bzw. sollte, dann muss diese nämlich nur 65536 mal aufgerufen werden, und nicht n-mal, was bei sehr langen Arrays nicht empfehlenswert wäre. Naja, das ganze ist ja sowieso unrealistisch, da wohl niemand ein mehrere GB großes Char-Array im RAM verarbeiten wird. Man sollte sich lieber auf Streams und Iteratoren besinnen. :)
Ich würde deine Lösung ehrlich gesagt auch vorziehen. :)
Wenn man wirklich vor hätte, mehrere GB zu analysieren, würde ich sowieso eine ordentliche Klasse drum herum bauen, sodass evtl. nicht bei jedem einzelnen Funktionsaufruf - wie bei meiner obigen Lösung - erstmal 512KB Speicher reserviert werden müssen. In dem Falle ist natürlich bei sehr kurzen Strings eine HashMap schneller. :)
Theoretish könnte mann noch ne Lauflängencodierung vorschalten. Dann müsste mann das für die einzelnen Zeichen die Werte aufaddieren und hätte das Ergebnis. Aber ich glaub das führt langsam zu weit ;)
PPS: Außerdem muss das Array am Anfang mit new long[Character.MAX_VALUE + 1] initialisiert werden ... oh man, heute stehe ich irgendwie neben mir. ><
Danke euch beiden für die Antworten. Wie blackst0rm schon geasgt hat handelt es sich um einen Teil einer Übungsaufgabe und ich werde höchstens 5 Sätze einlesen :) Ich habe das ganze mal mit einer HashMap gemacht. Und funktioniert auch :) Dankeschön :)
/*Sortieren und dann die längste Sequenz finden: */
package ch.programmieraufgaben.haeufig;
import java.util.Arrays;
/** * @version 0.1 (Jun 17, 2015)
* @author igeeks
* (igeeks@programmieraufgaben.ch) */
public class FindeHaeufigsteBuchstaben {
public static void main(String[] args) {
new FindeHaeufigsteBuchstaben().top();}
void top() {
test("abcb", 'b');
test("abteastasrnaiatsrnaeaaatarntsaa", 'a');
test("ccbbddefef", 'b'); // wird nicht übertroffen
test("ccbbddefefc", 'c');
}
void test(String orig, char testBuchst) {
char resultat = haeufigster(orig);
System.out.print("Test " + orig + " " + testBuchst + " ");
if(resultat == testBuchst) {
System.out.println("OK");
} else {
System.out.println(" fail! (ist " + resultat + ")");
}
}
/* Hauptmethode (bisher war alles blahblah. */
char haeufigster(String orig) {
char[] alle = orig.toCharArray();
Arrays.sort(alle);
// finde längste Sequenz
char found = alle[0];
int foundLen = findLen(alle, 0);
for(int i = 1; i < alle.length; i++) {
int actLen = findLen(alle, i);
if(actLen > foundLen) {
found = alle[i];
foundLen = actLen;
}
}
return found;
}
int findLen(char[] alle, int startPos) {
char startChar = alle[startPos];
int len = 1;
for(int i = startPos + 1; i < alle.length; i++) {
if(alle[i] != startChar) {
return len;
}
len ++;
}
return len;
}
} // end of class FindeHaeufigsteBuchstaben
Habe gerade gesehen, dass es noch perfomanter geht:
Anstelle "i++" in der Methode "häufigster()" setze ich nun am Ende in der Methode "i = i + actLen". So kann ich in Strings mit vielen Häufigkeiten einiges an Zeit sparen.
package ch.programmieraufgaben.haeufig;
import java.util.Arrays;
/** * @version 0.1 (Jun 17, 2015)
* @author igeeks
* (igeeks@programmieraufgaben.ch) */
public class FindeHaeufigsteBuchstaben {
/* Hauptmethode (bisher war alles blahblah. */
char haeufigster(String orig) {
char[] alle = orig.toCharArray();
Arrays.sort(alle);
// finde längste Sequenz
char found = alle[0];
int foundLen = findLen(alle, 0);
for(int i = 1; i < alle.length;) {
int actLen = findLen(alle, i);
if(actLen > foundLen) {
found = alle[i];
foundLen = actLen;
}
i = i + actLen;
}
return found;
}
int findLen(char[] alle, int startPos) {
char startChar = alle[startPos];
int len = 1;
for(int i = startPos + 1; i < alle.length; i++) {
if(alle[i] != startChar) {
return len;
}
len ++;
}
return len;
}
} // end of class FindeHaeufigsteBuchstaben
Du hast vollkommen Recht. Performancetechnisch ist die Lösung mit der HashMap natürlich eine Katastrophe. Aber ich dachte mir halt das es sich eher um ne Übungsaufgabe handeln wird bei der eher weniger mehrere hundert Megabyte an Daten analysiert werden sollen. Also KISS-Prinzip angewendet und diese Lösung vorgeschlagen. ;)