Dieser Teil der Vorlesung verwendet das Skriptum als Unterlage, daher sind hier nur Beispielprogramme und einige Stichworte zu finden.
javac,
Laufzeitsystem java
Lebensdauer und Speicher von Variablen bei fib(3):
public static int fib(int n) {
if (n<2)
return n;
else
return fib(n-1)+fib(n-2);
}
Referenztypen behandeln wir später
Interessant ist dabei besonders java.lang und java.util.
Fakultät berechnen:
public class Fact { // Dateiname Fact.java
public static int fact(int n) {
if(n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
public static void main(String[] args) {
System.out.println(fact(Integer.parseInt(args[0])));
}
}
Eingabe mit args beschränkt. Alternative: System.in.
Problem: Wie sollen Zeichen der Eingabe interpretiert werden? Lösung: Scanner
import java.util.Scanner;
public class Fact {
public static int fact(int n) {
/* ... */
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
System.out.println(i);
}
}
Fakultät von n! wird meist eher so berechnet, dass man bei 1 beginnend mit der nächst größeren Zahl multipliiert, bis man n erreicht.
10! = 1 * 2 * 3 * ... * 10
Als Programm: Beginne bei 1 und multipliziere auf, bis n erreicht wird.
public static int fact(int n) {
int i = 0;
int result = 1;
while(i <= n) {
result *= i;
i ++;
}
return result;
}
while-Schleife immer bei "Solange Bedingung, wiederhole".
Spezialfall von while-Schleife: For-Schleife mit Initialisierungsteil und Aktualisierungsteil.
Spezialfall von while-Schleife: For-Schleife mit Initialisierungsteil und Aktualisierungsteil.
public static int fact(int n) {
int result = 1;
for(int i = 0 ; i <= n ; i ++) {
result *= i;
}
return result;
}
Übungsaufgabe: Testen, ob eine Zahl eine Primzahl ist
Unterschied zu while: Wird mindestens 1x durchlaufen.
public static main(String[] args) {
Scanner sc = new Scanner(System.in);
do {
/* ... */
System.out.println("Noch einmal?");
} while(sc.next().equals("ja"));
}
Debuggen hilft beim Nachvollziehen des Programms. Je besser strukturiert das Programm, desto einfacher wird Debuggen. Debuggen ersetzt nicht den Designprozess!
Möglichkeiten zum Debuggen
Arrays sind Objekte, die aus mehreren Elementen - alle vom selben Datentyp - zusammengesetzt sind. Arrays sind Referenztypen, das heißt, Variablen vom Typ Array enthalten das Array nicht, sondern zeigen auf ein Array. Wie alle Objekte müssen Arrays angelegt werden.
public class ArrayTest {
public static void testSwapInts(int i0, int i1) {
int tmp = i0;
i0 = i1;
i1 = tmp;
}
public static void swapInts(int[] arr) {
int tmp = arr[0];
arr[0] = arr[1];
arr[1] = tmp;
}
public static void main(String[] args) {
int i0 = 5;
int i1 = 6;
testSwapInts(i0, i1);
System.out.printf("%d, %d\n", i0, i1); // Keine Änderung.
int[] arr = new int[2]; // Erzeugt ein Array mit 10 Elementen.
arr[0] = 5; // Erstes Element hat immer Index 0.
arr[1] = 6;
// Alternative: int[] arr = new int[]{5, 6};
// Zugriff auf arr[2] fuehrt zu einem Fehler.
swapInts(arr);
// Neuer Schleifentyp: For-Each-Schleife. Gibt alle Elemente zurueck:
for(int e : arr) {
System.out.println(e);
}
/* Aequivalent zu
for(int j = 0; j < arr.length; j++) {
System.out.println(arr[j]);
}
*/
}
}
Übungsaufgabe: Sieb des Eratosthenes
Strings sind Zeichenketten, d.h., Datenstrukturen in denen man Text speichern kann.
Strings sind ein Referenztyp. Es gibt allerdings keine Methoden, mit denen man einen String inhaltlich ändern kann. Alle Methoden, die eine Zeichenkette zurückgeben, erzeugen eine neue Zeichenkette. Daher keine Seiteneffekte.
nur ein Element bei der Implementierung von Datenstrukturen. Eine Datenstruktur enthält Daten und Operationen auf den Daten. Beispiel: Stack auf der Basis von linked lists. Andere naheliegende Datenstrukturen mit verketteten Listen: Menge, Sequenz.
Implementierung von Stack (oder Queue) mit Array
Gleiches Interface, (fast) gleiches Verhalten, unterschiedliche Implementierung: abstrakter Datentyp
Gleiches Interface, teilweise unterschiedliches Verhalten. Dynamische Bindung von Methoden.
new).
abstract kennzeichnen), aber auch Methoden und
Variablen, man kann kein Exemplar davon machen, sonst wie Klasse.
new).
static Methoden: Aufruf mit methode(args)
Object"a"+b ist äquivalent zu "a"+b.toString();.
== vs. equals
Beachte: Zusammenhang zwischen equals und hashCode muss man selbst sicherstellen
Object hashCode
toString
IntStackA hashCode
toString
IntStackI hashCode
toString
Zweck: Kommunikation mit anderen Programmierern (oder auch mit dem zukünftigen Ich): Auf welche Teile der Klasse kann man sich verlassen, und welche Teile können sich ändern; kann ich z.B. die Datenrepräsentation von Array auf verkettete Liste ändern?
Gutes Design? Klassenzusammenhalt (Cohesion): Man kann isIncreasing() ohne weiteres aus der Klasse entfernen, also geringer Zusammenhalt.
Assertions, Invarianten
Testen (Skriptum 5.3). Black box test, white box test, unit test, integration test, regression test. "Tests können nur die Anwesenheit von Fehlern beweisen, nicht die Abwesenheit".
Debuggen (Skriptum 5.4) mittels Ausgabe-Anweisungen ("printf-Debugging"). Debuggen mit netbeans; bequemer, aber oft Zeitfresser.
Beweisen. Model Checking.
Vorhersage: Äußere Schleife in taxi.main(): O(limit1/3) Iterationen; innere Schleife: O(limit1/3) Iterationen pro äussere Iteration, O(limit2/3) Iterationen insgesamt (A). Länge der Liste (B): Annähernd O(limit2/3) (fast immer ein put pro innerer Iteration in taxi.main()). Zahl der Iterationen in ListTable.get() insgesamt (C): O(limit4/3).
Messwerte/Faktor dazwischen:
limit A B C t
1250000 5110 5059 12893829 0.380s
8 4.008 4.019 16.1158 20.55
10000000 20480 20330 207795013 7.808s
8 4.001 4.009 16.0459 16.71
80000000 81937 81506 3334249330 130.476s
Erklärung dafür, dass der Faktor bei t größer ist als bei C: Caches funktionieren besser bei kurzen Listen.
Messwerte/Faktor dazwischen:
limit A C t
1250000 5110 78139 0.196s
8 4.008 16.3183 2.18
10000000 20480 1275098 0.428s
8 4.001 16.1345 7.75
80000000 81937 20573083 3.316s
8 4.002 16.1052 9.44
640000000 327889 331332685 31.298s
Weiterhin: A~O(limit2/3), C~O(limit4/3), t~O(limit4/3) (wirkt sich bei t erst bei grossem limit aus, da bei kleinem limit auch nennenswert Zeit ausserhalb von get() verbracht wird).
Aber die konstanten Faktoren für C und t sind deutlich anders (Faktor zwischen den C-Werten):
1250000 10000000 80000000
ListTable 12893829 207795013 3334249330
165.01 162.96 162.07
HashTable 78139 1275098 20573083
Der C-Faktor ist hier kleiner als 256, weil sich die Einträge nicht völlig gleich auf die Buckets (Einträge im Hash-Tabellen-Array) verteilen.
Allerdings kann man die algorithmische Komplexität hier leicht ändern, indem man die Anzahl der Buckets von limit abhängen läßt. Wenn die Anzahl der Buckets mit O(limit2/3) steigt, dann sollte die erwartete Anzahl der Elemente pro bucket O(1) ("konstant") betragen und C mit O(limit2/3) steigen.
limit A C t
1250000 5110 14381 0.208s
8 4.008 1.77 1.21
10000000 20480 25476 0.252s
8 4.001 7.27 1.94
80000000 81937 185098 0.488s
8 4.002 2.21 2.07
640000000 327889 408269 1.008s
Insgesamt ist der C-Faktor zwischen limit=1250000 und limit=640000000
gleich 28.39 (erwartet: Faktor 64).
In der Praxis ist die Anzahl der Einträge nicht so gut vorhersagbar wie bei diesem Beispiel. Daher setzt man gerne Hash-Tabellen ein, bei denen die Anzahl der Buckets verdoppelt wird, wenn die durchschnittliche Zahl der Einträge pro Bucket (load-factor) eine Grenze überschreitet.
Algorithmische Komplexität: get, put: O(ln(n)) bei balanciertem Baum, O(n) bei degeneriertem Baum. Beim Taxi-Problem ist der Baum nicht gut balanciert:
limit A C t
1250000 5110 448003 0.244s
8 4.008 7.77 1.54
10000000 20480 3482773 0.376s
8 4.001 7.77 3.79
80000000 81937 27068328 1.424s
8 4.002 7.80 10.00
640000000 327889 211217842 14.245s
Algorithmisches Prinizp: Teile und Herrsche (Skriptum 4.4).
Kein remove() in TreeTable: kompliziert, und die einfachste Version führt zu unbalancierten Bäumen.
Balancierte Bäume durch entsprechendes put: möglich, aber kompliziert.
Mergesort (Skriptum 4.4)
Beipsiel: TreeTable.toString() und TreeTable.toList(); hier sieht man auch, dass eine verkettete Liste am einfachsten vom Ende her aufgebaut wird.
Vorsicht: Rekursion bei Listen und degenerierten Bäumen benötigt O(|Knoten|) Zwischenspeicher.
Mit Schleifen (und tail recursion) geht nur das Vorwärtsgehen in einer Liste, mit allgemeiner Rekursion vorwärts und rückwärts. Beispiel: Klammern
Besonders wenn mehr als eine Datenstruktur im Spiel ist, kann man u.U. den Kontrollfluss nicht an alle Datenstrukturen, die im Spiel sind, anpassen. Beispiel: gleichzeitiges Iterieren über zwei Bäume, die unterschiedlich aufgebaut sind, z.B., Ausgabe der Elemente zweier Suchbäume in sortierter Reihenfolge.
Iteratoren ermöglichen es, Datenstrukturen einfach abzuwandern (und auch mehrere zugleich). Allerdings muss man für eigene Datenstrukturen Iteratoren erst programmieren. Damit ergibt sich erst recht das Problem, dass man einen nicht zur Datenstruktur passende Kontrollfluss hat (aber wenigstens nur an einer Stelle und dort nicht vermischt mit anderen Aufgaben).
Beim konventionellen Programmieren eines Iterators muss man den Zustand des Kontrollflusses an der Stelle, an der next() das Resultat liefert, als Daten repräsentieren. Beispiel (mit Verfeinerungen): TreeTable.TTI2
Zweck:
Beispiel: counter
Wenn man solche Zustände doch behandeln will (oder zumindest noch aufräumen will), kann man Exceptions auch fangen. Beispiel. Eigene Exception-Klassen machen, um sie fangen zu können:
Bei Exceptions kommt es auf den Aufrufbaum zur Laufzeit an (dynamic Scoping). Beispiel
For Beginners: Don't do it
For Experts: Don't do it now
Aber: Effizienzaspekte nicht völlig ignorieren.
Häufiger Fehler: Viel Aufwand in die Optimierung eines Teiles stecken, der wenig kostet.
Häufiger Fehler: Optimierungstipps blind anwenden. Cargo-cult programming.
Vorlesung zu dem Thema: Effiziente Programme.