[JAVA] Buchstaben sortieren, herausfinden welche Reihenfolge

[feuerteufel]

Hallo,

für ein Programm brauche ich eine Funktion die folgendes tut:

- Es wird ein String übergeben
- Die Buchstaben werden sortiert
- Ich brauche die alte Position der Buchstaben in einer Reihenfolge.

Zum Beispiel:

CAB
Sortiert ergibt das ABC
Die Positionen wären - beginnend bei 0:
1, 2, 0

Ein anderes Beispiel habe ich mit dem Wort "AUTOHAUS" angehängt.



Ich habe schon etwas ausprobiert, was aber nicht so klappt:

[src=java]private List<Integer> sortChars(String l){
List<Integer> sortiert = new ArrayList<>();
int amKleinsten;
char tempChar;
int grenze = l.length();

for(int i=0; i<grenze; i++){

amKleinsten = i;
tempChar = l.charAt(i);
boolean enthaelt;

for(int k=0; k<grenze; k++){
enthaelt = sortiert.contains(k);

if(tempChar > l.charAt(k) && enthaelt == false){
tempChar = l.charAt(k);
amKleinsten = k;
}

}
sortiert.add(amKleinsten);
}

return sortiert;
}[/src]

Die erste for-Schleife geht Buchstabe für Buchstabe durch, um in der zweiten for-Schleife (verschachtelt) zu prüfen, ob es noch andere "kleinere" chars gibt.
Dann wird die Position des kleinsten Buchstabens abgespeichert in einer ArrayList.

Sieht vielleicht jemand einen Fehler oder kennt ihr ein anderes Konzept?

Viele Grüße

 

[Kugelfisch]

Sofern das lediglich für einzelne Bytes (d.h. 7-Bit-ASCII-Zeichen oder Zeichen in einer Legacy-Kodierung wie z.B. ISO-8859-1) benötigst, wäre der einfachste Ansatz, in einer aufsteigenden Schleife über alle möglichen Byte-Werte (0-255) jeweils alle Bytes des aktuellen Werts im String zu suchen (d.h. es werden erst alle 0x00-Bytes gesucht, dann alle 0x01, ..., alle `A`, ..., alle `Z`, ..., alle `a`, usw.).

Beispielcode:
[src=java]import java.util.List;
import java.util.Vector;

public class Test {
private static List<Integer> sortString(String s) {
Vector<Integer> sorted = new Vector<Integer>();
for(char c=0; c<=0xFF; c++)
for(int i=0; i<s.length(); i++)
if(s.charAt(i) == c)
sorted.add(i);

return sorted;
}

public static void main(String[] a) {
List<Integer> sorted = sortString(a[0]);
for(int i=0; i<sorted.size(); i++)
System.out.printf("%d ", sorted.get(i));
System.out.println();
}
}[/src]
Ausgabe:

$ javac Test.java && java Test AUTOHAUS
0 5 4 3 7 2 1 6

Dieser Ansatz ist nicht nur einfacher als deiner, sondern bei längeren Strings auch deutlich effizienter, da die Laufzeit O in Bezug auf die String-Länge beträgt.

Sofern du alle im String enthaltenen Unicode-Zeichen nach ihrem Codepoint sortieren möchtest, wird dieser einfache Ansatz natürlich nicht funktionieren, da eine Schleife über alle 0x200000 möglichen Unicode-Codepoints wenig sinnvoll wäre; dann würde sich anbieten, eine HashMap von Unicode-Codepoints zu deren Position(en) im String zu erstellen, und diese am Ende nach Keys sortiert zurückzugeben. Alternativ liesse sich eine PriorityQueue mit eigenen Objekten und einem eigenen Comparator nutzen.

 

[feuerteufel]

Hallo kugelfisch,
Danke für deine - wie immer - sehr kompetente Antwort.
Ist dein Beispiel auch noch dann effizienter, wenn es sich bei der Eingabe nur um ein einzelnes Wort aus kleinen Buchstaben handelt?
Denn darauf wird die Eingabe beschränkt sein. Und ich weiß nicht ob es Sinn macht die Eingabe über die ganzen möglichen Byte Werte zu durchsuchen.

 

[Kugelfisch]

Ist dein Beispiel auch noch dann effizienter, wenn es sich bei der Eingabe nur um ein einzelnes Wort aus kleinen Buchstaben handelt?

Das hängt (vergleich mit deinem Ansatz, dessen Laufzeit mit O(n^2) skaliert) von der Länge des Strings ab. Bei langen Strings (> 255 Zeichen) ist er in jedem Fall effizienter; bei kürzeren Strings nicht, dann ist die Laufzeit auf aktuellen Systemen allerdings ohnehin vernachlässigbar klein.

Wenn du im Voraus weisst, dass nur Kleinbuchstaben zu berücksichtigen sind, kannst du den Suchbereich (äusserste Schleife) natürlich auch einschränken:
[src=java]for(char c='a'; c<='z'; c++)[/src]


Der Unterschied ist bei einer einmaligen Ausführung jedoch auf einem aktuellen System kaum messbar. Auf meinem System beträgt die Laufzeit für die Eingabe `autohaus` ~80ms, wobei der grösste Teil für die Initialisierung der Java-VM verwendet wird. Die Laufzeit des eigentlichen Codes dürfte eher im Bereich von Millisekunden liegen.

Suche bloss über 'a'-'z':

$ time java Test autohaus
0 5 4 3 7 2 1 6 

real	0m0.085s
user	0m0.070s
sys	0m0.021s

Suche über 0x00-0xFF:

$ time java Test autohaus
0 5 4 3 7 2 1 6 

real	0m0.086s
user	0m0.074s
sys	0m0.020s

 

[feuerteufel]

Okay, perfekt. Dankeschön
Das mit dem Anpassen war mein Fehler, sorry. Hätte da noch etwas genauer überlegen sollen.

Ich werde es dann gleich implementieren. Sollte es Probleme geben, melde ich mich nochmal. Davon gehe ich aber nicht aus.

EDIT:
Funktioniert. Habe es jetzt auch nachvollzogen. Rückblickend betrachtet habe ich zu kompliziert gedacht.

 

[accC]

Wie wäre es mit
[src=java]
HashMap<Char, List<Integer>> m = new HashMap<Char, List<Integer>>();
for(int i=0; i<str.length(); i++){
if(m.get(str.charAt(i)) == null){
List<Integer> l = new LinkedList<Integer>();
l.add(i);
m.put(str.charAt(i), l);
}else{
m.get(str.charAt(i)).add(i);
}
}
[/src]

Wenn dir die Buchstaben im Voraus bekannt sind und/oder du eine Reihenfolge erzwingen willst, kannst du auch die Map einmal mit einer leeren Liste für jeden Buchstaben vorinitialisieren.

[src=java]HashMap<Char, List<Integer>> m = new HashMap<Char, List<Integer>>();
String myChars = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ01234564789 ";
for(int i=0; i<str.length(); i++){
m.put(str.charAt(i), new LinkedList<Integer>());
}[/src]

Vorteil ist, dass automatisch nur die Buchstaben erfasst werden, die auch im Text vorkommen und dass du keine verschachtelten Schleifen verwendest.
Bei Kugelfisch hast du "Anzahl der (potentiell) zu erfassenden Zeichen * Länge des Strings" Schleifendurchläufe. Bei mir wäre es immerhin im oberen Fall "Lände des Strings". Allerdings weiß ich jetzt nicht unbedingt, wie sich HashMap und LinkedList auf die Geschwindigkeit auswirken.

 

[Kugelfisch]

Das hatte ich ja als Alternative erwähnt, wenn man beliebige Unicode-Zeichen korrekt behandeln möchte, da eine Schleife über 0x20000000 mögliche Unicode-Codepoints wenig effizient wäre. Für den angedachten Anwendungsfall (a-z als mögliche Zeichen, einzelne Wörter als Eingabe) ist die Frage nach der Laufzeit aber ohnehin eher theoretischer Natur - das Initialisieren der VM und das Laden der Imports dauert um Grössenordnungen länger als das Ausführen des eigentlichen Codes.

Vorteil ist, dass automatisch nur die Buchstaben erfasst werden, die auch im Text vorkommen und dass du keine verschachtelten Schleifen verwendest.

Allerdings ist die HashMap dadurch noch nicht sortiert. Insbesondere ist gemäss Dokumentation (vgl. http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html) nicht garantiert, in welcher Reihenfolge die Items ausgelesen werden, wenn darauf zugegriffen wird:

Hash table based implementation of the Map interface. [...] This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Deshalb hilft auch die Initialisierung mit leeren Listen nichts.

Entweder müsste man für diesen Ansatz eine LinkedHashMap verwenden und diese mit der gewünschten Reihenfolge initialisieren, oder die Keys am Ende explizit sortieren und dann darüber iterieren, um die Positionen aus der HashMap auszulesen und in die am Ende gewünschte Liste zu schreiben.

 

[accC]

Stimmt, das ist mir gestern, nachdem ich mich hingelegt hatte, auch gekommen.
Allerdings gibt es auch noch die LinkedHashMap, die wiederum sortiert ist.
Entsprechend müsste im obigen Code von mir HashMap durch LinkedHashMap ersetzt werden.


[src=java]class myMap {
// soll eine Init-Phase stattfinden und auf welche Zeichen soll sich beschränkt werden:
private static boolean checkOnlyPreDefinedChars = false;
private static String collectableChars = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ01234564789 ";


private LinkedHashMap<Char, List<Integer>> mymap = new HashMap<Char, List<Integer>>();

public void init(){
// no init needed
if(checkOnlyPreDefinedChars){return;}
// we want to do the init
for(int i=0; i<str.length(); i++){
collectableChars.put(str.charAt(i), new LinkedList<Integer>());
}
}

private void readStringInit(String str){
for(int i=0; i<str.length(); i++){
if(mymap.get(str.charAt(i)) != null){
mymap.get(str.charAt(i)).add(i);
}
}
}

private void readStringNoInit(String str){
for(int i=0; i<str.length(); i++){
if(mymap.get(str.charAt(i)) != null){
mymap.get(str.charAt(i)).add(i);
}else{
List<Integer> l = new LinkedList<Integer>();
l.add(i);
mymap.put(str.charAt(i), l);
}

}
}

public void read(String str){
if(checkOnlyPreDefinedChars){
readStringInit(str);
}else{
readStringNoInit(str);
}
}

public Map<Char, List<Integer>> getAsMap(){
return mymap;
}
}[/src]

Zuerst .init() und dann .read() aufrufen.
Wobei ich die Initphase intuitiv für vernachlässigbar halte, wenn der verwendete Zeichensatz signifikant kleiner dem potentiell möglichen ist. Also insbesondere bei sehr kurzen Texten.

 

[Kugelfisch]

Wobei ich die Initphase intuitiv für vernachlässigbar halte, wenn der verwendete Zeichensatz signifikant kleiner dem potentiell möglichen ist. Also insbesondere bei sehr kurzen Texten.

Nein, allerdings nicht aus Performance-Gründen, sondern weil die Reihenfolge in einer LinkedHashMap derjenigen beim erstmaligen Einfügen entspricht (Insertion-Order). Initialisierst du die LinkedHashMap nicht (oder verwendest stattdessen eine HashMap), müsstest du die Keys am Ende explizit sortieren, ansonsten entspricht die Reihenfolge derjenigen des ersten Auftretens im String (nicht initialisierte LinkedHashMap) oder ist komplett undefiniert (HashMap).

 

[accC]

Naja stimmt, allerdings kannst du ja sowieso implizit sortiert aus der Map rausfragen..