Hackschule Workspace
Anmelden Handbuch
ProjektBaut auf Katas: Dictionaries und Katas: Rekursion aufIm Handbuch: Terminal: Dateien und Verzeichnisse
image: teaser.webp image_alt: "Ein Terminal, in dem messen.rb läuft: eine Tabelle mit der Zahl der Straßennamen, den drei Arten zu zählen und ihren Zeiten; die Liste braucht für 64 000 Namen zwei Sekunden, die Menge ein Hundertstel davon" kind: projekt language: Ruby / Python / Dart / Java languages: [ruby, python, dart, java] duration: 3 Doppelstunden curriculum: "Oberstufe: Algorithmen und Datenstrukturen (Aufwand, Laufzeit messen und abschätzen, Mengen und Dictionaries), Vertiefung Theoretische Informatik (Komplexität, P und NP)" topics: [suchen-sortieren, datenstrukturen, berechenbarkeit] requires: [kata-dicts, kata-recursion] age: Oberstufe reference: [terminal]

Wie lange dauert das? Laufzeit und Aufwand

Wie viele verschiedene Straßennamen hat Berlin? Du beantwortest die Frage auf drei Arten, die alle richtig sind, und misst, wie lange jede braucht. Dann zählst du Schritte statt Sekunden, siehst, wie schnell manche Programme unbrauchbar werden, machst langsame schnell und planst eine Rundfahrt zu Berlins Sehenswürdigkeiten, für die es keine schnelle Lösung gibt, die jemand kennt.

1. Einrichten

Leg einen Ordner an und hol die Straßen Berlins, aus dem Datensatz des Routenplaners: eine Zeile für jedes Stück Straße, mit seinem Namen in der dritten Spalte. cut schneidet diese Spalte heraus, grep lässt die Stücke ohne Namen weg:

mkdir -p /workspace/laufzeit
cd /workspace/laufzeit
wget https://github.com/specht/workspace-files/raw/main/street-archive/berlin.tsv.gz
gunzip berlin.tsv.gz
cut -f3 berlin.tsv | grep -v '^$' > strassen.txt
wc -l strassen.txt

strassen.txt hat 102 763 Zeilen: Jede Straße steht so oft darin, wie sie Stücke hat, und manche Namen gibt es in mehreren Bezirken.

Deine Funktionen schreibst du in laufzeit.rb.

Deine Funktionen schreibst du in laufzeit.py.

Deine Funktionen schreibst du in laufzeit.dart.

Deine Methoden schreibst du in Laufzeit.java, in eine Klasse Laufzeit. Oben in die Datei gehört import java.util.*;, für Listen, Mengen und Maps.

2. Dreimal dieselbe Frage

Wie viele verschiedene Straßennamen sind es? Die erste Art ist die, die man sich selbst ausdenkt: eine Liste der Namen, die man schon kennt, und bei jedem Namen nachsehen, ob er darin steht.

Aufgabe 1Mit einer Liste

Schreib in laufzeit.rb eine Funktion distinct_list(names), die zählt, wie viele verschiedene Namen in der Liste names stehen. Sie merkt sich in einer zweiten Liste, welche Namen sie schon gesehen hat, und fragt diese Liste bei jedem Namen, ob er schon darin steht.

Tipp

Eine leere Liste seen = []; für jeden Namen: Steht er noch nicht darin, seen.include?(name), kommt er hinein.

Nächster Tipp

Am Ende ist die Zahl der verschiedenen Namen seen.size.

Aufgabe 1Mit einer Liste

Schreib in laufzeit.py eine Funktion distinct_list(names), die zählt, wie viele verschiedene Namen in der Liste names stehen. Sie merkt sich in einer zweiten Liste, welche Namen sie schon gesehen hat, und fragt diese Liste bei jedem Namen, ob er schon darin steht.

Tipp

Eine leere Liste seen = []; für jeden Namen: Steht er noch nicht darin, if name not in seen:, kommt er hinein.

Nächster Tipp

Am Ende ist die Zahl der verschiedenen Namen len(seen).

Aufgabe 1Mit einer Liste

Schreib in laufzeit.dart eine Funktion int distinctList(List<String> names), die zählt, wie viele verschiedene Namen in der Liste names stehen. Sie merkt sich in einer zweiten Liste, welche Namen sie schon gesehen hat, und fragt diese Liste bei jedem Namen, ob er schon darin steht.

Tipp

Eine leere Liste final seen = <String>[];; für jeden Namen: Steht er noch nicht darin, !seen.contains(name), kommt er hinein.

Nächster Tipp

Am Ende ist die Zahl der verschiedenen Namen seen.length.

Aufgabe 1Mit einer Liste

Schreib in Laufzeit.java, in der Klasse Laufzeit, eine Methode public static int distinctList(List<String> names), die zählt, wie viele verschiedene Namen in der Liste names stehen. Sie merkt sich in einer zweiten Liste, welche Namen sie schon gesehen hat, und fragt diese Liste bei jedem Namen, ob er schon darin steht.

Tipp

Eine leere Liste List<String> seen = new ArrayList<>();; für jeden Namen: Steht er noch nicht darin, !seen.contains(name), kommt er hinein. Oben in die Datei gehört import java.util.*;.

Nächster Tipp

Am Ende ist die Zahl der verschiedenen Namen seen.size().

Die zweite Art sortiert zuerst. Danach muss niemand mehr suchen: Gleiche Namen stehen nebeneinander, und es genügt, jeden mit dem davor zu vergleichen.

Aufgabe 2Erst sortieren

Schreib distinct_sorted(names), die dasselbe zählt, aber anders: Sie sortiert die Namen zuerst. Dann stehen gleiche Namen nebeneinander, und ein neuer Name beginnt dort, wo einer anders ist als der davor.

Tipp

sorted = names.sort gibt eine sortierte Kopie. Gezählt wird jeder Name, der anders ist als der davor, und der erste.

Nächster Tipp

sorted.each_with_index do |name, i| gibt jeden Namen mit seinem Index; der davor ist sorted[i - 1], und beim ersten, i == 0, gibt es keinen davor.

Aufgabe 2Erst sortieren

Schreib distinct_sorted(names), die dasselbe zählt, aber anders: Sie sortiert die Namen zuerst. Dann stehen gleiche Namen nebeneinander, und ein neuer Name beginnt dort, wo einer anders ist als der davor.

Tipp

ordered = sorted(names) gibt eine sortierte Kopie. Gezählt wird jeder Name, der anders ist als der davor, und der erste.

Nächster Tipp

for i, name in enumerate(ordered): gibt jeden Namen mit seinem Index; der davor ist ordered[i - 1], und beim ersten, i == 0, gibt es keinen davor.

Aufgabe 2Erst sortieren

Schreib int distinctSorted(List<String> names), die dasselbe zählt, aber anders: Sie sortiert die Namen zuerst. Dann stehen gleiche Namen nebeneinander, und ein neuer Name beginnt dort, wo einer anders ist als der davor.

Tipp

final sorted = [...names]..sort(); ist eine sortierte Kopie. Gezählt wird jeder Name, der anders ist als der davor, und der erste.

Nächster Tipp

for (var i = 0; i < sorted.length; i++) gibt jeden Index; der Name davor ist sorted[i - 1], und beim ersten, i == 0, gibt es keinen davor.

Aufgabe 2Erst sortieren

Schreib public static int distinctSorted(List<String> names), die dasselbe zählt, aber anders: Sie sortiert die Namen zuerst. Dann stehen gleiche Namen nebeneinander, und ein neuer Name beginnt dort, wo einer anders ist als der davor.

Tipp

List<String> sorted = new ArrayList<>(names); ist eine Kopie, Collections.sort(sorted); sortiert sie. Gezählt wird jeder Name, der anders ist als der davor, und der erste.

Nächster Tipp

for (int i = 0; i < sorted.size(); i++) gibt jeden Index; der Name davor ist sorted.get(i - 1), und beim ersten, i == 0, gibt es keinen davor. Texte vergleicht man mit equals.

Die dritte Art nimmt eine Menge, die jeden Namen nur einmal enthält. Wie ein Dictionary findet sie einen Namen, ohne die anderen anzusehen: Sie rechnet aus dem Namen aus, wo er liegen müsste, und schaut nur dort nach.

Aufgabe 3Mit einer Menge

Schreib distinct_set(names), die die Namen in eine Menge legt, ein Set. Eine Menge enthält jeden Namen nur einmal, und ob sie einen schon hat, weiß sie, ohne zu suchen. Die Zahl der verschiedenen Namen ist dann ihre Größe.

Tipp

Ganz oben in der Datei require 'set', dann seen = Set.new.

Nächster Tipp

Jeder Name kommt mit seen << name hinein; ein Name, der schon darin ist, kommt nicht zweimal hinein. Am Ende ist seen.size die Antwort.

Aufgabe 3Mit einer Menge

Schreib distinct_set(names), die die Namen in eine Menge legt, ein set. Eine Menge enthält jeden Namen nur einmal, und ob sie einen schon hat, weiß sie, ohne zu suchen. Die Zahl der verschiedenen Namen ist dann ihre Größe.

Tipp

Eine leere Menge ist seen = set().

Nächster Tipp

Jeder Name kommt mit seen.add(name) hinein; ein Name, der schon darin ist, kommt nicht zweimal hinein. Am Ende ist len(seen) die Antwort.

Aufgabe 3Mit einer Menge

Schreib int distinctSet(List<String> names), die die Namen in eine Menge legt, ein Set. Eine Menge enthält jeden Namen nur einmal, und ob sie einen schon hat, weiß sie, ohne zu suchen. Die Zahl der verschiedenen Namen ist dann ihre Größe.

Tipp

Eine leere Menge ist <String>{}.

Nächster Tipp

Jeder Name kommt mit seen.add(name) hinein; ein Name, der schon darin ist, kommt nicht zweimal hinein. Am Ende ist seen.length die Antwort.

Aufgabe 3Mit einer Menge

Schreib public static int distinctSet(List<String> names), die die Namen in eine Menge legt, ein Set. Eine Menge enthält jeden Namen nur einmal, und ob sie einen schon hat, weiß sie, ohne zu suchen. Die Zahl der verschiedenen Namen ist dann ihre Größe.

Tipp

Eine leere Menge ist Set<String> seen = new HashSet<>();.

Nächster Tipp

Jeder Name kommt mit seen.add(name) hinein; ein Name, der schon darin ist, kommt nicht zweimal hinein. Am Ende ist seen.size() die Antwort.

3. Messen

Alle drei geben dieselbe Zahl. Aber wie lange brauchen sie? Bevor du misst:

Vermutung 4Doppelt so viele Namen

Wie viel länger braucht distinct_list für 2000 Namen als für 1000, wenn alle Namen verschieden sind?

Vermutung 4Doppelt so viele Namen

Wie viel länger braucht distinct_list für 2000 Namen als für 1000, wenn alle Namen verschieden sind?

Vermutung 4Doppelt so viele Namen

Wie viel länger braucht distinctList für 2000 Namen als für 1000, wenn alle Namen verschieden sind?

Vermutung 4Doppelt so viele Namen

Wie viel länger braucht distinctList für 2000 Namen als für 1000, wenn alle Namen verschieden sind?

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Bei jedem neuen Namen fragt die erste Art ihre Liste, und die Liste sieht jeden Namen an, den sie schon hat. Bei doppelt so vielen Namen sind es doppelt so viele Fragen, und jede dauert doppelt so lange, weil die Liste doppelt so lang ist: zusammen viermal so lange.

messen ruft deine drei Funktionen für die ersten 1000 Namen auf, dann für 2000, 4000 und so weiter, und schreibt jede Zeit auf. Der »Faktor« sagt, um wie viel die Zeit gewachsen ist, seit die Zahl der Namen das letzte Mal verdoppelt wurde:

wget https://workspace.hackschule.de/laufzeit/starter/messen.rb
ruby messen.rb

wget https://workspace.hackschule.de/laufzeit/starter/messen.py
python3 messen.py

wget https://workspace.hackschule.de/laufzeit/starter/messen.dart
dart run messen.dart

wget https://workspace.hackschule.de/laufzeit/starter/Messen.java
java Messen.java
Aufgabe 5Was die Messung zeigt

Lass messen laufen und sieh dir die Spalte »Faktor« von distinct_list an: Um wie viel wächst die Zeit, wenn sich die Zahl der Namen verdoppelt?

Aufgabe 5Was die Messung zeigt

Lass messen laufen und sieh dir die Spalte »Faktor« von distinct_list an: Um wie viel wächst die Zeit, wenn sich die Zahl der Namen verdoppelt?

Aufgabe 5Was die Messung zeigt

Lass messen laufen und sieh dir die Spalte »Faktor« von distinctList an: Um wie viel wächst die Zeit, wenn sich die Zahl der Namen verdoppelt?

Aufgabe 5Was die Messung zeigt

Lass messen laufen und sieh dir die Spalte »Faktor« von distinctList an: Um wie viel wächst die Zeit, wenn sich die Zahl der Namen verdoppelt?

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Am Anfang ist fast jeder Name neu, und die Liste wächst mit: viermal so lange. Aber Berlin hat nur 11 772 verschiedene Straßennamen. Sind die meisten erst einmal in der Liste, wird sie kaum noch länger, und jeder neue Name kostet ungefähr gleich viel: doppelt so viele Namen, doppelt so lange. Wie viel ein Verfahren kostet, hängt also auch von den Daten ab. Mit 64 000 Namen braucht die Liste trotzdem rund hundertmal so lange wie die Menge.

Ausprobieren: Eine Messung schwankt: Läuft gerade etwas anderes, dauert es länger, und ein Programm ist beim zweiten Mal oft schneller als beim ersten. hyperfine lässt ein Programm mehrmals laufen und sagt, wie lange es im Mittel braucht und wie sehr das schwankt,
etwa hyperfine 'ruby messen.rb'.
etwa hyperfine 'python3 messen.py'.
etwa hyperfine 'dart run messen.dart'.
etwa hyperfine 'java Messen.java'.
Achte darauf, wie weit die einzelnen Läufe auseinanderliegen.
Bei den ersten, kleinen Zeilen von messen ist der Faktor oft seltsam, manchmal kleiner als 1: Ein Programm in dieser Sprache wird beim Laufen noch einmal übersetzt, und Code, der oft läuft, wird dabei schneller.

4. Zählen statt messen

Sekunden hängen vom Rechner ab, von der Sprache und davon, was nebenher läuft. Wie viele Schritte ein Programm macht, hängt nur vom Programm und seiner Eingabe ab. Man zählt darum Schritte, zum Beispiel, wie oft eine Zeile in der innersten Schleife läuft:

Vermutung 6Wie oft läuft die innere Zeile? 
count = 0
(0...n).each do |i|
  (0...i).each do |j|
    count += 1
  end
end

Welchen Wert hat count am Ende, wenn n gleich 1000 ist?

Vermutung 6Wie oft läuft die innere Zeile? 
count = 0
for i in range(n):
    for j in range(i):
        count += 1

Welchen Wert hat count am Ende, wenn n gleich 1000 ist?

Vermutung 6Wie oft läuft die innere Zeile? 
var count = 0;
for (var i = 0; i < n; i++) {
  for (var j = 0; j < i; j++) {
    count++;
  }
}

Welchen Wert hat count am Ende, wenn n gleich 1000 ist?

Vermutung 6Wie oft läuft die innere Zeile? 
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}

Welchen Wert hat count am Ende, wenn n gleich 1000 ist?

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Für i = 0 läuft die innere Schleife gar nicht, für i = 1 einmal, für i = 999 999-mal: zusammen 0 + 1 + … + 999 = 999 · 1000 / 2 = 499 500. Das ist rund die Hälfte von n², und bei doppelt so großem n wieder viermal so viel.

Auf die genaue Zahl kommt es selten an, nur darauf, wie sie mit n wächst. Man schreibt dafür O(n²), gesprochen »O von n Quadrat«: höchstens so schnell wie n², bis auf einen festen Faktor. Die Hälfte von n² ist auch O(n²), und O(n²) heißt immer: doppelt so viel Eingabe, viermal so viel Arbeit.

Aufwand woran man ihn erkennt Beispiel
O(1) keine Schleife über die Eingabe in einer Menge nachsehen
O(log n) bei jedem Schritt bleibt die Hälfte binäre Suche
O(n) eine Schleife über die Eingabe distinct_set
O(n log n) gutes Sortieren distinct_sorted
O(n²) eine Schleife in einer Schleife distinct_list, wenn alle Namen verschieden sind
O(2ⁿ) jede Teilmenge ausprobieren, zwei Aufrufe in jeder Rekursion fib ohne Gedächtnis
O(n!) jede Reihenfolge ausprobieren die Rundfahrt unten
Aufwand woran man ihn erkennt Beispiel
O(1) keine Schleife über die Eingabe in einer Menge nachsehen
O(log n) bei jedem Schritt bleibt die Hälfte binäre Suche
O(n) eine Schleife über die Eingabe distinctSet
O(n log n) gutes Sortieren distinctSorted
O(n²) eine Schleife in einer Schleife distinctList, wenn alle Namen verschieden sind
O(2ⁿ) jede Teilmenge ausprobieren, zwei Aufrufe in jeder Rekursion fib ohne Gedächtnis
O(n!) jede Reihenfolge ausprobieren die Rundfahrt unten

5. Wie schnell der Aufwand wächst

Wie groß der Unterschied wird, siehst du hier. Schieb n größer und schau, in welcher Zeile die Zeit zuerst unbrauchbar wird:

Vermutung 7Zehnmal so viel

Ein Programm mit einem Aufwand von n² braucht für 1000 Namen eine Sekunde. Wie lange braucht es für 10 000?

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Zehnmal so viel Eingabe heißt bei n² hundertmal so viel Arbeit: 100 Sekunden. Bei n wären es zehn Sekunden, bei 2ⁿ wäre das Programm für 10 000 Namen nie fertig geworden.

6. Schneller machen

Ein langsames Programm wird selten schneller, weil der Rechner schneller wird: Bei n² heißt ein doppelt so schneller Rechner nur, dass n um gut 40 Prozent größer sein darf. Schneller wird es, wenn es weniger tut. Zwei Tricks helfen oft: sich merken, was man schon ausgerechnet hat, und eine Menge oder ein Dictionary statt einer Liste, in der man sucht.

Die Fibonacci-Zahlen aus den Katas zur Rekursion, so wie man sie zuerst schreibt:

def fib(n)
  return n if n < 2
  fib(n - 1) + fib(n - 2)
end

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

int fib(int n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

public static long fib(int n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

fib(40) ruft fib(39) und fib(38) auf, fib(39) wieder fib(38), und so rechnet das Programm dieselben Zahlen viele Millionen Mal aus. Probier fib(30), fib(35) und fib(40) aus und achte darauf, um wie viel es jedes Mal länger dauert.

Aufgabe 8Fibonacci mit Gedächtnis

Die Fibonacci-Zahlen aus den Katas zur Rekursion: fib(0) ist 0, fib(1) ist 1, jede weitere ist die Summe der beiden davor. Rekursiv geschrieben ruft fib(n) fib(n - 1) und fib(n - 2) auf, und die rechnen dieselben Zahlen immer wieder aus. Schreib fib_memo(n), die sich jede Zahl merkt, sobald sie ausgerechnet ist, so dass fib_memo(90) sofort fertig ist.

Tipp

Das Gedächtnis ist ein Dictionary, memo = {}, das jeder Aufruf weitergibt: def fib_memo(n, memo = {}) und innen fib_memo(n - 1, memo).

Nächster Tipp

Steht n schon in memo, gibt die Funktion den Wert von dort zurück; sonst rechnet sie ihn aus und trägt ihn ein: memo[n] ||= fib_memo(n - 1, memo) + fib_memo(n - 2, memo).

Aufgabe 8Fibonacci mit Gedächtnis

Die Fibonacci-Zahlen aus den Katas zur Rekursion: fib(0) ist 0, fib(1) ist 1, jede weitere ist die Summe der beiden davor. Rekursiv geschrieben ruft fib(n) fib(n - 1) und fib(n - 2) auf, und die rechnen dieselben Zahlen immer wieder aus. Schreib fib_memo(n), die sich jede Zahl merkt, sobald sie ausgerechnet ist, so dass fib_memo(90) sofort fertig ist.

Tipp

Das Gedächtnis ist ein Dictionary, das jeder Aufruf weitergibt: def fib_memo(n, memo=None):, beim ersten Aufruf memo = {}, und innen fib_memo(n - 1, memo). (Ein memo={} als Vorgabe würde Python nur einmal anlegen und für alle Aufrufe behalten.)

Nächster Tipp

Steht n schon in memo, gibt die Funktion memo[n] zurück; sonst rechnet sie den Wert aus, trägt ihn ein und gibt ihn zurück.

Aufgabe 8Fibonacci mit Gedächtnis

Die Fibonacci-Zahlen aus den Katas zur Rekursion: fib(0) ist 0, fib(1) ist 1, jede weitere ist die Summe der beiden davor. Rekursiv geschrieben ruft fib(n) fib(n - 1) und fib(n - 2) auf, und die rechnen dieselben Zahlen immer wieder aus. Schreib int fibMemo(int n, [Map<int, int>? memo]), die sich jede Zahl merkt, sobald sie ausgerechnet ist, so dass fibMemo(90) sofort fertig ist. […] macht memo zu einem Parameter, den man weglassen darf.

Tipp

Das Gedächtnis ist eine Map, die jeder Aufruf weitergibt: Beim ersten Aufruf fehlt sie, memo ??= {}; legt dann eine an, und innen ruft die Funktion fibMemo(n - 1, memo) auf.

Nächster Tipp

Steht n schon in memo, gibt die Funktion den Wert von dort zurück; sonst rechnet sie ihn aus und trägt ihn ein: return memo[n] ??= fibMemo(n - 1, memo) + fibMemo(n - 2, memo);.

Aufgabe 8Fibonacci mit Gedächtnis

Die Fibonacci-Zahlen aus den Katas zur Rekursion: fib(0) ist 0, fib(1) ist 1, jede weitere ist die Summe der beiden davor. Rekursiv geschrieben ruft fib(n) fib(n - 1) und fib(n - 2) auf, und die rechnen dieselben Zahlen immer wieder aus. Schreib public static long fibMemo(int n), die sich jede Zahl merkt, sobald sie ausgerechnet ist, so dass fibMemo(90) sofort fertig ist. Sie gibt long zurück, denn fib(90) passt nicht in ein int.

Tipp

Das Gedächtnis ist eine Map, die jeder Aufruf weitergibt: fibMemo(n) ruft eine zweite Methode fibMemo(int n, Map<Integer, Long> memo) mit new HashMap<>() auf, und die ruft sich selbst mit derselben Map auf.

Nächster Tipp

Steht n noch nicht in memo, rechnet sie den Wert aus und trägt ihn ein, memo.put(n, …); dann gibt sie memo.get(n) zurück.

Aufgabe 9Zwei, die zusammenpassen

Schreib pair_with_sum?(numbers, target): Gibt es in der Liste zwei Zahlen an verschiedenen Stellen, die zusammen target ergeben? Mit zwei Schleifen ineinander ginge es, aber die Prüfung gibt deiner Funktion 200 000 Zahlen. Geh die Liste einmal durch und merk dir in einer Menge, welche Zahlen du schon gesehen hast.

Tipp

Für jede Zahl x passt genau eine andere: target - x. Die Frage ist nur, ob sie schon vorkam.

Nächster Tipp

Eine Menge seen = Set.new; für jede Zahl: Ist target - x in seen, gibt es ein Paar; sonst kommt x hinein. Erst danach, so zählt keine Zahl doppelt.

Aufgabe 9Zwei, die zusammenpassen

Schreib has_pair_with_sum(numbers, target): Gibt es in der Liste zwei Zahlen an verschiedenen Stellen, die zusammen target ergeben? Mit zwei Schleifen ineinander ginge es, aber die Prüfung gibt deiner Funktion 200 000 Zahlen. Geh die Liste einmal durch und merk dir in einer Menge, welche Zahlen du schon gesehen hast.

Tipp

Für jede Zahl x passt genau eine andere: target - x. Die Frage ist nur, ob sie schon vorkam.

Nächster Tipp

Eine Menge seen = set(); für jede Zahl: Ist target - x in seen, gibt es ein Paar; sonst kommt x hinein. Erst danach, so zählt keine Zahl doppelt.

Aufgabe 9Zwei, die zusammenpassen

Schreib bool pairWithSum(List<int> numbers, int target): Gibt es in der Liste zwei Zahlen an verschiedenen Stellen, die zusammen target ergeben? Mit zwei Schleifen ineinander ginge es, aber die Prüfung gibt deiner Funktion 200 000 Zahlen. Geh die Liste einmal durch und merk dir in einer Menge, welche Zahlen du schon gesehen hast.

Tipp

Für jede Zahl x passt genau eine andere: target - x. Die Frage ist nur, ob sie schon vorkam.

Nächster Tipp

Eine Menge final seen = <int>{};; für jede Zahl: Ist target - x in seen, gibt es ein Paar; sonst kommt x hinein. Erst danach, so zählt keine Zahl doppelt.

Aufgabe 9Zwei, die zusammenpassen

Schreib public static boolean pairWithSum(List<Integer> numbers, int target): Gibt es in der Liste zwei Zahlen an verschiedenen Stellen, die zusammen target ergeben? Mit zwei Schleifen ineinander ginge es, aber die Prüfung gibt deiner Methode 200 000 Zahlen. Geh die Liste einmal durch und merk dir in einer Menge, welche Zahlen du schon gesehen hast.

Tipp

Für jede Zahl x passt genau eine andere: target - x. Die Frage ist nur, ob sie schon vorkam.

Nächster Tipp

Eine Menge Set<Integer> seen = new HashSet<>();; für jede Zahl: Ist target - x in seen, gibt es ein Paar; sonst kommt x hinein. Erst danach, so zählt keine Zahl doppelt.

7. Eine Rundfahrt durch Berlin

Jetzt ein Problem, für das niemand eine schnelle Lösung kennt: Du willst mehrere Sehenswürdigkeiten besuchen und am Ende wieder am Anfang sein. In welcher Reihenfolge ist die Rundfahrt am kürzesten? Das ist das Problem des Handlungsreisenden. Der Routenplaner löst es auf den echten Straßen; hier geht es um die Luftlinie, und darum, wie die Zeit wächst.

Die Entfernung zweier Orte in Kilometern, aus ihrer Länge und Breite:

def distance(a, b)
  dx = (b[1] - a[1]) * 111.32 * Math.cos((a[2] + b[2]) / 2 * Math::PI / 180)
  dy = (b[2] - a[2]) * 110.57
  Math.hypot(dx, dy)
end

def distance(a, b):
    dx = (b[1] - a[1]) * 111.32 * math.cos((a[2] + b[2]) / 2 * math.pi / 180)
    dy = (b[2] - a[2]) * 110.57
    return math.hypot(dx, dy)

Dazu steht import math oben in der Datei.

Ein Ort ist ein Record aus Namen, Länge und Breite, mit einem Namen für seinen Typ:

typedef Place = ({String name, double lon, double lat});

double distance(Place a, Place b) {
  final dx = (b.lon - a.lon) * 111.32 * cos((a.lat + b.lat) / 2 * pi / 180);
  final dy = (b.lat - a.lat) * 110.57;
  return sqrt(dx * dx + dy * dy);
}

Dazu steht import 'dart:math'; oben in der Datei.

Ein Ort ist ein Record aus Namen, Länge und Breite; beides gehört in die Klasse Laufzeit:

public record Place(String name, double lon, double lat) {}

public static double distance(Place a, Place b) {
    double dx = (b.lon() - a.lon()) * 111.32 * Math.cos((a.lat() + b.lat()) / 2 * Math.PI / 180);
    double dy = (b.lat() - a.lat()) * 110.57;
    return Math.hypot(dx, dy);
}

Ein Grad Breite ist überall etwa 110,6 km lang, ein Grad Länge in Berlin nur knapp 68 km, weil die Längenkreise zu den Polen hin zusammenlaufen; darum der Kosinus.

Aufgabe 10Wie lang ist eine Rundfahrt?

Ein Ort ist eine Liste aus Namen, Länge und Breite, ["Brandenburger Tor", 13.377705, 52.516276], und eine Rundfahrt eine Liste der Nummern der Orte, [0, 2, 1]: vom Ort 0 zum Ort 2, von dort zum Ort 1 und zurück zum Ort 0. Kopier die Funktion distance(a, b) von oben in laufzeit.rb und schreib tour_length(tour, places), die die Länge einer Rundfahrt in Kilometern ausrechnet.

Tipp

Gezählt wird jeder Schritt von einem Ort zum nächsten in der Liste: vom Ort tour[i] zum Ort tour[i + 1].

Nächster Tipp

Der letzte Schritt geht zurück zum ersten Ort: tour[(i + 1) % tour.size] ist beim letzten Index wieder tour[0].

Aufgabe 10Wie lang ist eine Rundfahrt?

Ein Ort ist eine Liste aus Namen, Länge und Breite, ["Brandenburger Tor", 13.377705, 52.516276], und eine Rundfahrt eine Liste der Nummern der Orte, [0, 2, 1]: vom Ort 0 zum Ort 2, von dort zum Ort 1 und zurück zum Ort 0. Kopier die Funktion distance(a, b) von oben in laufzeit.py und schreib tour_length(tour, places), die die Länge einer Rundfahrt in Kilometern ausrechnet.

Tipp

Gezählt wird jeder Schritt von einem Ort zum nächsten in der Liste: vom Ort tour[i] zum Ort tour[i + 1].

Nächster Tipp

Der letzte Schritt geht zurück zum ersten Ort: tour[(i + 1) % len(tour)] ist beim letzten Index wieder tour[0].

Aufgabe 10Wie lang ist eine Rundfahrt?

Ein Ort ist ein Record aus Namen, Länge und Breite, (name: 'Brandenburger Tor', lon: 13.377705, lat: 52.516276), vom Typ Place, und eine Rundfahrt eine Liste der Nummern der Orte, [0, 2, 1]: vom Ort 0 zum Ort 2, von dort zum Ort 1 und zurück zum Ort 0. Kopier Place und die Funktion distance(a, b) von oben in laufzeit.dart und schreib double tourLength(List<int> tour, List<Place> places), die die Länge einer Rundfahrt in Kilometern ausrechnet.

Tipp

Gezählt wird jeder Schritt von einem Ort zum nächsten in der Liste: vom Ort tour[i] zum Ort tour[i + 1].

Nächster Tipp

Der letzte Schritt geht zurück zum ersten Ort: tour[(i + 1) % tour.length] ist beim letzten Index wieder tour[0].

Aufgabe 10Wie lang ist eine Rundfahrt?

Ein Ort ist ein Place aus Namen, Länge und Breite, new Place("Brandenburger Tor", 13.377705, 52.516276), und eine Rundfahrt eine Liste der Nummern der Orte, List.of(0, 2, 1): vom Ort 0 zum Ort 2, von dort zum Ort 1 und zurück zum Ort 0. Kopier Place und die Methode distance(a, b) von oben in die Klasse Laufzeit und schreib public static double tourLength(List<Integer> tour, List<Place> places), die die Länge einer Rundfahrt in Kilometern ausrechnet.

Tipp

Gezählt wird jeder Schritt von einem Ort zum nächsten in der Liste: vom Ort tour.get(i) zum Ort tour.get(i + 1).

Nächster Tipp

Der letzte Schritt geht zurück zum ersten Ort: tour.get((i + 1) % tour.size()) ist beim letzten Index wieder tour.get(0).

Aufgabe 11Alle Reihenfolgen

Schreib best_tour(places), die die kürzeste Rundfahrt findet, indem sie alle ausprobiert. Der erste Ort bleibt vorn; die anderen kommen in jeder Reihenfolge dahinter.

Tipp

(1...places.size).to_a.permutation gibt alle Reihenfolgen der Orte außer dem ersten. Vor jede kommt die 0.

Nächster Tipp

Von allen Rundfahrten die mit der kleinsten Länge: min_by { |tour| tour_length(tour, places) }.

Aufgabe 11Alle Reihenfolgen

Schreib best_tour(places), die die kürzeste Rundfahrt findet, indem sie alle ausprobiert. Der erste Ort bleibt vorn; die anderen kommen in jeder Reihenfolge dahinter.

Tipp

Ganz oben import itertools; itertools.permutations(range(1, len(places))) gibt alle Reihenfolgen der Orte außer dem ersten. Vor jede kommt die 0: [0] + list(order).

Nächster Tipp

Von allen Rundfahrten die mit der kleinsten Länge: min(tours, key=lambda tour: tour_length(tour, places)).

Aufgabe 11Alle Reihenfolgen

Schreib List<int> bestTour(List<Place> places), die die kürzeste Rundfahrt findet, indem sie alle ausprobiert. Der erste Ort bleibt vorn; die anderen kommen in jeder Reihenfolge dahinter.

Tipp

Alle Reihenfolgen einer Liste: eine Funktion Iterable<List<int>> permutations(List<int> items) sync*, rekursiv wie die Reihenfolgen eines Textes in den Katas zur Rekursion. Mit sync* gibt sie jede Reihenfolge mit yield heraus, sobald sie fertig ist, statt alle in einer Liste zu sammeln. Für die Orte 1 bis places.length - 1; vor jede kommt die 0.

Nächster Tipp

Von allen Rundfahrten die mit der kleinsten Länge: Merk dir die bisher kürzeste und ihre Länge, und nimm eine neue nur, wenn sie kürzer ist.

Aufgabe 11Alle Reihenfolgen

Schreib public static List<Integer> bestTour(List<Place> places), die die kürzeste Rundfahrt findet, indem sie alle ausprobiert. Der erste Ort bleibt vorn; die anderen kommen in jeder Reihenfolge dahinter.

Tipp

Alle Reihenfolgen einer Liste: eine Methode static List<List<Integer>> permutations(List<Integer> items), rekursiv wie die Reihenfolgen eines Textes in den Katas zur Rekursion. Für die Orte 1 bis places.size() - 1; vor jede kommt die 0.

Nächster Tipp

Von allen Rundfahrten die mit der kleinsten Länge: Merk dir die bisher kürzeste und ihre Länge, und nimm eine neue nur, wenn sie kürzer ist.

rundfahrt holt die Sehenswürdigkeiten aus dem Datensatz der Orte und plant mit deinen Funktionen eine Rundfahrt zu den ersten n davon, auf beide Arten, mit der Zeit, die jede braucht:

wget https://github.com/specht/workspace-files/raw/main/street-archive/berlin-places.tsv
wget https://workspace.hackschule.de/laufzeit/starter/rundfahrt.rb
ruby rundfahrt.rb 8

wget https://github.com/specht/workspace-files/raw/main/street-archive/berlin-places.tsv
wget https://workspace.hackschule.de/laufzeit/starter/rundfahrt.py
python3 rundfahrt.py 8

wget https://github.com/specht/workspace-files/raw/main/street-archive/berlin-places.tsv
wget https://workspace.hackschule.de/laufzeit/starter/rundfahrt.dart
dart run rundfahrt.dart 8

wget https://github.com/specht/workspace-files/raw/main/street-archive/berlin-places.tsv
wget https://workspace.hackschule.de/laufzeit/starter/Rundfahrt.java
java Rundfahrt.java 8

rundfahrt ruft auch nearestTour auf, die du erst gleich schreibst, und ohne sie lässt es sich nicht übersetzen. Bis dahin genügt eine, die die kürzeste zurückgibt:

List<int> nearestTour(List<Place> places) => bestTour(places);

Rundfahrt.java ruft auch nearestTour auf, die du erst gleich schreibst, und ohne sie lässt es sich nicht übersetzen. Die Prüfung übersetzt jede Java-Datei im Ordner, also auch diese. Bis dahin genügt eine, die die kürzeste zurückgibt:

public static List<Integer> nearestTour(List<Place> places) {
    return bestTour(places);
}

Noch fehlt die zweite Art. Vorher:

Vermutung 12Drei Orte mehr

Für zehn Orte probiert best_tour 9 · 8 · 7 · … · 1 = 362 880 Reihenfolgen aus und braucht dafür etwa anderthalb Sekunden. Wie lange braucht es für 13 Orte?

Vermutung 12Drei Orte mehr

Für zehn Orte probiert best_tour 9 · 8 · 7 · … · 1 = 362 880 Reihenfolgen aus und braucht dafür etwa anderthalb Sekunden. Wie lange braucht es für 13 Orte?

Vermutung 12Drei Orte mehr

Für zehn Orte probiert bestTour 9 · 8 · 7 · … · 1 = 362 880 Reihenfolgen aus und braucht dafür etwa eine halbe Sekunde. Wie lange braucht es für 13 Orte?

Vermutung 12Drei Orte mehr

Für zehn Orte probiert bestTour 9 · 8 · 7 · … · 1 = 362 880 Reihenfolgen aus und braucht dafür etwa eine Sekunde. Wie lange braucht es für 13 Orte?

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Bei 11 Orten sind es zehnmal so viele Reihenfolgen wie bei 10, bei 12 noch einmal elfmal so viele, bei 13 zwölfmal. Dazu hat jede Rundfahrt 13 statt 10 Strecken, die zusammengezählt werden: 10 · 11 · 12 · 13 / 10, also 11 · 12 · 13 = 1716-mal so viel Arbeit, 1,5 s · 1716, rund 43 Minuten. Mit 20 Orten wären es Zehntausende Jahre. O(n!) wächst schneller als alles in der Tabelle oben.

Bei 11 Orten sind es zehnmal so viele Reihenfolgen wie bei 10, bei 12 noch einmal elfmal so viele, bei 13 zwölfmal. Dazu hat jede Rundfahrt 13 statt 10 Strecken, die zusammengezählt werden: 10 · 11 · 12 · 13 / 10, also 11 · 12 · 13 = 1716-mal so viel Arbeit, 0,5 s · 1716, rund eine Viertelstunde. Mit 20 Orten wären es Zehntausende Jahre. O(n!) wächst schneller als alles in der Tabelle oben.

Bei 11 Orten sind es zehnmal so viele Reihenfolgen wie bei 10, bei 12 noch einmal elfmal so viele, bei 13 zwölfmal. Dazu hat jede Rundfahrt 13 statt 10 Strecken, die zusammengezählt werden: 10 · 11 · 12 · 13 / 10, also 11 · 12 · 13 = 1716-mal so viel Arbeit, 1 s · 1716, rund eine halbe Stunde. Mit 20 Orten wären es Zehntausende Jahre. O(n!) wächst schneller als alles in der Tabelle oben.

Aufgabe 13Immer zum nächsten Ort

Schreib nearest_tour(places): Vom ersten Ort aus geht die Rundfahrt immer zu dem Ort, der am nächsten liegt und an dem sie noch nicht war. Sie probiert nichts aus und ist darum schnell, aber nicht immer die kürzeste.

Tipp

Die Rundfahrt beginnt mit [0]; eine zweite Liste hält die Orte, an denen sie noch nicht war, left = (1...places.size).to_a.

Nächster Tipp

Solange left nicht leer ist: der nächste Ort zum letzten der Rundfahrt, left.min_by { |i| distance(places[tour.last], places[i]) }, kommt hinten an die Rundfahrt und aus left heraus.

Aufgabe 13Immer zum nächsten Ort

Schreib nearest_tour(places): Vom ersten Ort aus geht die Rundfahrt immer zu dem Ort, der am nächsten liegt und an dem sie noch nicht war. Sie probiert nichts aus und ist darum schnell, aber nicht immer die kürzeste.

Tipp

Die Rundfahrt beginnt mit [0]; eine zweite Liste hält die Orte, an denen sie noch nicht war, left = list(range(1, len(places))).

Nächster Tipp

Solange left nicht leer ist: der nächste Ort zum letzten der Rundfahrt, min(left, key=lambda i: distance(places[tour[-1]], places[i])), kommt hinten an die Rundfahrt und aus left heraus.

Aufgabe 13Immer zum nächsten Ort

Schreib List<int> nearestTour(List<Place> places): Vom ersten Ort aus geht die Rundfahrt immer zu dem Ort, der am nächsten liegt und an dem sie noch nicht war. Sie probiert nichts aus und ist darum schnell, aber nicht immer die kürzeste.

Tipp

Die Rundfahrt beginnt mit [0]; eine zweite Liste hält die Orte, an denen sie noch nicht war: final left = [for (var i = 1; i < places.length; i++) i];.

Nächster Tipp

Solange left nicht leer ist: Such in left den Ort, der dem letzten der Rundfahrt, places[tour.last], am nächsten liegt; er kommt hinten an die Rundfahrt und mit left.remove(nearest) aus left heraus.

Aufgabe 13Immer zum nächsten Ort

Schreib public static List<Integer> nearestTour(List<Place> places): Vom ersten Ort aus geht die Rundfahrt immer zu dem Ort, der am nächsten liegt und an dem sie noch nicht war. Sie probiert nichts aus und ist darum schnell, aber nicht immer die kürzeste.

Tipp

Die Rundfahrt beginnt mit der 0, new ArrayList<>(List.of(0)); eine zweite Liste hält die Orte, an denen sie noch nicht war, die Nummern 1 bis places.size() - 1.

Nächster Tipp

Solange left nicht leer ist: Such in left den Ort, der dem letzten der Rundfahrt, places.get(tour.getLast()), am nächsten liegt; er kommt hinten an die Rundfahrt und mit left.remove(Integer.valueOf(nearest)) aus left heraus. Ohne Integer.valueOf nähme remove den Index, nicht die Zahl.

Ausprobieren: Vergleiche beide Arten für 8, 9 und 10 Orte. Achte darauf, um wie viel die Rundfahrt zum nächsten Ort länger ist als die kürzeste, und wie viel schneller sie fertig ist.
Aufgabe 14Wo es aufhört

Probier rundfahrt mit 8, 9, 10 und 11 Orten aus. Ab wie vielen Orten würdest du nicht mehr warten wollen, und was würdest du jemandem raten, der eine Rundfahrt zu allen 36 Sehenswürdigkeiten Berlins planen will?

Mindestens 25 Wörter. Nur du und deine Lehrkraft können die Antwort lesen.

8. Schnell prüfen, langsam finden

Bei der Rundfahrt fällt etwas auf: Ob eine Rundfahrt kürzer als 20 km ist, prüft man in einem Augenblick: Man rechnet ihre Länge aus. Eine zu finden, ist schwer. Das gilt für viele Probleme: einen Stundenplan ohne Überschneidungen, ein Sudoku, die beste Packung eines Koffers. Eine Lösung zu prüfen geht schnell, in polynomieller Zeit, O(n²) oder O(n³) etwa. Probleme mit dieser Eigenschaft heißen NP. Die, die sich auch schnell lösen lassen, heißen P.

Ob jedes Problem aus NP auch in P liegt, ob also jede Lösung, die sich schnell prüfen lässt, sich auch schnell finden lässt, weiß niemand. Die meisten Fachleute glauben es nicht. Gefragt hat es zuerst Stephen Cook 1971, und heute ist es eine der sieben Fragen, für deren Antwort das Clay Mathematics Institute eine Million Dollar ausgesetzt hat. Bis dahin hilft, was du mit der Rundfahrt zum nächsten Ort gebaut hast: eine Lösung, die gut genug ist, statt der besten.

9. Schneller geht es nicht Extra

Ein Extra für Schnelle. Wer es auslässt, springt zu Zum Nachschlagen.

Manchmal lässt sich beweisen, dass es nicht schneller geht. Ein Verfahren, das nur durch Vergleichen sortiert, muss unter allen n! möglichen Reihenfolgen die richtige finden, und jeder Vergleich teilt die Möglichkeiten höchstens in zwei Hälften. Nach k Vergleichen bleiben also mindestens n! / 2ᵏ, und erst wenn das 1 ist, ist es fertig: k ist mindestens log₂(n!), und das wächst wie n log n. Schneller als O(n log n) sortiert darum kein Verfahren, das nur vergleicht.

Und manche Fragen lassen sich gar nicht beantworten, so viel Zeit man auch hat: ob ein Programm irgendwann anhält oder für immer läuft, entscheidet kein Programm für alle Programme. Warum, zeigt das Halteproblem in Turingmaschinen.

10. Zum Nachschlagen