String Methode für längste Sequenz von Leerzeichen

O

ocsme

Top Contributor
Guten Tag,

ich sitze hier schon seit ein paar Tagen vor einem Problem. Hier mal die genaue Fragestellung die wir beantworten sollen:

Schreiben Sie eine effiziente Methode, die die Länge der längsten Sequenz von
Leerzeichen in einem gegebenen String sucht und dabei möglichst wenig Zeichen im
String untersucht (Hinweis: Das Programm sollte schneller werden, wenn die Länge
der Sequenz von Leerzeichen zunimmt). Geben Sie außerdem die Zahl der
benötigten Vergleiche aus.

Nun hab ich zu unseren Tutors gesagt das man durch den ganzen String wandern muss und er meinte Brauch man das wirklich?
Denn wenn ich ein String hab mit 10 Wörtern und 3 Leerzeichen am ende dann soll die Methode schneller werden wenn ich wieder 10 Wörter habe und 100 Leerzeichen am Ende doch wie soll das gehen ohne durch den ganzen String zu wandern?
Ihn aufzuteilen wie bei Binärersuche ist auch eher Fragwürdig denn dann könnte der Worst-Case passieren und man Teilt an der längsten stelle der Leerzeichen etc.!!! Also auch eher Fragwürdig.

Nun bin ich einfach hin gegangen und benutze die Klasse StringTokenizer doch durch das einfügen von Leerzeichen wird die Methode ja nicht schneller sondern es kommt ja nur auf die Anzahl der Worte im String an.

Hat da jemand eine Idee? Ich stehe auf dem Schlauch 😀

LG
 
ocsme hat gesagt.:
Ihn aufzuteilen wie bei Binärersuche ist auch eher Fragwürdig denn dann könnte der Worst-Case passieren und man Teilt an der längsten stelle der Leerzeichen etc.!!! Also auch eher Fragwürdig.
Zum Vergrößern anklicken....
Den Fall kannst du ganz einfach abfangen, indem du prüfst, ob an der Schnittstelle ein Leerzeichen sitzt 😉
 
Meniskusschaden hat gesagt.:
Je größer die bereits gefundene größte Sequenz wird, desto größer kannst du die Schrittweite wählen, mit der du im String weiter springst.
Zum Vergrößern anklicken....

Ja doch das Problem hierbei ist ja das wenn ich 10 Wörter habe und 3 Leerzeichen ist das Programm immer noch schneller als wenn ich 10 Wörter habe und 500 Leerzeichen am ende!
In der Aufgabenstellung hab ich das halt jetzt so verstanden das es beim 2ten schneller gehen soll als beim ersten. Das bedeutet der counter der durchläuft wäre geringer als beim nächsten.
Des weiteren kann man die suche nach Leerzeichen immer nur um 1 Plus rechnen! Dann springt er immer um 2 dann 3 stelle drüber doch auch was ist wenn er dann springt und es kommt nur ein Buchstabe und 2 Leerzeichen springt also über die 2 Leerzeichen und danach kommen wieder 3 Leerzeichen dann speichert er nur die 3 Leerzeichen und nicht die 5!
Also so wäre es für mich logisch es gibt da sicher irgendwelche Tricks doch wir spielen ja immer noch nur rum 😀 deswegen 😀

Wie Prüfe ich denn ob das wo er Teilen soll ein Leerzeichen ist? einfach mit dem char 32? oder gibt es eine Methode die es leichter macht 😀

LG
 
ocsme hat gesagt.:
Ja doch das Problem hierbei ist ja das wenn ich 10 Wörter habe und 3 Leerzeichen ist das Programm immer noch schneller als wenn ich 10 Wörter habe und 500 Leerzeichen am ende!
Zum Vergrößern anklicken....
Der zweite String ist ja auch länger als der erste (zumindest, wenn die Wörter gleich lang sind).
ocsme hat gesagt.:
In der Aufgabenstellung hab ich das halt jetzt so verstanden das es beim 2ten schneller gehen soll als beim ersten. Das bedeutet der counter der durchläuft wäre geringer als beim nächsten.
Zum Vergrößern anklicken....
Ich verstehe es so, dass die Suche mit jeder gefundenen Sequenzverlängerung schneller werden soll. Grundsätzlich tut mein Vorschlag das auch. Es stimmt aber, dass er nicht mehr von der Sequenz am Ende des Strings profitiert. Das ist hier (fast) der worst case. Trotzdem beschleunigt er nach dem gefundenen Leerzeichen zwischen den ersten beiden Wörtern.
Ich glaube aber nicht, dass die Aufgabenstellung so gemeint ist, dass das auch im worst case funktionieren muß. Angenommen der String enthält nur Leerzeichen. Dann wirst du mit jedem Algorithmus jedes Zeichen überprüfen müssen und bist somit langsamer als bei Strings, die Buchstaben und Leerzeichen enthalten. Dasselbe gilt, wenn der String überhaupt kein Leerzeichen enthält.
ocsme hat gesagt.:
Des weiteren kann man die suche nach Leerzeichen immer nur um 1 Plus rechnen! Dann springt er immer um 2 dann 3 stelle drüber doch auch was ist wenn er dann springt und es kommt nur ein Buchstabe und 2 Leerzeichen springt also über die 2 Leerzeichen und danach kommen wieder 3 Leerzeichen dann speichert er nur die 3 Leerzeichen und nicht die 5!
Zum Vergrößern anklicken....
Wenn du nach einem Sprung auf ein Leerzeichen triffst, musst du natürlich überprüfen, ob die übersprungenen Zeichen auch Leerzeichen waren. Wenn es aber kein Leerzeichen war, kannst du weiter springen.

Meines Erachtens liegt das Optimierungspotential darin, dass durch gefundene "Nicht-Leerzeichen" Teile des Strings nicht mehr untersucht werden müssen. Mein Vorschlag ist wahrscheinlich die naivste Umsetzung dafür. Vielleicht geht das mit einem geschickten Divide&Conquer-Verfahren im Durchschnitt effizienter. Im worst case wird man aber jedes Zeichen prüfen müssen.
 
So also danke für die Antworten jetzt weiß ich leider aber überhaupt nicht mehr was ich tun soll 😀
und da reden die doch immer von Eindeutigkeit 😀 so eine Übung ist sehr eindeutig zu verstehen 😀

Also im Klartext was soll ich nun tun? Hat jemand eine Idee? Das mit dem Divide&Conquer-Verfahren mit Prüfung auf Leerzeichen beim Teilen finde ich an sich eine gute Idee 🙂 denke zwar das ich es nicht hin bekomme aber mal sehen. Oder wie war das mit dem Naiven Umsatz was meintest du damit?
LG
 
ocsme hat gesagt.:
Also im Klartext was soll ich nun tun?
Zum Vergrößern anklicken....
Das musst du selbst entscheiden.
ocsme hat gesagt.:
Hat jemand eine Idee?
Zum Vergrößern anklicken....
Ja, siehe Post #2.
ocsme hat gesagt.:
Das mit dem Divide&Conquer-Verfahren mit Prüfung auf Leerzeichen beim Teilen finde ich an sich eine gute Idee 🙂 denke zwar das ich es nicht hin bekomme aber mal sehen.
Zum Vergrößern anklicken....
Ich verspreche mir nicht allzu viel davon, will es aber auch nicht ausschließen. Wie soll der Algorithmus denn prinzipiell arbeiten?
ocsme hat gesagt.:
Oder wie war das mit dem Naiven Umsatz was meintest du damit?
Zum Vergrößern anklicken....
Damit meine ich den Vorschlag aus Post #2.
 
So hat das einer aus meiner Gruppe gemacht.
Ich hab es nicht hin bekommen :-(

Java: 
import java.util.Scanner;
public class Leerzeichensequenz {
    public static void main(String[]args){
        Scanner in = new Scanner(System.in);
        String text = "";
        String s = " ";
        int max=0,index1=0,index2=0;
        text = in.nextLine();
        int counter=0;
       
        while(index1 !=-1){
            index2=index1;
             index1 = text.indexOf(s);
             s=s+" ";
             if(index1 !=-1)
                 max++;
             counter++;
        }
        System.out.println(max +" Leerzeichen ab dem "+(index2+1)+" zeichen. "+counter+" durchl\u00E4ufe");
        //System.out.println(text);
        in.close();
    }
}

Gibt es verbesserungsvorschläge 🙄 Wie gesagt ich hab es ja selber nicht hin bekommen zu blöde😡
 
ocsme hat gesagt.:
So hat das einer aus meiner Gruppe gemacht.
Zum Vergrößern anklicken....
Das dürfte langsamer sein, als den String einfach ohne jegliche Optimierung einmal von vorne bis hinten zu durchlaufen. Die Methode indexOf() liefert ihr Ergebnis ja nicht "einfach so", sondern geht den String ebenfalls zeichenweise durch. Bei dieser Lösung werden die String-Abschnitte also mehrfach durchlaufen. Je weiter vorne ein Wort steht, desto häufiger wird es verarbeitet.
 
Also mit so viel Trickserei bekommt man das noch besser hin - einfach mit einem regulären Ausdruck greedy auf Leerzeichen matchen.

Wäre dann ein Durchlauf.


Müsste ich es bewerten gäbs aber nur nen Punkt für die Trickserei, aber keine für die Aufgabe 😀
 
Hier eine binäre rekursive Suchvariante. Beim Start muss max = 0 sein.
Code: 
public static int maxSpaceInTxt(String text, int max) {
        int len = text.length();
        if (len == 0 || len < max) // length < max --> stop search
            return max;
        if (len == 1)
            return (text.charAt(0) == ' ') ? 1 : 0;
        int idLeft = len / 2;
        int idRight = idLeft + 1;

        while (idLeft > 0 && text.charAt(idLeft) == ' ')
            idLeft--;
        while (idRight < len && text.charAt(idRight) == ' ')
            idRight++;
        int spcLen = idRight - idLeft - 1;
        spcLen = maxSpaceInTxt(text.substring(0, idLeft), spcLen > max ? spcLen : max);
        spcLen = maxSpaceInTxt(text.substring(idRight, len), spcLen > max ? spcLen : max);
        return spcLen > max ? spcLen : max;
    }
 
Blender3D hat gesagt.:
Hier eine binäre rekursive Suchvariante.
Zum Vergrößern anklicken....
Das sieht gut aus. Bei zwei Punkten bin ich mir allerdings noch nicht so sicher. Da sind einmal die den substring()-Operationen innewohnenden Stringkopien, die das Ganze wieder ausbremsen. Das wäre aber wohl kein prinzipielles Problem, sondern nur ein Implementierungsdetail, weil man es ja sicher so abwandeln könnte, dass komplett auf dem Originalstring gearbeitet wird. So wie es jetzt ist, ist die Idee aber bestimmt viel leichter zu erkennen.

Bei der grundsätzlichen Laufzeitabschätzung bin ich mir auch nicht so sicher, ob es viel bringt. Wenn es eine sehr lange Sequenz gibt (z.B. ca. die Hälfte des Strings), benötigt deren Verarbeitung ja schon einen Großteil der Zeit. Wenn die längste Sequenz nicht so lang ist (z.B. zehn Zeichen in einem 1000-Zeichen-String) ist es ja Glückssache, ob man sie früh oder spät findet, also auch, ob man viele oder nur noch wenige rekursive Aufrufe einsparen kann. Ich denke schon, dass es schneller läuft, als mein naiver Vorschlag aus #2, bin mir aber noch nicht ganz sicher, ob es auch asymptotisch schneller ist.
 
Meniskusschaden hat gesagt.:
Das sieht gut aus. Bei zwei Punkten bin ich mir allerdings noch nicht so sicher. Da sind einmal die den substring()-Operationen innewohnenden Stringkopien, die das Ganze wieder ausbremsen. Das wäre aber wohl kein prinzipielles Problem, sondern nur ein Implementierungsdetail, weil man es ja sicher so abwandeln könnte, dass komplett auf dem Originalstring gearbeitet wird. So wie es jetzt ist, ist die Idee aber bestimmt viel leichter zu erkennen.
Zum Vergrößern anklicken....
Bin hier ganz Deiner Meinung.
Meniskusschaden hat gesagt.:
Bei der grundsätzlichen Laufzeitabschätzung bin ich mir auch nicht so sicher, ob es viel bringt. Wenn es eine sehr lange Sequenz gibt (z.B. ca. die Hälfte des Strings), benötigt deren Verarbeitung ja schon einen Großteil der Zeit.
Zum Vergrößern anklicken....
Eine lange Sequenz braucht immer linear die gleiche Zeit, da zum Zählen alle Leerzeichen durchlaufen werden.
Die binäre Suche findet die Sequenz schneller, da hier ein logarithmisches Wachstum stattfindet.
🙄
 
Blender3D hat gesagt.:
Eine lange Sequenz braucht immer linear die gleiche Zeit, da zum Zählen alle Leerzeichen durchlaufen werden.
Die binäre Suche findet die Sequenz schneller, da hier ein logarithmisches Wachstum stattfindet.
🙄
Zum Vergrößern anklicken....
Bist du da sicher?
Spontan würde ich sagen, in diesem Fall läuft beides aufs gleiche hinaus...

Die "binäre Suche" macht hier auch nichts anderes, als nur Stücke größer als die bisher gefundene Sequenz zu untersuchen, fängt halt in der Mitte anstatt vorne an.
 
Bei einem z.B. 1000 Zeichen langen String haben sich die zu untersuchenden Zeichenketten nach 9 Schritten bereits auf eine Länge von circa 4 Zeichen reduziert.
 
Blender3D hat gesagt.:
Bei einem z.B. 1000 Zeichen langen String haben sich die zu untersuchenden Zeichenketten nach 9 Schritten bereits auf eine Länge von circa 4 Zeichen reduziert.
Zum Vergrößern anklicken....
Die du dafür 25 mal untersuchen musst 😉

Es gibt in dem Fall nicht wie bei der üblichen binären Suche ein entweder rechts oder links (weshalb die Bezeichnung als "binäre Suche" vermutlich nicht ganz richtig ist).
 
das ist mir viel zu kompliziert.
Das werde ich also sein lassen!
Danke für eure Antworten. Auf die Aufgabe gibt es 3 Punkte auf die kann ich auch gut verzichten!

LG
 
Deine Variante liefert btw für Leerzeichen am Anfang des Strings falsche Ergebnisse.

Ja, ich weiß das der String verkürzt wird - implizit wird das bei @Meniskusschaden Variante aber auch gemacht, durch das überspringen. Die größten Vorteile entstehen durch die Position der Leerzeichen

Java: 
public static int maxSpaceInTxt(String text) {
        int max = 0;
        int step = 1;
        for (int i = 0; i < text.length(); i += step) {
            if (isSpace(text.charAt(i))) {
                int begin = i - 1;
                int end = i + 1;

                while (begin >= 0 && isSpace(text.charAt(begin))) {
                    begin--;
                }

                while (end < text.length() && isSpace(text.charAt(end))) {
                    end++;
                }

                max = Math.max(max, end - (begin + 1));
                step = Math.max(1, max + 1);
                i = end;
            }
        }
        return max;
    }


Einfach mal die Aufrufe von isSpace zählen lassen:

Für 100 Zeichen und 4 Leerzeichen:
Anfange | Mitte | Ende
72 | 66 | 134
24 | 63 | 101

Für 100 Zeichen und 8 Leerzeichen:
Anfange | Mitte | Ende
36 | 38 | 131
19 |61 | 101

Wer rät, welches welche Variante ist?
 
Hey ich wollte das so machen:

Java: 
String test="Das ist ein Test";
        String leer=" ";
        int testLength=test.length();
        int index=0;
        while(testLength>0)
        {
            if(test.charAt(index)==' ')
               
            index++;
        }

Doch hab jetzt schon das Problem das ich bei if(test.charAt(index)==' ') sobald er ein " " findet das ganze verdoppelt und immer mit zwei Sprüngen weiter macht doch so klappt das nicht.
 
mrBrown hat gesagt.:
Wer rät, welches welche Variante ist?
Zum Vergrößern anklicken....
Ich würde sagen, die zweite Zeile muß jeweils der Algorithmus "Lineares Durchhopsen" sein. Vier Leerzeichen am Anfang sind vier Vergleiche. Die 96 verbleibenden Zeichen werden in Fünfersprüngen verarbeitet. Also kommen noch 96/5 Vergleiche hinzu.

Der Algorithmus von @Blender3D lässt sich vielleicht noch etwas verbessern. Im Moment wird der Leerzeichentest ja erst vorgenommen, wenn Stringlänge 1 erreicht ist. Wenn man sich die rekursiven Aufrufe als Baum vorstellt, muss man also erst bis auf die Blattebene herunter, bevor man das erste Leerzeichen finden kann. Man könnte vielleicht stattdessen zuerst das mittlere Element prüfen, falls es ein Leerzeichen ist, die angrenzenden Leerzeichen hinzufügen und erst dann die verbliebene linke und rechte Restzeichenfolge rekursiv verarbeiten. Dann würde man im Rekursionsbaum auch mal Leerzeichen bei inneren Knoten finden.
 
Meniskusschaden hat gesagt.:
Der Algorithmus von @Blender3D lässt sich vielleicht noch etwas verbessern. Im Moment wird der Leerzeichentest ja erst vorgenommen, wenn Stringlänge 1 erreicht ist. Wenn man sich die rekursiven Aufrufe als Baum vorstellt, muss man also erst bis auf die Blattebene herunter, bevor man das erste Leerzeichen finden kann. Man könnte vielleicht stattdessen zuerst das mittlere Element prüfen, falls es ein Leerzeichen ist, die angrenzenden Leerzeichen hinzufügen und erst dann die verbliebene linke und rechte Restzeichenfolge rekursiv verarbeiten. Dann würde man im Rekursionsbaum auch mal Leerzeichen bei inneren Knoten finden.
Zum Vergrößern anklicken....
Er sucht schon in der Mitte zuerst - die beiden Schleife die nach Links/Rechts laufen 😉
 
ja und das verstehe ich alles nicht wie soll das gehen 😀
Ich steh mal wieder total neber mir! hab das Gefühl das es einfach NIE klappen wird! Dann sollte ich wohl endlich mir selber eingestehen das ich das nicht schaffe und abbrechen!
Nochmals danke!

was ist eigentlich isSpace? das finde ich nicht soll das eine Methode sein für String? Wo findet man die?
 
mrBrown hat gesagt.:
Deine Variante liefert btw für Leerzeichen am Anfang des Strings falsche Ergebnisse.
Zum Vergrößern anklicken....
Stimmt: Habe die linke Grenze nicht berücksichtigt.
Hier die verbesserte Variante
Code: 
public static int maxSpaceInTxt(String text, int max) {
        int len = text.length();
        if (len == 0 || len < max) // length < max --> stop search
            return max;
        if (len == 1)
            return (text.charAt(0) == ' ') ? 1 : 0;
        int idLeft = len / 2;
        int idRight = idLeft + 1;

        while (idLeft > 0 && text.charAt(idLeft) == ' ')
            idLeft--;
        while (idRight < len && text.charAt(idRight) == ' ')
            idRight++;
        int spcLen = idRight - idLeft - ( idLeft == 0 ? 0: 1) ;
        spcLen = maxSpaceInTxt(text.substring(0, idLeft), spcLen > max ? spcLen : max);
        spcLen = maxSpaceInTxt(text.substring(idRight, len), spcLen > max ? spcLen : max);
        return spcLen > max ? spcLen : max;
    }
 
Ich hab mir das ganze mal aufgezeichnet und festgestellt Funktioniert das überhaupt so richtig?

Denn nehmen wir mal ein Beispiel Satz: Ein" "Satz" "" "" "" "" "als" "Beispiel würde er dann nicht bis zum ersten " " < Leerzeichen vorrücken danach dann immer in 2er Sprünge weiter doch dann ist er ja schon über ein " " Leerzeichen gesprungen macht das ganze überhaupt so Sinn?

Ah hab mich schon gewundert über die Methode 😀 also ich verstehe es aber trozdem nicht wie gesagt sie beispiel oben das ist mir einfach zu hoch!
 
ocsme hat gesagt.:
Denn nehmen wir mal ein Beispiel Satz: Ein" "Satz" "" "" "" "" "als" "Beispiel würde er dann nicht bis zum ersten " " < Leerzeichen vorrücken danach dann immer in 2er Sprünge weiter doch dann ist er ja schon über ein " " Leerzeichen gesprungen macht das ganze überhaupt so Sinn?
Zum Vergrößern anklicken....
Nein, wenn er die erste Sequenz Leerzeichen gefunden hat, die hier eins ist, springt immer zwei weiter.
Er kann also maximal ein einzelnes Leerzeichen übersehen, was ja egal ist, weil es ja eine Sequenz mit Länge 1 schon gefunden wurde.
Trifft er auf ein Leerzeichen, prüft er die übersprungenen Felder davor auch noch.


Angenommen:
" a b c d "
er findet das erste Leerzeichen und dann das 'a'. Weil die Sequenz Länge eins hat, springt er dann zwei weiter, prüft also das 'b' als nächstes.
Von dem 'b' springt er dann zum letzten Leerzeichen. Da das ein Leerzeichen ist, prüft er wie viele direkt davor und danach sind, und findet eine Sequenz der Länge 2. Springt also jetzt 3 weiter.
Von dem 'c' landet er dann beim 'd', hat dabei zwei Leerzeichen übersprungen, die aber egal sind, weil Länge 2 ja schon das aktuelle Maximum ist.
von dem 'd' springt er dann ans Ende, das letzte Leerzeichen ist ja auch egal, weil es wieder maximal zwei sein könnten, und zwei ja schon übersprungen wurden.
 
Was meinst du eigentlich mit int max?

Java: 
public static int maxSpaceInTxt(String text, int max) {
        int len = text.length();
        if (len == 0 || len < max) // length < max --> stop search
            return max;

Kann mir das noch jemand erklären? Ich wollte doch eigentlich nur einen String mit geben und wozu brauch ich dann ein Max?
 
max ist die Länge der bisher gefundenen längsten Sequenz, damit wird rausgesprungen, wenn der zu untersuchende Teilstrich kürzer ist, als das bisher gefundene längste Stück
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Längste Sequenz gleicher Int Werte
Antworten: 22
String-Collection: längste gemeinsame Strings / Prefixe
Antworten: 3
Wie finde ich die längste Spalte der DB heraus
Antworten: 2
Längste Reihe anzeigen lassen
Antworten: 11
Plateau auslesen und längste Ebene ausgeben
Antworten: 5

Zurück
Oben