1.1 Lineare Suche

Um ein Gefühl dafür zu bekommen, warum man überhaupt sortieren muss, beschäftigen wir uns in diesem Kapitel erst einmal mit dem Suchen in unsortierten Daten.

Demo

Ich habe ein Programm Dictionary.java geschrieben, dass Dateien wie german-english-1000.txt einliest und dann Anfragen beantworten kann. 

java Dictionary german-english-1000.txt                            
arm
arm
reich
rich
bein
leg

wobei die schwarzen Zeilen "unsere" Eingabe darstellen und die blauen Zeilen die Ausgabe des Programms.

Demo

Wir betrachten die Datei english-words-58110.txt, eine sortierte Liste von 58.110 englischen Wörtern. Ich habe ein Java-Programm Set.java geschrieben, welches so eine Liste einlesen kann und dann Anfragen von der Kommandozeile einliest und beantwortet: 

java SortedSet english-words-58110.txt                            
arm
cat: true
bein
bein: false

und so weiter. Um unser Programm unter "Last" zu testen, nehmen wir die Datei german-50000.txt, eine unsortierte Liste von 50.000 deutschen Wörtern, und fragen dann für alle deutschen Wörter ab, ob sie in der englischen Wortmenge enthalten sind. Das Ergebnis sollte ungefähr so aussehen: 

java Set english-words-58110.txt < german-50000.txt | more                        
sind: false
war: true
von: false
wenn: false
dich: false
ihr: false
nein: false
habe: false
an: true
bin: true
noch: false

Als nächstes messen wir die Laufzeit unseres Programmes: 

time java Set english-words-58110.txt < german-50000.txt > /dev/null                            

real	2m47.048s
user	2m20.644s
sys	0m1.403s

Auf meinem Rechner braucht es über zwei Minuten, obwohl die Datenmengen jetzt auch nicht so riesig sind.

Quellen: github.com/hermitdave/FrequencyWords und www.mieliestronk.com.

Lassen Sie mich kurz die beiden Kommandozeilenbefehle erklären. Es handelt sich um Spezifika der Unix-Kommandozeile bash (ich verwende OSX, da gibt es das auch).
  • Den Befehl java Set english-words-58110.txt verstehen Sie wohl auch. Hier starte ich das Java-Programm Set. Das Argument english-words-58110.txt ist der Name der Datei, die die Daten für die Set-Datenstruktur enthält. Das Programm Set liest dann von der Kommandozeile.
  • Mit java Set english-words-58110.txt < german-50000.txt leite ich den Inhalt von german-50000.txt auf die Standardeingabe des Programms um; aus Sicht von Set.java sieht es so aus, als würde der Nutzer den Inhalt von german-50000.txt Zeile für Zeile in die Konsole eingeben.
  • Das | more schließlich erreicht, dass nicht die gesamte Ausgabe auf einmal ausgegeben wird, sondern immer nur Stück für Stück. Der Nutzer kann dann durch Drücken der Enter-Taste den Output weiterlaufen lassen.
  • In dem zweiten Kommandozeilenbefehl time java Set english-words-58110.txt < german-50000.txt > /dev/null verwenden wir > /dev/null um die Ausgabe des Programms zu unterdrücken. Dies ist insofern wichtig, weil in diesem Fall der Output sehr lang ist und ein Großteil der Laufzeit für die Ausgabe draufgehen würde. Wir unterdrücken jegliche Ausgabe und können somit die reine Rechenzeit präziser messen. Naja; unsere Messung erfasst auch die Zeit, die das Programm zum Einlesen der Daten braucht; dies fällt aber nicht so sehr ins Gewicht.
Übungsaufgabe

Wiederholen Sie die zwei obigen Experimente. Das heißt, implementieren Sie eine Klasse Dictionary.java, die eine Datei im Format von german-english-1000.txt einlesen und dann Anfragen beantworten kann. Tun Sie das gleiche für Set.java und Dateien im Format von english-words-58110.txt.

Hinweis. Das schwierigste an dieser Übung ist wahrscheinlich, Dateien im Format von german-english-1000.txt korrekt einzulesen. Dafür habe ich ein Beispielprogramm SeparateByCommas.java geschrieben, das dies mithilfe von Scanner und String.split erreicht, und an dem Sie sich orientieren können; es liest seine Daten von der Kommandozeile. Wenn Sie Beispielcode brauchen, wie man Daten aus einer Datei einliest, so orientieren Sie sich bitte an SeparateByCommasFromFile.java

Übungsaufgabe

Wiederholen Sie das ganze in Elm. Einlesen von Dateien und Zeit messen ist in Elm schwierig bis unmöglich, aber Sie können die Tabelle einfach roh in die Quelltextdatei kopieren. Am Besten laden Sie GermanEnglish.elm herunter und schreiben eine Funktion find in die gleiche Datei.