Palindrome aus Sätzen filtern

[lostmaster]

Hallo liebe Community,

ich möchte mich zunächst einmal vorstellen. Ich bin Informatikstudent, jedoch leider mit sehr geringem Wissen sowie Erfahrung im Programmieren ausgestattet . (Meine Stärken liegen eher in der Mathematik).
Sei´s drum. Ich habe eine Aufgabe gestellt bekommen an der ich am verzweifeln bin. Und zwar folgende:


Aufgabentext:

Palindrome sind Wörter, die vorwärts und
rückwärts gelesen genau die gleiche Buchstabenfolge ergeben. Beispiele: Otto, Reittier
oder Rentner
Implementieren Sie folgenden Methode die prüft, ob ein übergebener String ein Palindrom
ist, oder nicht. Die Groß/Kleinschreibung soll dabei ignoriert werden. Die Klassen
String und ggf. Character stellen alle Methoden bereit, die Sie dafür benötigen.

public s tat ic boolean isPalindrome ( St r ing pWord ) ;

Testen Sie diese Methode zunächst in dem es für das Programm Palindrome verwenden.
Das Programm prüft alle Wörter die beim Programmstart als Parameter übergeben
werden darauf, ob sie ein Palindrom sind. Jeder Parametereintrag im statischen String-
Array wird dabei als separates Wort interpretiert. Das Programm gibt die erkannten
Palindrome auf der Konsole aus.

Beispielaufruf:
java -jar palindrome.jar Das Reittier wirft Otto ab
Ausgabe:
Reittier
Otto

Zunächst einmal: Ja ich habe die Suche im Forum verwendet, aber leider keine hilfreichenden Threads gefunden, die mir geholfen hätten, dass spezifische Problem so zu lösen, auch wenn es schon Themen über "Palindrome" gibt


So, nun habe ich mich also daran versucht und folgenden Code erstellt. Ich kann mir gut vorstellen, dass der ein oder andere sich die Hände vor den Kopf schlagen wird, aber wie eingangs erläutert sind meine Kenntnisse noch sehr begrenzt auch wenn ich mich stets um eine Besserung selbiger bemühe.


Hier mein Code:

import java.util.Scanner;

public class Palindrome {
	public static boolean main(String args[]){
	boolean isPalindrome = true;
	
	String input = new Scanner(System.in);
	System.out.println(input);


	int i = 0;
	int j = input.length();{
	
		
		if (j > 0){
	
			while (i<j && isPalindrome){
				if(input.charAt(i) == input.charAt(j)){
					++i;
					--j;
					isPalindrome = true;
				}
			else {
				isPalindrome = false;}
			}
		}
		else{
			isPalindrome = true;
		}
		return isPalindrome;
		}
	}
}

Ich wäre wirklich sehr dankbar über jegliche Hilfe. Es würde mir auch sehr helfen wenn mir jmd. eine Art Struktur geben könnte die ich abarbeiten könnte, um das Problem zu lösen.

Vielen, vielen Dank

lostmaster


Hinzufügend:

Ich habe mir das grundsätzlich so gedacht.

1. Eingabe: (Bsp: Otto ist ein Rentner)
2. alles zu kleinbuchstaben machen
3. zerlegen in einzelne Parametereingaben und speichern in statischen String Array, sodas seperate Wörter gespeichert sind
4. prüfen ob palindrom mit for-schleife vergleichen von erstem buchstaben index= 0 und letztem index = length --> bis mitte (length/2)
5. Ausgabe: Otto, Renter
- ggf.: "Es sind keine Palindrome im eingegebenen Text vorhanden."

Ist diese Herangehensweise soweit richtig oder fehlt etwas?

danke

 

[.Buh]

öhm bei der while schleife musst du nicht immer wieder isPalindrome = true; schreiben

sonst siehts richtig aus wo ist denn genau dein problem / die frage

(bei mir würdes so aussehen wenn ich die aufgabe richtig verstehe bin aber auch recht neu mit Java)

....
boolean isPalindrome = false;
String[] alleWorter = input.split(" ");


 for(int i = 0; i < alleWorter.length())
 {
   String neuesWort = "";
    for(int x = alleWorter[i].length() ; x > 0; x--)
    {
        neuesWort += alleWorter[i].charAt(x);
     }
    if(alleWorter[i].equalsIgnoreCase(neuesWort))
    {
      System.out.println(neuesWort);
      isPalindrome = true;
    }

 }
 if(isPalindrome == false)
   {
     System.out.println("Es sind keine Palindrome im eingegebenen Text vorhanden.");
   }
}

wäre meine Lösung , aber wie gesagt bin selber neu mit jave
(enthält vielleicht nen fehler, ist aus dem kopf geschrieben und kenne mich nicht so gut mit Consolen input aus habe einfach mal Input als String genommen)

 

[lostmaster]

Stimmt die Fehlermeldung hätte ich vielleicht noch hinzufügen sollen^^

Fehler:
Hauptmethode muss einen Wert vom Typ void in Klasse Palindrome zurückgeben. Definieren Sie
die Hauptmethode als:

public static void main(String[] args)

Das ist sie, und ich verstehe es nicht ganz, denn wenn ich in meiner Code-Zeile 4 ein "void" noch hinzufüge entstehen an anderer Stelle mehrere neue Fehler. ???:L

 

[.Buh]

Stimmt die Fehlermeldung hätte ich vielleicht noch hinzufügen sollen^^

Fehler:
Hauptmethode muss einen Wert vom Typ void in Klasse Palindrome zurückgeben. Definieren Sie
die Hauptmethode als:

public static void main(String[] args)

Das ist sie, und ich verstehe es nicht ganz, denn wenn ich in meiner Code-Zeile 4 ein "void" noch hinzufüge entstehen an anderer Stelle mehrere neue Fehler. ???:L

die main methode muss so aussehen

	public static void main(String[] args) {
	

	}

und du musst am ende das

return isPalindrome;

löschen

 

[lostmaster]

Habs ausprobiert, jetzt kommt folgende Fehlermeldung:

Exception in thread "main" java.lang.Error: Unresolved compilation problem:
Type mismatch: cannot convert from Scanner to String

at Palindrome.main(Palindrome.java:7)


Hier nochmal der korrigierte Gesamtcode. Nicht das ich irgendwo jetzt einen Fehler habe

import java.util.Scanner;

public class Palindrome {
	public static void main(String[] args) {
	boolean isPalindrome = true;
	
	String input = new Scanner(System.in);
	System.out.println(input);


	int i = 0;
	int j = input.length();{
	
		
		if (j > 0){
	
			while (i<j && isPalindrome){
				if(input.charAt(i) == input.charAt(j)){
					++i;
					--j;
					isPalindrome = true;
				}
			else {
				isPalindrome = false;}
			}
		}
		else{
			isPalindrome = true;
		}
	}
	}
}

 

[lostmaster]

Ohne den Ansatz von eben zu verwerfen hab ich mich nochmal komplett neu auf das Projekt gestürzt dabei bin ich insgesamt jetzt soweit gekommen:

import java.util.Scanner;

public class Palindrom 
{
	public static void main(String[] args) 
	{
	
		
		System.out.println("Bitte geben sie hier ihren Text ein, welcher darauf getestet, ob selbiger Palindrome enthält: ");
		Scanner scanner = new Scanner(System.in);
		String input = scanner.nextLine();
		System.out.println("Ihr eingegebener Text lautet: " + "\"" + input +  "\"" + " Der Text wird nun auf Palindrome überprüft bitte haben Sie ein wenig Geduld. ");
		input = input.toLowerCase();
		System.out.println("Ihr Text wurde nun in Kleinbuchstaben konvertiert: " + "\"" + input + "\"");
        String[] UsersInput = input.split(" ");
                       int i = 0;
		for (UsersInput[i] = 0 ; i < UsersInput[UsersInput.length - 1]; i++)
        	System.out.println();
	}

}

Ich habe also zunächst einmal eine Eingabe des Benutzers in einem String namens "input" gespeichert. diesen dann mithilfe von input.toLowerCase() in reine Kleinbuchstaben konvertiert und dann über input.split(" ") unter dem Namen "UsersInput" die einzelnen Wörter in einem String-Array gespeichert.

Nun bleibe ich aber hängen, ich müsste im Prinzip die einzelnen Wörter nochmal in einzelne Buchstaben splitten und dann mit Hilfe einer for-schleife durch jedes einzelne Array gehen und den Array-Index 0 mit Array.length vergleichen bis zu length/2 (der Mitte des jeweiligen Wortes) .. sind diese dann immer gleich ist es ein Palindrom und ich kann es ausgeben.

Jetzt meine Problem.

1. Wie kann ich die Wörter nochmals in einzelne Buchstaben splitten und in ein Array abspeichern?
2. Wie kann ich mit einer Schleife die Arrays überprüfen und die Palindrome abspeichern?

Vielen Dank für Antworten


PS: Der Code ist sehr ausführlich und mit Sicherheit sehr umständlich, aber ich habe ihn verstanden und es hilft mir sehr wenn ich jeden einzelnen Schritt zunächst einmal ausführe. Deswegen würde ich diesen Lösungsansatz gerne weiterausführen

 

[jgh]

Variablen schreibt man klein...und dein Code compiliert nicht und schmeißt folgenden Fehler:

for (usersInput[i] = 0; i < usersInput[usersInput.length - 1]; i++)
			System.out.println();

Multiple markers at this line
	- Type mismatch: cannot convert from int to String
	- The operator < is undefined for the argument type(s) 
	 int, String

zu 1) warum willst du das machen...ich behaupte mal, dass ist für die Aufgabe sinnfrei...aber:

	public String[] aufsplittenVonEinzelnenBuchstaben(String string) {
		String[] buchstabenArray = new String[string.length()];
		for (int i = 0; i < buchstabenArray.length; i++) {
			buchstabenArray[i] = String.valueOf(string.charAt(i));
		}
		System.out.println(Arrays.toString(buchstabenArray));
		return buchstabenArray;
	}

zu 2) möglich wäre doch bspw. -wenn du das Buchstabenarray hast- den ersten und letzten Buchstaben zu vergleichen, sind die beide gleich...dann den zweiten und den letzten...usw

hier mal ein Ansatz:

[java=15] String[] usersInput = input.split(" ");
String[] palindrome = new String[usersInput.length];
for (int i = 0; i < usersInput.length; i++) {// erste (äußere) Schleife zum iterieren über das Array usersInput
for (int j = 0; j < usersInput.length() / 2; j++) {// zweite(innere) Schleife zum iterieren über die einzelnen Buchstaben
if (true) {// hier fehlt halt natürlich noch die Bedingung
// dafür, dass es ein Palindrom ist
palindrome = usersInput;
}
}
}
System.out.println("Palindrome: " + Arrays.toString(palindrome));
}
[/code]

 

[Landei]

Ihr wisst schon, dass das Testen ein klein wenig einfacher geht?

public boolean isPalindrom(String str) {
  String s = str.toLowerCase();
  return s.equals(new StringBuilder(s).reverse().toString());
}

 

[hyperflex]

Eine super Übung wie ich finde. Ich habe sie vor kurzem auch gelöst - jedoch eine etwas andere Lösung..

Hoffe das ist okay wenn ich das hier mal hin poste, falls du nicht weiter kommst kannst du ja ein wenig spicken.

Als nächste Übung könntest du ein Hangman programmieren.. Und dann in Richtung OO gehen.
Ich habe "Java ist auch eine Insel" gelesen, anschliessend und parallel ein paar main-Line Programme und bin jetzt bei OO angekommen..

Hoffe das ist der richtige Weg

EDIT:
Code entfernt, da er nicht funktioniert..:autsch:

EDIT2:
Habe den Fehler gesucht - konnte ihn aber nicht finden. Ein Hinweis betreffend meinem Fehler wäre nett. Liegt wohl an der

 && char1 == char2

Bedingung in der while-Schleife.

import java.io.*;

import java.io.InputStreamReader;

public class Mb4a1 {

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        System.out.print("Gib was ein: ");
        String eingabe = br.readLine();

        int laenge = eingabe.length() - 1;
        char char1 = eingabe.charAt(0);
        char char2 = eingabe.charAt(laenge);
        int durchgang = 1;

        if (eingabe.length() == 1) {
            System.out.println(eingabe + " ist ein Palindrom.");
        }
        else {
            while ((eingabe.length() + 1) / 2 > (durchgang - 1) && char1 == char2); {
                char1 = eingabe.charAt(durchgang);
                char2 = eingabe.charAt(--laenge);
                durchgang++;
            }
            if (char1 == char2) {
                System.out.println(eingabe + " ist ein Palindrom.");
            } else {
                System.out.println(eingabe + " ist kein Palindrom.");
            }
        }
    }
}

Danke & Gruss

 

[TryToHelp]

...
Beispielaufruf:
java -jar palindrome.jar Das Reittier wirft Otto ab
Ausgabe:
Reittier
Otto
...

Also wenn ich das richtig sehe, soll aus dem Programmaufruf der Text mit übergeben werden oder Täusche ich mich da?

Was den Code, bzw das einlesen deutlich vereinfacht, es ist schon ein String array getrennt Wort für Wort ;-)

public static void main(String[] args){
  for(Strings s :args){ //garantiere nicht, das das beim array auch geht
    if (isPalindrom(s)){
      System.out.println(s);
    }
  }

}

public boolean isPalindrom(String str) {
  String s = str.toLowerCase();
  return s.equals(new StringBuilder(s).reverse().toString());
}

 

[s4ke]

@Landei: Ich glaube nicht, dass das Sinn der Übung ist .

[snip] War ziemlich doof [/snip]

Fixed:

Oder mit Stack:

import java.util.Stack;

public class Palindrom {

	public static boolean isPalindrom(String pString) {
		int length = pString.length();
		Stack<Character> stack = new Stack<Character>();
		boolean midCheck = length % 2 == 1;
		int mid = Math.round(length / 2);
		for(int i = 0; i < length; ++i) {
			Character current = Character.toLowerCase(pString.charAt(i));
			if(stack.size() > 0 && stack.peek().equals(current)) {
				System.out.println("popped: " + stack.pop());
			} else if(midCheck && i == mid) {
				System.out.println("ignored mid: " + current);
			} else {
				System.out.println("pushed: " +
						stack.push(Character.toLowerCase(current)));
			}
		}
		return stack.size() == 0;
	}

	public static void main(String[] pArgs) {
		System.out.println(isPalindrom("Otto"));
		System.out.println(isPalindrom("Reittier"));
		System.out.println(isPalindrom("Rentner"));
	}

}

Sollte man das benutzen, bitte die System.out.printlns löschen.

 

[lostmaster]

Huhu,
ich bin es nochmal. Ich habe jetzt meinen zweiten Versuch weiterausgearbeitet. Allerdings scheitert es noch an einem entscheidenden Punkt. Und zwar gibt mir das Programm nicht nur die Palindrome zurück sondern alle Wörter des Textes. Ich muss also noch i-eine Bedingung eingeben, aber ich weiß nicht genau wo. Hier der Code:

import java.util.Scanner;

public class Palindrom {

	public static void main (String[] args) 
	{
	
		boolean isPalindrome = false;
				
		System.out.println("Bitte geben sie hier ihren Text ein, welcher darauf getestet, ob selbiger Palindrome enthält: ");
		Scanner scanner = new Scanner(System.in);
		String input = scanner.nextLine();
		System.out.println("Ihr eingegebener Text lautet: " + "\"" + input +  "\"" + " Der Text wird nun auf Palindrome überprüft bitte haben Sie ein wenig Geduld. ");
		input = input.toLowerCase();
		System.out.println("Ihr Text wurde nun in Kleinbuchstaben konvertiert: " + "\"" + input + "\"");
        String[] UsersInput = input.split(" ");
        String reversedinput = input;
        reversedinput = new StringBuffer(input).reverse().toString();
        System.out.println("Dies ist ihr Text rückwärts gelesen: " + reversedinput);
        String[] UsersInputReversed = reversedinput.split(" ");
        
        {
        	int i = 0;
        	int j = UsersInput.length;
        	for(int i1=0; i1<UsersInput.length; i1++) 
        	{
        			for (int j1=0; j1<UsersInputReversed.length; j1++)
        			{
        				if (UsersInput[i1].equals(UsersInputReversed[j1]));
        				{
        					System.out.println(UsersInput[i1]);
        				}
        			}
        	}
        }
	}
}

Habt ihr da eine Lösung wie ich es schaffe das bei dem Durchlauf der for-Schleifen nur die ausgebe die wirklich identisch sind? dachte ich hätte das über .equal. gemacht in Code-Zeile 29.
Vielleicht mit hilfe des oben definierten isPalindrome ?

DAnke

 

[s4ke]

Nur mal so: Du sollst doch laut Aufgabenstellung eine extra Methode zum checken schreiben? Das würde deinen Code auf jeden Fall ändern.

 

[lostmaster]

Nur mal so: Du sollst doch laut Aufgabenstellung eine extra Methode zum checken schreiben? Das würde deinen Code auf jeden Fall ändern.

Ja, das stimmt aber ehrlich gesagt weiß ich nicht wie ich das anstellen sollte. Muss ich jetzt über "public static void isPalindrome" bspw. diese checkmethode initialiseren ? und kann ich diese einfach darunter schreiben, ab dem Teil wo die ich die beiden Arrays gespeichert habe? und steht dann dort nicht "einfach" dieser teil

int i = 0;
        	int j = UsersInput.length;
        	for(int i1=0; i1<UsersInput.length; i1++) 
        	{
        			for (int j1=0; j1>UsersInputReversed.length; j1++)
        			{
        				if (UsersInput[i1].equals(UsersInputReversed[j1]));
        				{
        					System.out.println();
        				}
        			}
        }

drin? Nur korrigiert, sodass dieser wirklich nur das ausspuckt was Palindrome sind?

 

[s4ke]

Schau dir unsere Postings an. das boolean steht da nicht ohne Grund . Die Methode soll ja was zurückliefern, und das ist ja der boolean Wert.

 

[Landei]

@Landei: Ich glaube nicht, dass das Sinn der Übung ist

Wahrscheinlich nicht, aber wenn's nicht verboten ist...

 

[s4ke]

Wahrscheinlich nicht, aber wenn's nicht verboten ist...

Ja wieso nicht . Aber ich glaube, dass so etwas den Lernerfolg ein bischen hindert, meinst du nicht?

 

[Ark]

Landeis Lösung ist zwar schön kurz in Bezug auf die Länge des Quelltextes, aber man sollte den Nebenaufwand (bezüglich Performance, d.h. Speicher- und Zeitaufwand) dieser Lösung nicht unterschätzen – meine Meinung. Zumindest würde ich mir so was mit XXX oder Ähnlichem markieren.

Ark

 

[hüteüberhüte]

Als Informatik-Student nicht zu wissen, wie eine Palindrom-Funktion geht, ist ungefähr so, wie als Mathe-Student nicht zu wissen, was ein Teilmenge ist. (Btw.) Oder was ich eig. schreiben wollte: sollte man die Antworten nicht auch das Posten fertiger Lösungen beschränken.

 

[Landei]

Oder was ich eig. schreiben wollte: sollte man die Antworten nicht auch das Posten fertiger Lösungen beschränken.

Das habe ich schon oft gehört, aber es stimmt so pauschal meiner Meinung nach nicht.

Wenn man eine fertige Lösung anbietet, sollte sie ein Angebot sein, selber aktiv zu werden. Hier z.B. sich über die API von String und StringBuilder schlau zu machen. In anderen Fällen, zu verstehen, wie ein "Trick" oder Idiom funktioniert. Eine besonders kurze oder elegante Lösung kann auch einen "Aha"-Effekt auslösen und neugierig machen.

Natürlich kann das nur funktionieren, wenn die Lösung nicht so kompliziert ist, dass man sie ohne Erläuterungen nicht versteht - und dann schreibe ich auch etwas dazu. Aber das ist hier nicht der Fall, hier wäre es tatsächlich nur ein "Vorkauen".

Ich bin aber kein Pädagoge, ich gebe eine - meiner Meinung nach ausreichende - Hilfestellung, und der Student kann damit arbeiten, nachfragen, oder sie eben auch durch stupides Abschreiben missbrauchen - das liegt ganz in seinem Verantwortungsbereich. Ich kann niemandem diese Verantwortung abnehmen, diese müssen die Studenten selbst lernen, entweder jetzt oder in der Prüfung auf die harte Tour.

 

[s4ke]

Als Informatik-Student nicht zu wissen, wie eine Palindrom-Funktion geht, ist ungefähr so, wie als Mathe-Student nicht zu wissen, was ein Teilmenge ist. (Btw.) Oder was ich eig. schreiben wollte: sollte man die Antworten nicht auch das Posten fertiger Lösungen beschränken.

Das mit den fertigen Lösungen stimmt schon, aber am Anfang des Studiums (die Aufgabe klingt sehr nach 1. Semester) kann man schon mal "schummeln", wenn man wenigstens die Lösung verstanden hat, aber das liegt wie Landei schon gesagt hat im Ermessen des jeweiligen Studenten.

 

[hüteüberhüte]

Wenn man eine fertige Lösung anbietet, sollte sie ein Angebot sein, selber aktiv zu werden. Hier z.B. sich über die API von String und StringBuilder schlau zu machen. In anderen Fällen, zu verstehen, wie ein "Trick" oder Idiom funktioniert. Eine besonders kurze oder elegante Lösung kann auch einen "Aha"-Effekt auslösen und neugierig machen.

Hier muss man aber unbedingt noch hinzufügen (wie Ark schon erwähnt hat), dass zusätzlich Objekterzeugung + Mehr(zeit und speicher)aufwand hinzukommt.

Ich würde einfach nur auf die super Methode charAt(int index) und wie man char s miteinander vergleicht, hinweisen - falls ich überhaupt etwas dazu schreiben sollte, was ich eig. nicht vorhatte (<- das schreibt man zusammen, gruselig ).

Auch braucht er sich über Benutzereingabe nicht Gedanken machen, denn die Eingabe wird dem Programm als Parameter mitgegeben und liegt deshalb schon als String[] vor

 

[Landei]

Ich soll aus pädagogischen Gründen keine fertigen Lösungen liefern, während du zwei Posts weiter junge, hoffnungsvolle Eleven mit dem verderblichen Virus der Mikrooptimierung verseuchst?

Hast du einmal nachgemessen, was heutzutage eine Objekterzeugung "kostet"? Unter Umständen gar nichts, nämlich wenn Hotspot (gepriesen sei sein Bytecode!) das schlicht wegoptimiert. Und ansonsten Nanosekunden.

Also im Zweifelsfall einfach mal...

 

[hüteüberhüte]

Also dann lies dir mal bloch effective java durch. Das ist doch nicht an den Haaren herbeigezogen. Es ist auch nicht nur micro optimierung, es ist im Zweifel auch nicht besser lesbar, was der einzige dafürsprechende Punkt wäre. Der Vollständigkeit halber ist das zu erwähnen auch richtig. Das mit der Kresse lass lieber weg. Kaum einer ist hier bestimmt Pädagoge

Gesendet mit Tapatalk 2

 

[Nuke77]

Also dann lies dir mal bloch effective java durch. Das ist doch nicht an den Haaren herbeigezogen.

Aha, sagst du das jetzt nur weil du meinst "effective" hieße im Deutschen "effizient" oder "performant" oder hast du das Buch selbst auch gelesen?

 

[Ark]

Hier geistern ja schon teilweise abenteuerliche Vorstellungen von optimierenden Compilern rum …

Im Zweifelsfall gilt: Der Compiler optimiert gar nicht. Das klingt zwar wahnsinnig pessimistisch, aber genau so gehen die Optimierungen vonstatten. Wenn der Compiler nicht für alle möglichen Fälle garantieren kann, dass der "optimerte" Code semantisch äquivalent zum ursprünglichen ist, dann rührt er da nichts an.

Wenn auf der höchsten Abstraktionsebene (sprich: im Java-Quellcode) das, was eigentlich getan werden soll, zu einer Nebenaufgabe verkommt, und hauptsächlich nur "um das Problem herum" programmiert wurde, dann werden die Compiler, die den Code für immer niedrigere Abstraktionsebenen umschreiben, da nicht mehr viel herausholen können. Möglicherweise werden die Compiler davon sogar in die Irre geführt, sodass sie z.B. die 90% unnützen Code optimieren, während die eigentlich wichtigen 10% unoptimiert bleiben.

Ergo: Wenn schon auf höchster Ebene ein grober Fehler hinsichtlich Performance gemacht wurde, wird sich dieser Fehler bis nach ganz unten auswirken – da hilft auch kein Compiler mehr. Und ich bin der Meinung, dass man zumindest eine grobe Vorstellung davon haben sollte, was ein Compiler optimieren kann und was nicht. Denn sonst schlägt Wirth zu.

Mal ein einfaches Beispiel: Wird

intA * 2

optimiert zu

intA << 1

? Antwort: Wahrscheinlich, immerhin spricht eigentlich nichts dagegen. Aber passiert das auch wirklich? Mein Tipp: Schreib gleich die Shift-Variante hin, denn das ist schneller erledigt als die Suche nach dem Flaschenhals später. Und dass die Shift-Variante langsamer sein sollte als die Multiplikation, ist so gut wie ausgeschlossen: Eine Multiplikation kostet typischerweise sehr viel mehr als ein Shift. (Je nach Hardware stehen eventuell keine großen Shifter zur Verfügung, aber bei kleinen Shifts sollte man so auf der sicheren Seite sein.) In meinem Test auf meiner Hardware ergab sich in diesem Beispiel kein messbarer Unterschied.

So, und nun ein anderes Beispiel: Wird

intA / 2

optimiert zu

intA >> 1

? Antwort: so gut wie nie. Grund: die Variante mit dem Shift ist nur dann semantisch äquivalent zur Division, wenn

intA >= 0 || (intA & 1) == 0

oder äquivalent dazu

(i & 0x80000001) != 0x80000001

gilt. In Worten ausgedrückt: intA muss positiv oder wenigstens gerade sein. Und da der Compiler dies so gut wie nie beweisen können wird, lässt er wohl die Finger davon. Ein Alternative wäre, wenn der Compiler als "optimierten" Code

(intA >> 1) + (intA >>> 31 & i)

einsetzen würde. (Ich weiß gerade nicht, ob es eine schnellere Variante gibt.) Zumindest in meinen Tests auf meiner Hardware war dieser "optimierte" Code aber tatsächlich langsamer: er benötigte 104,43% der Zeit, die die Division benötigte. Ein anderes Bild ergab sich jedoch, wenn ich

intA >> 1

einsetze, weil ich aufgrund des Codes wusste, dass intA nur positiv sein kann: Dieser optimierte Code benötigte hier nur 70,01% der Zeit der Division.

Wie dieser kleine Test gezeigt hat, können schon relative simple Peephole-Optimierungen vom Compiler nur deshalb nicht vorgenommen werden, weil – etwas allgemeiner ausgedrückt – viele Randbedingungen dem Compiler schlicht nicht bekannt sind.


Zurück zu den Palindromen: Ich habe für eine genauere Untersuchung nun folgende Implementierungen fürs Benchmarking verwendet:

	public static boolean alternative1(final String str){
		final String s = str.toLowerCase();
		return s.equals(new StringBuilder(s).reverse().toString());
	}

	public static boolean alternative2(final String str){
		int left = 0;
		int right = str.length() - 1;

		while(left < right){
			if(Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))){
				return false;
			}
			left++;
			right--;
		}
		return true;
	}

	public static boolean alternative3(final String str){
		int left = 0;
		int right = str.length() - 1;

		while(left < right){
			if((str.charAt(left) & 0xFFFD) != (str.charAt(right) & 0xFFFD)){
				return false;
			}
			left++;
			right--;
		}
		return true;
	}

Die Methode

alternative1()

entspricht dabei Landeis Code, die beiden anderen Methoden basieren auf typischen Implementierungen, wie man sie etwa im Internet findet. Es sei angemerkt, dass alle drei Methoden bezüglich Groß-/Kleinschreibung andere Annahmen machen und deshalb nicht für alle Unicode-Zeichen äquivalent sind. Für Wörter, die nur aus Zeichen von a bis z oder A bis Z bestehen, spielen diese Unterschiede aber keine Rolle.

Zum Test wurden 1000 zufällige Wörter erzeugt, die zwischen 0 und 100 Zeichen (inklusive) lang, mit etwa 75% Wahrscheinlichkeit Palindrome und zu etwa 87,5% aus Kleinbuchstaben a bis z (sonst Großbuchstaben A bis Z) aufgebaut sind.

Die durchschnittlichen Ausführungszeiten nach 10000 Durchläufen über alle 1000 Wörter:

alternative1()

: 836536 Nanosekunden

alternative2()

: 177401 Nanosekunden

alternative3()

: 91642 Nanosekunden

Schon

alternative2()

braucht also nur etwa 21,21% der Zeit von

alternative1()

. Und

alternative3()

kann die Ausführungszeit fast noch mal halbieren (10,95%). Der Test wurde mit folgender Java-Version durchgeführt:

java version "1.7.0_07"
OpenJDK Runtime Environment (IcedTea7 2.3.2) (7u7-2.3.2a-0ubuntu0.12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

Noch ein paar Anmerkungen zur Sache mit dem Speicherverbrauch: Ein mögliches Problem, auf das ich hier aufmerksam machen möchte, betriff nicht direkt die Zeit, die zur Objekterzeugung notwendig ist, sondern den Geschwindigkeitsverlust aufgrund von schlecht nutzbarem CPU-Cache: Neu erzeugte Objekte landen wahrscheinlich irgendwo auf dem Heap. Zugriffe auf diese Objekte können vor allem, wenn sie groß sind (etwa das char[]-Array, das für jeden String erzeugt wird), andere (wichtigere) Teile des Arbeitsspeichers aus den CPU-Caches verdrängen. Dadurch kann auch die Ausführungszeit des Aufrufers schlechter ausfallen (obwohl er nichts dafür kann) und die Gesamt-Performance verschlechtert sich: Das Programm benötigt mehr Speicher und ist langsamer.

Kurz gesagt: Schiebt nicht alles auf die Compiler!

Ark

 

[Landei]

Meine "langsame" Methode braucht also ungefähr 84 ns, also 0.000000084 s für 1000 Wörter (wir wollen einmal die bekannten Probleme von Microbenchmarks außen vor lassen und annehmen, dass das ungefähr hinkommt). Ich denke, dass ist für 99% aller Anwendungen schnell genug. Wenn man sich die Größenordnung vor Augen führt, wird klar, wie unsinnig eine Performance-Diskussion hier aus praktischer Sicht ist.

Dass die anderen Methoden schneller sind, liegt meiner Meinung nach weniger an der Objekterzeugung, sondern am "early exit", d.h. sie können aufhören, sobald sie einen Unterschied gefunden haben. Man könnte nun einwenden, dass mein Algorithmus zu ineffizient ist, bei genauerem Hinsehen ist das aber eine Konsequenz der Abarbeitungsstrategie in Java. "Faule" Sprachen wie Haskell würden das [c]reverse[/c] immer nur "soweit wie nötig" ausführen, und so ebenfalls einen "early exit" erreichen. Im Prinzip könnte das eine weiterentwickelte Java-Runtime auch.

Der Hauptvorteil meiner Version ist nicht, dass sie kürzer ist, sondern vor allem, dass sie auf einen Blick als korrekt zu erkennen ist. Hier kann buchstäblich nichts schiefgehen, es sei denn, API-Funktionen wie [c]toString[/c] oder [c]reverse[/c] hätten Bugs, was extrem unwahrscheinlich ist. Bei den anderen Implementierungen muss man erst einmal schauen, was passiert, ob keine Indexüberschreiten vorkommen, was die seltsamen Bitschubsereien bedeuten u.s.w. Die Mikrooptimierung kostet also Entwicklungszeit, und zwar jedesmal wenn jemand diesen Code verstehen will.

 

[hüteüberhüte]

Aha, sagst du das jetzt nur weil du meinst "effective" hieße im Deutschen "effizient" oder "performant" oder hast du das Buch selbst auch gelesen?

Effektiv o. effizientes Java, übersetze es, wie du willst. Und ja, es liegt neben meinem Schreibtisch, weil die Autoren auch an der Entwicklung Javas beteiligt waren und davon wirklich etwas verstehen und sagen können, wie man etwas machen oder nicht machen sollte.

Variante 1 von Landei/Ark ist ja auch nicht falsch. Das richtige Ergebnis wird zurückgegeben und man kann den Code gut lesen. Aber es werden Objekte erzeugt, was eig. immer langsam geht. Man sollte zwar immer auch Alternativen erwähnen, dann aber immer auch sagen, warum sie besser oder nicht besser sind.

 

[Landei]

Nimm deine 75 gewonnenen Nanosekunden und mach etwas sinnvolles. Vielleicht mal ein Buch lesen, "Clean Code" zum Beispiel...

 

[hüteüberhüte]

21,21 oder 10,95% sind schon viel, wenn es ausschließlich um diese Aufgabe geht/das Programm also nur Palindrom e testen soll.

Aber Hey, warum regst du dich darüber so auf? Unter Freunden wird es doch erlaubt sein, irgendwelche Hinweise oder Anmerkungen zu geben? Ich freue mich ja auch, wenn etwas neues gezeigt wird oder jemand sagt, so lieber nicht machen, sonder das oder jenes wäre besser?

Ich hätte das etwa so gemacht:

    public static boolean isPalindrome(String str) {
        for (int i = 0; i < str.length() / 2; i++) {
            if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

Was einen Kompromiss zwischen Lesbarkeit und Performance darstellen würde.

Aber ich glaube, es geht vielmehr um meine Aussage bzgl. Mathe-/Info-Student. Wenn es darum geht, ja war halt meine Meinung dazu. :autsch:

 

[Ark]

Meine "langsame" Methode braucht also ungefähr 84 ns, also 0.000000084 s für 1000 Wörter (wir wollen einmal die bekannten Probleme von Microbenchmarks außen vor lassen und annehmen, dass das ungefähr hinkommt). Ich denke, dass ist für 99% aller Anwendungen schnell genug. Wenn man sich die Größenordnung vor Augen führt, wird klar, wie unsinnig eine Performance-Diskussion hier aus praktischer Sicht ist.

Hm, wahrscheinlich habe ich mich missverständlich ausgedrückt. Die Zahlen, die mein Programm ausspuckte, beziehen sich auf einen Durchlauf mit 1000 Wörtern. Und um einen halbwegs aussagekräftigen Wert zu bekommen, wurden 10000 solcher Durchläufe gestartet und die Ergebnisse gemittelt. (Vielen Dank für den Hinweis auf Probleme beim Microbenchmarking. Mein ursprünglicher Code zog bisher nämlich nur die Zeit für eine leere Dummy-Methode ab, nicht aber die Zeit, die fürs Iterieren über die 1000 Wörter draufging. Mit dem aktuellen Code wird der Unterschied also deutlicher, aber der Unterschied beträgt auch nur vielleicht 1% der Laufzeit, fällt also nicht wirklich ins Gewicht.)

Das heißt also, für 1000 Wörter wurden z.B. etwa 837 Mikrosekunden benötigt – schon eine beachtliche Größe, wie ich finde.

Dass die anderen Methoden schneller sind, liegt meiner Meinung nach weniger an der Objekterzeugung, sondern am "early exit", d.h. sie können aufhören, sobald sie einen Unterschied gefunden haben. Man könnte nun einwenden, dass mein Algorithmus zu ineffizient ist, bei genauerem Hinsehen ist das aber eine Konsequenz der Abarbeitungsstrategie in Java. "Faule" Sprachen wie Haskell würden das [c]reverse[/c] immer nur "soweit wie nötig" ausführen, und so ebenfalls einen "early exit" erreichen. Im Prinzip könnte das eine weiterentwickelte Java-Runtime auch.

Es mag dich vielleicht wundern, aber auch dein Code verwendet ein "early exit", nämlich

String.equals()

. Leider kommt diese Methode erst ganz zum Schluss dran, und bis es so weit ist, werden vergleichsweise langwierige Vorbereitungen getroffen. Es ähnelt also eher dem Verwenden einer multi-threaded Mergesort-Implementierung, um vielleicht 50 Elemente zu sortieren: Selbst ein Bubblesort wäre wohl schon fertig, bevor überhaupt alle Threads gestartet wurden. (Ob dein Vorgehen überhaupt bei wachsender Eingabegröße performanter ist, sei mal dahingestellt.)

Der Hauptvorteil meiner Version ist nicht, dass sie kürzer ist, sondern vor allem, dass sie auf einen Blick als korrekt zu erkennen ist. Hier kann buchstäblich nichts schiefgehen, es sei denn, API-Funktionen wie [c]toString[/c] oder [c]reverse[/c] hätten Bugs, was extrem unwahrscheinlich ist. Bei den anderen Implementierungen muss man erst einmal schauen, was passiert, ob keine Indexüberschreiten vorkommen, was die seltsamen Bitschubsereien bedeuten u.s.w. Die Mikrooptimierung kostet also Entwicklungszeit, und zwar jedesmal wenn jemand diesen Code verstehen will.

Hast du denn in den Code der Methoden

String.equals()

und

StringBuilder.reverse()

geschaut? Hast du sie auf Korrektheit überprüft? Auch

StringBuilder.reverse()

macht von Bitschubsereien Gebrauch. Warum hat dich dieser Umstand nicht von der Verwendung dieser Methode abgehalten?

Falls du jetzt sagen willst, "Diese Methoden wurden geprüft und wahrscheinlich schon sehr oft verwendet, also sind sie sehr wahrscheinlich korrekt", dann entgegne ich: "Meine" Methoden habe ich auch (oft) geprüft und für gut befunden. Natürlich könnte man jetzt so was sagen wie: "Ja, aber

alternative3()

funktioniert nur mit einigen wenigen Zeichen und kann nicht einmal mit Surrogates umgehen. Dafür kann

alternative1()

mit allen Unicode-Zeichen korrekt umgehen." Stimmt, deswegen würde ich auch in der API-Dokumentation von

alternative3()

auf diese Einschränkungen hinweisen.


Noch ein Wörtchen zur Performance: Man sollte nicht nur (soll heißen: auch, aber eben nicht nur) das eigene Programm berücksichtigen, sondern vielleicht schon ein kleines bisschen größer denken: Was würde passieren, wenn jede Methode eine vergleichsweise geringe Leistung hätte? Nehmen wir mal an, wir würden es bei einer Implementierung belassen, die nur 12,5% des Möglichen rausholt. Nehmen wir ferner an, dass eine weitere Methode diese Implementierung verwendet und (unabhängig von der aufgerufenen Methode) ebenfalls nur 12,5% leistet, usw. Wie lange geht das gut? Wenn ich mich nicht verrechnet habe, würde so – rein auf die Taktgeschwindigkeit bezogen – schon nach der fünften(!) Methode mein Core2Duo (2 x 2,3 GHz) von einem mittelalterlichen 6510-Prozessor (ca. 1 MHz) überholt werden, und zwar richtig (etwa: Auto mit 140 km/h vs. Fußmarsch)!

Ark

 

[Landei]

Noch ein Wörtchen zur Performance: Man sollte nicht nur (soll heißen: auch, aber eben nicht nur) das eigene Programm berücksichtigen, sondern vielleicht schon ein kleines bisschen größer denken: Was würde passieren, wenn jede Methode eine vergleichsweise geringe Leistung hätte? Nehmen wir mal an, wir würden es bei einer Implementierung belassen, die nur 12,5% des Möglichen rausholt. Nehmen wir ferner an, dass eine weitere Methode diese Implementierung verwendet und (unabhängig von der aufgerufenen Methode) ebenfalls nur 12,5% leistet, usw. Wie lange geht das gut? Wenn ich mich nicht verrechnet habe, würde so – rein auf die Taktgeschwindigkeit bezogen – schon nach der fünften(!) Methode mein Core2Duo (2 x 2,3 GHz) von einem mittelalterlichen 6510-Prozessor (ca. 1 MHz) überholt werden, und zwar richtig (etwa: Auto mit 140 km/h vs. Fußmarsch)!

Man muss sich schon ziemlich dumm anstellen, um das auf allen Ebenen zu erreichen. Der Punkt ist, dass ich dann optimiere, wenn etwas zu langsam ist, nicht "einfach so", obwohl die Lesbarkeit darunter leidet.

Weiterhin stellt sich selbst dann, wenn ich optimiere, auf welcher Ebene ich das tue. Der Palindromtester wird möglicherweise auf eine beschränkte Zahl von Strings angewandt, da ist es gut möglich, dass durch Memoisierung wesentlich mehr gespart werden kann als durch einen besseren Algorithmus - aber das kommt auf den Anwendungsfall an.

Das allerwichtigste ist, erst einmal sauberen, verständlichen und vor allem korrekten Code zu schreiben, und das müssen Studenten erst einmal lernen. Falls ich dann optimiere, habe ich einen funktionierenden Ausgangspunkt (den man z.B. für Back-To-Back-Tests nutzen kann), und stochere nicht im Nebel, bis mein komplizierter Ansatz irgendwann so aussieht, als ob er funktioniert.

 

[Bernd Hohmann]

Hast du sie auf Korrektheit überprüft? Auch

StringBuilder.reverse()

macht von Bitschubsereien Gebrauch.

Tatsache, da wird ein Wert via Shift durch 2 geteilt.

Ich nenne sowas "akademischen Code": der Entwickler wird (aus den von Dir aufgeführten Gründen) länger darüber nachgedacht haben ob das an dieser Stelle "schmerzfrei" geht und andere Entwickler werden ebenfalls länger darüber nachdenken ob das geht als diese "Optimierung" jemals Zeit sparen wird - hauptsache der Schreiber hat bewiesen, dass er in der Vorlesung aufgepasst hat.

Dass .reverse() trotzdem korrekt ist, davon sollten wir mal ausgehen.

Und was ich gar nicht verstehe: Sonst heissts immer "nimm das, was schon da ist" und jetzt fangen wir an für einen gemächlichen Test auf ein Palindrom zu optimieren als ob die Existenz der Welt daran hängen würde :lol:

btw: ich hab mal Deine Tests mit einem konstanten String durchgeführt: der erste Schleifendurchlauf (egal mit welcher alternative) dauert immer das 2-3fache als die weiteren Durchläufe. Würde mich mal interessieren wie die Zahlen in Deinem Szenario aussehen wenn das in der Reihenfolge 3/2/1 aufgerufen wird.

Bernd

 

[hüteüberhüte]

Wenn man gleich richtig schreibt, braucht man hinterher im Nachhinein nicht mehr optimieren

btw: ich hab mal Deine Tests mit einem konstanten String durchgeführt: der erste Schleifendurchlauf (egal mit welcher alternative) dauert immer das 2-3fache als die weiteren Durchläufe. Würde mich mal interessieren wie die Zahlen in Deinem Szenario aussehen wenn das in der Reihenfolge 3/2/1 aufgerufen wird.

Wenn du immer denselben String (der ist immutable) einer Methode übergibst und darin nicht auf andere Variablen zugegriffen wird, wird immer das gleiche Ergebnis zurückgegeben und das kann wegoptimiert werden. Also kein Beispiel für ein realistisches Szenario

 

[s4ke]

Statt

        if(pWord.toLowerCase().equals(pWordReversed)){
            return true;
        }
        else {
            return false;
        }

hätte es auch ein

return pWord.toLowerCase().equals(pWordReversed);

getan .

 

[hüteüberhüte]

Schreib alles in eine Zeile wie Landei vorgeschlagen hat. Die Methoden haben mnemonische Bezeichner u. sind deshalb unmittelbar verständlich

 

[Ark]

Das allerwichtigste ist, erst einmal sauberen, verständlichen und vor allem korrekten Code zu schreiben, und das müssen Studenten erst einmal lernen. Falls ich dann optimiere, habe ich einen funktionierenden Ausgangspunkt (den man z.B. für Back-To-Back-Tests nutzen kann), und stochere nicht im Nebel, bis mein komplizierter Ansatz irgendwann so aussieht, als ob er funktioniert.

Dito. Und dennoch bin ich der Meinung, dass man zumindest eine Vorstellung dafür entwickeln sollte, was man der Maschine so zutraut.

Ich nenne sowas "akademischen Code": der Entwickler wird (aus den von Dir aufgeführten Gründen) länger darüber nachgedacht haben ob das an dieser Stelle "schmerzfrei" geht und andere Entwickler werden ebenfalls länger darüber nachdenken ob das geht als diese "Optimierung" jemals Zeit sparen wird - hauptsache der Schreiber hat bewiesen, dass er in der Vorlesung aufgepasst hat.

Schau dich mal in anderen Klassen von z.B. java.util oder java.lang um, etwa

Integer.toString()

bzw.

Integer.toString(int)

. Wenn man da an jeder fraglichen Stelle ewig rumüberlegt hätte, wären wir heute noch vielleicht erst beim Stand von JDK 1.1, schätze ich mal.

Und was ich gar nicht verstehe: Sonst heissts immer "nimm das, was schon da ist" und jetzt fangen wir an für einen gemächlichen Test auf ein Palindrom zu optimieren als ob die Existenz der Welt daran hängen würde :lol:

Man kann viele Ego-Shooter auch zum Chatten benutzen … Was hältst du eigentlich von Projekten wie dem hier?

btw: ich hab mal Deine Tests mit einem konstanten String durchgeführt: der erste Schleifendurchlauf (egal mit welcher alternative) dauert immer das 2-3fache als die weiteren Durchläufe. Würde mich mal interessieren wie die Zahlen in Deinem Szenario aussehen wenn das in der Reihenfolge 3/2/1 aufgerufen wird.

Bitteschön, hier gleich drei Versuche (jeweils gleiche Reihenfolge der Alternativen wie oben):

818189
173998
92030

804319
166832
88406

822591
169738
85851

Dass die Werte relativ stark schwanken, liegt wahrscheinlich vor allem an den vielen (pseudo-)zufälligen Stringlängen pro Versuch. Die Verhältnisse bleiben aber ähnlich.

Wenn man gleich richtig schreibt, braucht man hinterher im Nachhinein nicht mehr optimieren

Es kommt wohl auf den Anwendungsfall an, ob und wo noch weiter optimiert werden muss. Ich sehe da aber noch einen weiteren Aspekt: Das eigene Programm ist nicht das einzige, das auf einem Rechner laufen will. Es kann sein, dass ein Programm unter Laborbedingungen (mit vielleicht 16 GB Arbeitsspeicher, 2 Quadcores à 3 GHz etc.) ganz passabel läuft, im Feldversuch aber wegen "schlechter" Hardware nicht zu gebrauchen ist – zumal auch andere Prozesse etwas von der Hardware abhaben möchten. Außerdem werden Module mit schlechtem Laufzeitverhalten wahrscheinlicher nicht wiederverwendet, weil sie neuen Anforderungen eher nicht mehr gewachsen sind. Performance hat also auch was mit Wiederverwendbarkeit zu tun.

Wenn du immer denselben String (der ist immutable) einer Methode übergibst und darin nicht auf andere Variablen zugegriffen wird, wird immer das gleiche Ergebnis zurückgegeben und das kann wegoptimiert werden. Also kein Beispiel für ein realistisches Szenario

Dass da so krass optimiert wird, halte ich eher für unwahrscheinlich.

@lostmaster: Dein Javadoc-Kommentar ist so, wie er da steht, der Klasse zugeordnet (und eben nicht der Methode). Verschiebe einfach den Kommentarblock so, dass er unmittelbar vor der Methode steht.

Außerdem kann man die Ausdrücke für die if-Bedingungen (bei dir z.B. Zeile 26) immer so umschreiben, dass weder

true

noch

false

verwendet werden muss. (Okay, zum Aufruf von Methoden etc. eventuell schon, aber ich denke, es ist klar, was damit gemeint ist).

Ark

 

[Bernd Hohmann]

(Akademischer Code) Schau dich mal in anderen Klassen von z.B. java.util oder java.lang um, etwa

Integer.toString()

bzw.

Integer.toString(int)

. Wenn man da an jeder fraglichen Stelle ewig rumüberlegt hätte, wären wir heute noch vielleicht erst beim Stand von JDK 1.1, schätze ich mal.

Hoffentlich hat nur der ursprüngliche Enwickler alle Fälle geprüft - ansonsten ist mir der Code an dieser Stelle seit Java 1.1 suspekt weil schon dort irgendwelche Optimierungen zur damaligen VM hin gemacht wurden und der Code in jeder Version anders aussah wegen anderer VM.

Sinnig wäre es gewesen, das einfach als "native" zu deklarieren und in der VM abzuhandeln.

Was hältst du eigentlich von Projekten wie dem hier?

Erinnert mich bisserl an Ethan Winers P.D.Q als Ersatz für BCOMxx.LIB - damit konnte man mit dem MS-Basic Compiler sogar TSRs entwickeln. Leider war alles sehr gewöhnungsbedürftig und dann kam Windows 3.1 wo Multitasking halbwegs Unfallfrei in der DOS-Box machen konnte.

Javalution ist irgendwie nicht Fisch und nicht Fleisch - ich sehe für mich selbst keinen Einsatzzweck.

Bitteschön, hier gleich drei Versuche (jeweils gleiche Reihenfolge der Alternativen wie oben):

Danke für die Mühe, wie Hüteüberhüte sagte hab ich einen Denkfehler gemacht.

Es kommt wohl auf den Anwendungsfall an, ob und wo noch weiter optimiert werden muss. Ich sehe da aber noch einen weiteren Aspekt: Das eigene Programm ist nicht das einzige, das auf einem Rechner laufen will. Es kann sein, dass ein Programm unter Laborbedingungen (mit vielleicht 16 GB Arbeitsspeicher, 2 Quadcores à 3 GHz etc.) ganz passabel läuft, im Feldversuch aber wegen "schlechter" Hardware nicht zu gebrauchen ist

Das ist eine Ecke, wo man sich noch nie wirklich Gedanken machen musste - unter der Voraussetzung natürlich dass man ein Gefühl dafür hat, was Ressourcen verbrät und die Laufzeiten seiner Algorithmen erahnen kann.

Alter Schwank: Da gab es mal eine MS-Access Programmierung für eine Wäscherei wo eine Bedarfsoptimierung durchgeführt wurde. Im Prinzip eine äussere Schleife über HEMDEN....HOSEN, in der Mitte über Lieferstellen und die innere Schleife über fertige Wäschekörbe. Im Test mit 4 Lieferstellen, 10 Wäschekörben und 3 Produkten (Hemden, Hosen, Unterhosen) funktionierte das ganz prima

Bernd

 

[HoloYoitsu]

Danke für die Aufgabestellung, hat spaß gemacht. :applaus:

Bin allerdings selbst erst Programmierer/in im 2. Lehrjahr, daher war es eine schöne Übung.

Unabhängig von euren Lösungen würde ich euch gerne noch meine zeigen.

Für konstruktive Kritik bin ich natürlich auch gern offen


Grüße, Holo

package defau1t;

public class TestKlasse
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		try
		{
			String satz = "Das Reittier wirft Otto ab";

			TestKlasse tk = new TestKlasse();
			tk.printPalindrome(satz);
		}

		catch (Exception e)
		{
			System.out.println("Fehler: " + e.getMessage());
			System.out.println("________________________________________________");
			e.printStackTrace();
		}

	}

	private void printPalindrome(String satz)
	{
		String[] saWoerter = satz.split(" ");

		for (int i = 0; i < saWoerter.length; i++)
		{
			if (isPalindrom(saWoerter[i]))
			{
				System.out.println(saWoerter[i]);
			}
		}
	}

	private boolean isPalindrom(String string)
	{
		String reversed = "";

		for (int i = 0; i < string.length(); i++)
		{
			reversed = reversed + string.charAt(string.length()-1 - i);
		}

		if (string.toLowerCase().trim().equals(reversed.trim().toLowerCase()) && string.trim().length() > 1)
		{
			return true;
		}

		return false;

	}
}

 

[s4ke]

Kleine Anmerkung zu deinem Programm :

1. Generelles Exception Fangen ist ein no-go. Vor allem weil dein Code, wenn er richtig geschrieben ist, keine werfen sollte.
2.

if( [boolschebedingung] ) {
 return true;
} else {
 return false;
}

So ein Code kann !immer! durch

return [boolschebedingung];

ersetzt werden.
3. "teststring".length() sollte imho in eine Zwischenvariable kommen, das sind zu viele unnütze Aufrufe .

 

[HoloYoitsu]

Wieder was dazugelernt, so hätte ich meine Kritik gern immer!

Danke s4ke!

 

[s4ke]

Und noch was:

Wenn man oft Strings konkateniert, gibt das einiges an Objektmüll, benutz da lieber [JAPI]java.lang.StringBuilder[/JAPI]. Das liegt nämlich daran, dass Strings Immutable sind, also unveränderlich und bei jeder Operation immer ein neues String-Objekt erzeugt werden muss.

Und was ich zu .length() gesagt hab gilt auch für Arrays und sonstige "Aufrufe" genauso. Ich persönlich verfahre danach: "Wenn etwas zweimal gebraucht wird, bekommt es eine Zwischenvariable", das macht den Code 1. lesbarer und wartbarer und 2. unter Umständen schneller .

 

[HoloYoitsu]

Beim programmieren lernt man wohl nie aus

Aber wird der Objektmüll nicht vom Garbagecollector wieder aufgeputzt? :O

Also mal unabhängig von der Geschwindigkeit gesehen. :bahnhof:

 

[s4ke]

Ja, das schon, aber man sollte ihm das Leben doch nicht schwer machen, der hat doch so schon genug zu tun ^^.

Objekterzeugung ist allgemein sehr teuer (laufzeittechnisch gesehen) und sollte vermieden werden, wenn man drumrum kommt. Deswegen wird z.B. bei Grafikengines Objekt Pooling für Objekte die ständig gebraucht werden verwendet, was dann gebrauchte Objekte "recycled", auf einen Initialzustand zurücksetzt und wieder frei gibt.

 

[HoloYoitsu]

Jaja, der arme Garbage-Collector feif:

Ich danke jedenfalls für die Super Kritik und hoffe der Threadsteller ist auch zufrieden

 

[Ullenboom]

Und für ubergeeks, bei denen Performance und Speicherbedarf Randthemen sind: How does this Java regex detect palindromes? - Stack Overflow

 

[Ark]

Und was ich zu .length() gesagt hab gilt auch für Arrays und sonstige "Aufrufe" genauso. Ich persönlich verfahre danach: "Wenn etwas zweimal gebraucht wird, bekommt es eine Zwischenvariable", das macht den Code 1. lesbarer und wartbarer und 2. unter Umständen schneller .

Ich bin mit fast allem einverstanden: Dass der Code durch Verwendung von Variablen für "triviale" Getter schneller wird, wage ich zu bezweifeln. So wurde bei mir neulich der Code von

String.length()

zu

0x00007f8b190688ea: mov    0xc(%r9),%r11d
0x00007f8b190688ee: mov    0xc(%r11),%esi

kompiliert und so direkt in den Aufrufer eingebaut (inline).

Ark

 

[Bernd Hohmann]

Ich bin mit fast allem einverstanden: Dass der Code durch Verwendung von Variablen für "triviale" Getter schneller wird, wage ich zu bezweifeln. So wurde bei mir neulich der Code von

String.length()

zu

0x00007f8b190688ea: mov    0xc(%r9),%r11d
0x00007f8b190688ee: mov    0xc(%r11),%esi

kompiliert und so direkt in den Aufrufer eingebaut (inline).

Wenns eine Stringkonstante ist wird das auch von Java entsprechend einkompiliert.

Möglich, dass Dein C++ Compiler schlauer ist und das auch bei nicht-Konstanten erkennt.

Was "triviale" Getter angeht: man sieht ".size()" oder ".length()" nicht an, ob das Innenleben trivial ist oder es sich lohnt, das in einer Zwischenvariablen abzulegen. Das sind dann immer die Momente wo man abwägen, in den Source oder mit einem kleinen Benchmark arbeiten muss.

Auf jeden Fall hat eine Zwischenvariable den Vorteil, dass nicht ständig ein Methodenaufruf stattfinden muss (weiss jetzt aber nicht, wie kostspielig das in Java wirklich ist).

Bernd

 

[Ark]

Wenns eine Stringkonstante ist wird das auch von Java entsprechend einkompiliert.

Möglich, dass Dein C++ Compiler schlauer ist und das auch bei nicht-Konstanten erkennt.

???:L Die Strings wurden erst zur Laufzeit erzeugt, und erst zur Laufzeit hat der JIT-Compiler diesen Code generiert. C++ hatte damit wohl eher gar nichts zu tun.

Auf jeden Fall hat eine Zwischenvariable den Vorteil, dass nicht ständig ein Methodenaufruf stattfinden muss (weiss jetzt aber nicht, wie kostspielig das in Java wirklich ist).

Es ist wohl nicht so kostspielig wie in Python, habe ich mir sagen lassen. Aber grundsätzlich stimme ich dir zu.

Ark

 

[s4ke]

Hmm, dass das von Compiler rausoptimiert wird, habe ich mir schon fast gedacht. Ich bin trotzdem noch ein Fan von Extra Variablen.