Vorlesung 7: Laufzeit, Maps

Angewandte Informa/k für Ingenieure/-‐innen

Michael Zilske

Angenommen, ich möchte •  eine Textdatei einlesen (zum Beispiel einen Roman), •  die Häufigkeiten aller unterschiedlichen vorkommenden

Wörter zählen, •  diese Wörter mit ihren Häufigkeiten als Rangliste ausgeben.

the 12231 to 11979 of 10565 and 10285 a 6627 was 5341 in 5334 I 5206 her 5015 not 4115 be 4078

public static void main(String[] args) throws IOException {new CorpusCount().run();

}void run() throws IOException {

readFile("files/emma.txt");readFile("files/sense.txt");readFile("files/persuasion.txt");sort();write();

}

Ich habe mir also drei Jane-‐Austen-‐Romane aus dem Internet besorgt. Weil ich die nacheinander bearbeiten will, schreibe ich mir eine separate Methode readFile(). Danach will ich die gesammelten Daten sor/eren und dann herausschreiben. Da diese Methoden Dateiopera/onen ausführen, deklarieren sie IOExcep/ons. Ich deklariere sie weiter.

void readFile(String filename) throws IOException {FileReader fr = new FileReader(filename);BufferedReader br = new BufferedReader(fr);String line;while ((line = br.readLine()) != null) { String[] words = line.split(" "); for (String word : words) { countWord(word); }}br.close();

}

Diese Methode haben wir im Prinzip letzte Woche schon gesehen. Man muss Reader und Writer übrigens, wenn man sie nicht mehr braucht, mit close() schließen, denn Dateizugriffe sind vom Betriebssystem verwaltete, beschränkte Ressourcen.

private class Entry {String word;int count;

}private void countWord(String word) {

Entry entry = findEntry(word);entry.count++;

}

Was ich berechnen möchte, ist eine Tabelle, deren Einträge Wörter mit ihren (bisherigen) Häufigkeiten sind. Für jedes Wort, das ich einlese, suche ich den entsprechenden Eintrag heraus und erhöhe den Zähler. Für die Tabellenzeile eignet sich eine eigene Klasse Entry. Ich kann eine Klasse innerhalb einer anderen Klasse definieren – wenn ich sie private deklariere, ist sie nur innerhalb der umschließenden Klasse sichtbar. Prima für einmalige Dinge wie Tabellenzeilen!




}

Vorteil einer solchen Konstruk/on (private Klasse): Ich brauche nicht darüber nachzudenken, wie sie verwendet werden könnte. Im Uhrenladenbeispiel habe ich gesagt, es ist gut, Felder immer als private zu deklarieren, um nur kontrollierten Zugriff darauf zu erlauben (wie bei der Uhr, die man nur zerstören, aber nicht reparieren kann). Bei einer privaten Klasse ist das unnö/g, denn alle sta]indenden Zugriffe stehen in derselben Datei, also gibt es nichts zu kontrollieren. Ich kann munter direkt die Felder verwenden.




}

Wie finde ich nun meinen Eintrag, bzw. wie verwalte ich meine Einträge überhaupt?


}List<Entry> entries = new ArrayList<Entry>();private void countWord(String word) {


}private Entry findEntry(String word) {

for (Entry entry : entries) { if (word.equals(entry.word)) { return entry; }}Entry entry = new Entry();entry.word = word;entries.add(entry);return entry;

}

List<Entry> entries = new ArrayList<Entry>();private Entry findEntry(String word) {

for (Entry entry : entries) { if (word.equals(entry.word)) { return entry; }}Entry entry = new Entry();entry.word = word;entries.add(entry);return entry;

}

Das ist eine völlig legi/me Art, mit den bisher gelernten Mi_eln das Problem zu lösen. Es wird für ein gegebenes Wort ein bisher vorhandener Eintrag gesucht. Wenn keiner vorhanden ist, wird einer angelegt. Warum braucht man “equals”, warum reicht nich “==“?

public static void main(String[] args) {String a = new String(new char[]{'h','e','l','l','o'});String b = new String(new char[]{'h','e','l','l','o'});System.out.println(a == b);System.out.println(a.equals(b));b = a;System.out.println(a == b);

}falsetruetrue

String ist ein Objek_yp. Das heißt, == vergleicht, ob die Variablen a und b dasselbe Objekt im Speicher bezeichnen. Zwei unterschiedliche String-‐Objekte im Speicher können aber durchaus für die gleiche Zeichenke_e stehen. Und das ist die Art Gleichheit, die uns hier interessiert.

Diese Schreibweise ini/alisiert ein Array mit den

angegebenen Werten.

public static void main(String[] args) {String c = "Hello";String d = "Hello";System.out.println(c == d);

}true Das ist eine Anomalie: Strings, die ich als Wert in meinen Quellcode schreibe (sog. Literale, wie 5, 0.45, ‘a’ oder eben “abc”) werden vom Java-‐Compiler als iden/sch erkannt und tatsächlich nur einmal als Objekt angelegt. Dieser Code wird also intern umgeformt zu so etwas wie: public static void main(String[] args) {

String HELLO = "Hello";String c = HELLO;String d = HELLO;System.out.println(c == d);

}

... und damit ist das Verhalten wieder erklärt. Das nur am Rande.

public static void main(String[] args) throws IOException {new CorpusCount().run();

}void run() throws IOException {

readFile("files/emma.txt");readFile("files/sense.txt");readFile("files/persuasion.txt");sort();write();

}

readFile haben wir jetzt also im Griff. Jetzt schauen wir uns sort an.

List<Entry> entries = new ArrayList<Entry>();private class EntryComparator implements

Comparator<Entry> { public int compare(Entry arg0, Entry arg1) { return arg0.word.compareTo(arg1.word); }

}private void sort() throws IOException {

Collections.sort(entries, new EntryComparator());}

Collec/ons.sort ist eine sta/sche Methode, die eine Liste sor/ert. Neben dieser Liste benö/gt sie als Argument einen Vergleicher, das heißt, ein Objekt, das das Interface Comparator<T> implemen/ert, wobei T der Typ der Listenelemente ist. Das Interface Comparator<T> wiederum verlangt eine Methode compare(T a, T b).

java.utilInterface Comparator<T>int compare(T o1, T o2)Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.[...]

Mit einem solchen übergebenen Comparator wird bes/mmt, wonach die Liste sor/ert werden soll. In der Dokumenta/on des Interface Comparator wird bes/mmt, dass Klassen, die es implemen/eren, darauf achten müssen, dass compare eine totale Ordnung beschreibt.


Comparator<Entry> { public int compare(Entry arg0, Entry arg1) { return arg0.word.compareTo(arg1.word);}

}private void sort() throws IOException {

Collections.sort(entries, new EntryComparator());}

In diesem Beispiel wird zunächst alphabe/sch sor/ert. String hat prak/scherweise eine compareTo-‐Methode, an die wir den Vergleich delegieren können, wenn wir nach dem String-‐Feld word sor/eren wollen.


Comparator<Entry> {

public int compare(Entry arg0, Entry arg1) { if (arg0.count < arg1.count) return -1; else if (arg0.count > arg1.count) return 1; else return 0;}

}

Wenn wir nach dem int-‐Feld count sor/eren wollen, müssen wir leider die Bedingung ausschreiben. int ist kein Objek_yp und hat daher keine compareTo-‐Methode (oder sonst irgendwelche Methoden). Eine Methode Integer.compare(a, b) gibt es leider erst in Java 7.


Comparator<Entry> {

public int compare(Entry arg0, Entry arg1) { if (arg0.count < arg1.count) return 1; else if (arg0.count > arg1.count) return -1; else return 0;}

}

Eigentlich wollen wir aber absteigend sor/eren, also müssen wie das Vorzeichen umdrehen, so dass der Eintrag mit der größeren Zahl als kleiner gilt.

private void write() throws IOException {FileWriter fw = new FileWriter("files/words.txt");BufferedWriter bw = new BufferedWriter(fw);for (Entry entry : entries) { bw.write(entry.word + "\t" + entry.count); bw.newLine();}bw.close();

}

Fehlt nur noch die write-‐Methode. Hier gehen wir die mi_lerweile sor/erte Liste durch und geben sie aus.

Wie lange dauert das? void run() throws IOException {

long startTime = System.currentTimeMillis(); readFile("files/emma.txt"); readFile("files/sense.txt"); readFile("files/persuasion.txt"); long endTime = System.currentTimeMillis(); sort(); write(); System.out.println("Total execution time: " + (endTime - startTime) );

}

Wie lange dauert das? void run() throws IOException {

long startTime = System.currentTimeMillis(); readFile("files/emma.txt"); readFile("files/sense.txt"); readFile("files/persuasion.txt"); long endTime = System.currentTimeMillis(); sort(); write(); System.out.println("Total execution time: " + (endTime - startTime) );

}Total execution time: 5744

Auf meinem Rechner: 5,7 Sekunden.

Das ist eigentlich schon ziemlich schnell. Ich bin überrascht. Anscheinend sind Laptops so schnell, dass dicke Bücher als Beispiel für “große Datenmengen” nicht taugen. Trotzdem: Bekommen wir es schneller? Überlegen wir uns, was da passiert:

String line;while ((line = br.readLine()) != null) {

String[] words = line.split(" ");for (String word : words) { countWord(word);}

}br.close();

Jede Zeile, und jedes Wort wird einzeln verarbeitet. Daran kommen wir nicht vorbei, wenn wir Wörter zählen wollen. Aber bekommen wir die Methode countWord() schneller?

private void countWord(String word) {Entry entry = findEntry(word);entry.count++;nWords++;

}

CountWord bleibt auch nicht viel anderes übrig, als den Eintrag herauszusuchen und zu erhöhen. Aber bekommen wir findEntry schneller?

private Entry findEntry(String word) {for (Entry entry : entries) { if (word.equals(entry.word)) { return entry; }}Entry entry = new Entry();entry.word = word;entries.add(entry);return entry;

}

Wir suchen einen Eintrag in der Wortliste, indem wir sie von vorne nach hinten dursuchen. Das ist nicht effizient, insbesondere dauert diese Opera/on länger, je mehr Wörter schon im Katalog stehen. Im schlimmsten Fall, also wenn das Wort noch gar nicht vorhanden ist, wird die Liste einmal ganz durchgegangen.

Hypothese: Das Programm wird allmählich langsamer, je mehr Daten wir schon verarbeitet haben, weil die Wortliste sich füllt und somit jedes Wort mit der Zeit im Schni_ länger gesucht werden muss.

private void countWord(String word) {Entry entry = findEntry(word);entry.count++;nWords++;if (nWords % 10000 == 0) { final long currentTime = System.currentTimeMillis(); System.out.println("Intermediate execution time: ” + (currentTime - checkpointTime) ); checkpointTime = currentTime;}

}

private void countWord(String word) {Entry entry = findEntry(word);entry.count++;nWords++;if (nWords % 10000 == 0) { final long currentTime = System.currentTimeMillis(); System.out.println("Intermediate execution time: ” + (currentTime - checkpointTime) ); checkpointTime = currentTime;}

}Intermediate execution time: 83Intermediate execution time: 79Intermediate execution time: 89Intermediate execution time: 97Intermediate execution time: 110Intermediate execution time: 122Intermediate execution time: 124Intermediate execution time: 140Intermediate execution time: 152Intermediate execution time: 152Intermediate execution time: 102Intermediate execution time: 115Intermediate execution time: 112Intermediate execution time: 115Intermediate execution time: 123Intermediate execution time: 122Intermediate execution time: 198...

In der Tat. Zumindest tendenziell und am Anfang. In eine genaue Analyse würde natürlich mehr hineinspielen: Irgendwann wurden alle gängigen englischen Wörter gesehen, so dass sich nicht mehr viel ändert, insbesondere wurden die gängigsten Wörter schon ziemlich früh gesehen und damit auch schneller gefunden, usw. Man begnügt sich aber normalerweise mit einer worst-‐case Analyse: Bei einem künstlichen Text, der nur unterschiedliche Wörter enthält, würde dieses Programm pro Wort immer langsamer werden.

Die Lösung Eine Liste, in der linear nach Einträgen gesucht wird, ist keine adäquate Datenstruktur für dieses Problem. Was wir brauchen, ist keine Liste, sondern eine Indexstruktur, in der auf Einträge unter einem besAmmten Suchschlüssel effizient zugegriffen werden kann. Diese Strukturen sind in Java die Maps. Map<String, Entry> map = new HashMap<String,Entry>();

Map<String, Entry> entriesMap = new HashMap<String, Entry>();private Entry findEntry(String word) {

Entry entry = entriesMap.get(word);if (entry == null) { entry = new Entry(); entry.word = word; entriesMap.put(word, entry);}return entry;

}

Abgesehen vom Effizienzgewinn wird auch der Code einfacher. Die for-‐Schleife ist weg. Mit Map.get wird ein Eintrag (Wert) unter einem Schlüssel nachgeschlagen. Mit Map.put wird er hinzugefügt. Die beiden Typparameter (genau behandeln wir die später) geben den Schlüsseltyp und den Wer_yp an. Dies hier ist eine Map von String nach Entry.

private void sort() {entries = new ArrayList<Entry>(entriesMap.values());Collections.sort(entries, new EntryComparator());

}

Zum Sor/eren erzeuge ich weiterhin meine Liste (dann muss ich auch den Code für das Herausschreiben nicht ändern). Dieser Konstruktor von ArrayList erzeugt eine Liste basierend auf einer bestehenden Liste, und Map.values() liefert eine Liste, die aus allen Werten der Map besteht.

Intermediate execution time: 46Intermediate execution time: 25Intermediate execution time: 20Intermediate execution time: 17Intermediate execution time: 9Intermediate execution time: 13Intermediate execution time: 5Intermediate execution time: 5Intermediate execution time: 4Intermediate execution time: 9Intermediate execution time: 10Intermediate execution time: 10Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 1Intermediate execution time: 2Intermediate execution time: 10Intermediate execution time: 3Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 1Intermediate execution time: 2Intermediate execution time: 7Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 2Intermediate execution time: 1Intermediate execution time: 2Intermediate execution time: 5Total execution time: 238

Und wie es sich lohnt: Es dauert jetzt nur noch 0,2 Sekunden sta_ 5. Die Entwicklung über die Laufzeit ist auch völlig anders: Das Programm wird eher schneller. Vermutlich, weil die Laufzeit nun nicht mehr durch das Suchen dominiert wird, sondern durch das Hinzufügen neuer Wörter (und davon kommen später nicht mehr so viele).

Collections.sort(entries, new EntryComparator());

kann man auch schreiben:

Sta_

Collections.sort(entries, new Comparator<Entry>() {public int compare(Entry arg0, Entry arg1) { if (arg0.count < arg1.count) return 1; else if (arg0.count > arg1.count) return -1; else return 0;}

});

Hier wird eine sogenannte anonyme Klasse übergeben (weil sie den Namen (EntryComparator) hier gar nicht bekommt). Das ist gut geeignet für Klassen wie diese, von denen man nur ein einziges Objekt erzeugt, um es an eine Methode zu übergeben, und die man danach nie wieder benutzt.

Bleibt zu erklären: Wie macht die HashMap das?

Wikipedia: Hash Table

Die Einträge werden zu sogenannten Hashwerten verschlüsselt. Die HashMap ist im Prinzip ein Array aus Listen, und in der Liste an einer Arrayposi/on n sind alle Werte, deren Hashwert n ist. Die genauen Eigenschauen dieser Struktur hängen von der Wahl der Hashfunk/on ab. Die Analyse sprengt hier den Rahmen, aber diese Struktur ist immer dann Mi_el der Wahl, wenn Dinge nachgeschlagen werden sollen.

Documents

Vorlesung 7: Laufzeit, Maps