Der Bericht, der plötzlich lange dauert
Ein Bericht lief im Test in einer Sekunde. Nach dem Start mit echten Daten dauert er eine Stunde.
Der Code ist derselbe, nur die Daten sind größer. Manche Verfahren vertragen das, andere nicht. Diese Lektion zeigt, wie Sie das vorher erkennen.
Am Ende dieser Lektion
Notiz
Ich kann vergleichen, wie der Aufwand zweier Algorithmen mit den Daten wächst.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Schritt | eine kleine, einzelne Arbeit des Computers, etwa ein Vergleich |
| Wachstum | wie die Schritte zunehmen, wenn die Daten zunehmen |
| Linear | doppelt so viele Daten, doppelt so viele Schritte |
| Logarithmisch | Daten verdoppeln, nur ein Schritt mehr |
| Schlechtester Fall | die höchste Zahl an Schritten, die vorkommen kann |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Sie zählen Schritte, keine Sekunden
Wie lange ein Programm braucht, hängt vom Rechner ab. Ein neuer Laptop ist schneller als ein alter.
Darum zählen wir Schritte. Die Zahl bleibt gleich, auf jedem Rechner. Wir fragen: Wie viele Schritte braucht das Verfahren bei 10, 100 und 1000 Einträgen? Dieses Wachstum ist die Antwort.
Probieren Sie es: Schritte der linearen Suche
# Schritte zählen: lineare Suche, schlechtester Fall.
def schritte_linear(anzahl):
schritte = 0
for eintrag in range(anzahl):
schritte = schritte + 1
return schritte
for anzahl in [10, 100, 1000]:
print(anzahl, "Einträge ->", schritte_linear(anzahl), "Schritte")
# Fügen Sie 10000 in die Liste ein und drücken Sie Run.
Halbieren wächst kaum
Die binäre Suche halbiert den Rest bei jedem Schritt. Wie oft lässt sich 1000 halbieren, bis nichts mehr übrig ist? Etwa zehnmal.
Verdoppeln sich die Daten, kommt nur ein Schritt dazu. Das nennt man logarithmisches Wachstum. Es bleibt auch bei riesigen Daten klein.
Probieren Sie es: Halbierungen zählen
# Schritte zählen: wie oft lässt sich eine Zahl halbieren?
def schritte_halbieren(anzahl):
schritte = 0
rest = anzahl
while rest >= 1:
rest = rest // 2
schritte = schritte + 1
return schritte
for anzahl in [10, 100, 1000, 1000000]:
print(anzahl, "Einträge ->", schritte_halbieren(anzahl), "Schritte")
# Bei einer Million sind es nur etwa 20 Schritte.
Beispiel: zwei Verfahren im Vergleich
| Einträge | Lineare Suche | Binäre Suche |
|---|---|---|
| 10 | 10 Schritte | 4 Schritte |
| 100 | 100 Schritte | 7 Schritte |
| 1000 | 1000 Schritte | 10 Schritte |
| 1.000.000 | 1.000.000 Schritte | 20 Schritte |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, das Verfahren mit weniger Schritten sei immer das bessere. Bei 10 Einträgen ist der Unterschied winzig, und die binäre Suche braucht eine sortierte Liste. Das Wachstum zählt erst bei großen Daten. Fragen Sie: Wie groß werden die Daten?
Was Sie später lernen können
Listen, Stapel, Schlangen, Wörterbücher und Mengen sind der Grundstock. Für andere Aufgaben gibt es weitere Strukturen.
Ein Baum ordnet Daten in Ästen an, so wie Ordner und Unterordner. Ein Graph verbindet Punkte durch Linien, etwa Stationen im Verkehrsnetz. Beides sind eigene Themen für später.