String Methode für längste Sequenz von Leerzeichen

[ocsme]

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

 

[Meniskusschaden]

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.

 

[mrBrown]

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.

Den Fall kannst du ganz einfach abfangen, indem du prüfst, ob an der Schnittstelle ein Leerzeichen sitzt

 

[ocsme]

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.

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

 

[mrBrown]

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

Einfach mit dem char ' '

 

[Meniskusschaden]

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!

Der zweite String ist ja auch länger als der erste (zumindest, wenn die Wörter gleich lang sind).

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.

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.

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!

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.

 

[ocsme]

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

 

[Meniskusschaden]

Also im Klartext was soll ich nun tun?

Das musst du selbst entscheiden.

Hat jemand eine Idee?

Ja, siehe Post #2.

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.

Ich verspreche mir nicht allzu viel davon, will es aber auch nicht ausschließen. Wie soll der Algorithmus denn prinzipiell arbeiten?

Oder wie war das mit dem Naiven Umsatz was meintest du damit?

Damit meine ich den Vorschlag aus Post #2.

 

[ocsme]

So hat das einer aus meiner Gruppe gemacht.
Ich hab es nicht hin bekommen :-(

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

 

[Meniskusschaden]

So hat das einer aus meiner Gruppe gemacht.

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.

 

[mrBrown]

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

 

[Blender3D]

Hier eine binäre rekursive Suchvariante. Beim Start muss max = 0 sein.

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;
    }

 

[Meniskusschaden]

Hier eine binäre rekursive Suchvariante.

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.

 

[Blender3D]

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.

Bin hier ganz Deiner Meinung.

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.

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.

 

[mrBrown]

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.

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.

 

[Blender3D]

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.

 

[mrBrown]

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.

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

 

[ocsme]

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

 

[Blender3D]

Die du dafür 25 mal untersuchen musst

Wenn kein Leerzeichen gefunden wird --> der String wird sofort verkürzt. Falls doch wird untersucht. Eine Zeichenkette die kürzer als das bisherige Maximum ist wird ebenfalls nicht mehr untersucht.

 

[mrBrown]

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

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?

 

[ocsme]

Hey ich wollte das so machen:

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.

 

[Meniskusschaden]

Wer rät, welches welche Variante ist?

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]

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.

Sobald man das erste Leerzeichen findet, kann man ja auch in Zweiersprüngen weiter machen. Ist es das, was du meinst? Ich verstehe dein Posting nicht wirklich.

 

[mrBrown]

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.

Er sucht schon in der Mitte zuerst - die beiden Schleife die nach Links/Rechts laufen

 

[ocsme]

Sobald man das erste Leerzeichen findet, kann man ja auch in Zweiersprüngen weiter machen. Ist es das, was du meinst? Ich verstehe dein Posting nicht wirklich.

Genau das ist das was ich meine doch wie soll ich denn in der if abfrage dann aus dem einen Leerzeichen zwei machen?
Oh man!

 

[Meniskusschaden]

Er sucht schon in der Mitte zuerst - die beiden Schleife die nach Links/Rechts laufen

Stimmt. Da habe ich Unfug geschrieben.

Genau das ist das was ich meine doch wie soll ich denn in der if abfrage dann aus dem einen Leerzeichen zwei machen?

Wofür brauchst du die denn? Du kannst doch auch zwei Zeichen weiter springen, ohne einen solchen "Zwei-Leerzeichen-String" zu haben.

 

[ocsme]

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]

was ist eigentlich isSpace? das finde ich nicht soll das eine Methode sein für String? Wo findet man die?

Das ist eine selbst geschriebene Methode, die macht nicht mehr als zu prüfen, oder der Character ein Space ist.

 

[Blender3D]

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

Stimmt: Habe die linke Grenze nicht berücksichtigt.
Hier die verbesserte Variante

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;
    }

 

[ocsme]

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!

 

[mrBrown]

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?

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.

 

[Meniskusschaden]

Angenommen:
" a b c d "

Da sind offenbar die doppelten Leerzeichen verloren gegangen, so daß das Beispiel nicht mehr zur Erklärung passt. Wahrscheinlich sollte es ungefähr so aussehen:

" a b  c  d "

 

[ocsme]

Okay Danke dann verstehe ich den Code nicht mal

naja

 

[mrBrown]

Da sind offenbar die doppelten Leerzeichen verloren gegangen, so daß das Beispiel nicht mehr zur Erklärung passt. Wahrscheinlich sollte es ungefähr so aussehen:

Jap, sollte es, danke

Ich bin naiverweise davon ausgegangen, dass auch inline-code nicht umformatiert wird...

 

[ocsme]

Was meinst du eigentlich mit int max?

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?

 

[mrBrown]

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