Viele Programmieraufgaben können auf mehr als eine Art erledigt werden, aber die eine Art kann unter Umständen viel schneller sein als eine andere. Schnelle Programme zu entwerfen gehört zu den zentralen Aufgaben der Programmierung und der Informatik. Wir sehen uns in dieser Einheit einige Beispiele hierfür an.

Teil 1: Berechne die selbe Sache nicht zweimal

Die Fibonacci-Folge ist eine faszinierend einfache Zahlenreihe. Du fängst mit zwei Zahlen an, 1 und 1. Danach gilt: um zur nächsten Zahl zu kommen, addiere die vorherigen beiden. Also ist die nächste Zahl 1+1=2. Die ersten drei Zahlen sind also

1, 1, 2

die vierte Zahl ist 1+2=3, dann haben wir 2+3=5, und so weiter:

1, 1, 2, 3, 5, 8, 13, ...

Die Fibonacci-Folge wurde ursprünglich erfunden, um Kaninchenpopulationen zu beschreiben, und sie hat interessante Verbindungen zur Architektur von verschiedenen Pflanzen. Hier ist ein Teil einer fantastischen Videoreihe über die Fibonacci-Folge:

Aus der Definition der Fibonacci-Folge lässt sich leicht eine rekursive Funktion ableiten. Die nächste Übung definiert eine Funktion Fibonacci(n) , um das n-te Element in der obigen Liste aufzurufen (beginnend mit n=1).

Es ist aber so, dass die rekursive Funktion zu langsam wird, um Einträge weiter unten in der Folge zu berechnen. Klicke auf "Testbefehle eingeben" und tippe print(Fibonacci(80)) ein. Wenn du diesen Befehl testest, bekommst du "Time Limit Exceeded." raus.

Warum geht das so langsam? Die Funktion hat keine komplizierten Anweisungen oder Schleifen, nur Addition. Also stellt sich heraus, dass die Langsamkeit in Beziehung dazu steht, wie oft die Funktion aufgerufen wird. Wenn wir Fibonacci(3) aufrufen, wird die rekursive Funktion insgesamt drei Mal aufgerufen: der initialisierende Aufruf, dann zwei rekursive Aufrufe. Wenn wir Fibonacci(4)aufrufen, wird die rekursive Funktion insgesamt fünf Mal aufgerufen: der initialisierende Aufruf, dann die drei Aufrufe, die wir gerade für n=3 erwähnt haben, und einen weiteren rekursiven Aufruf mit n=2. Wenn wir Fibonacci(5) berechnen, unternehmen wir insgesamt neun Aufrufe, und Fibonacci(6) ergibt eine Gesamtzahl an 9+5+1=15 Aufrufen. Die Anzahl der Aufrufe wird schnell sehr groß, wenn n größer wird!

Als ungefährer Schätzwert: Fibonacci(n+2) braucht mindestens doppelt so viele rekursive Aufrufe wie Fibonacci(n), weil Fibonacci(n+2) nämlich Fibonacci(n) einmal direkt aufruft, und ein anderes Mal indirekt durch den rekursiven Aufruf von Fibonacci(n+1). Also ist die Rechenzeit proportional zu einer exponentiellen Funktion, die mindestens so groß ist wie (√2)ⁿ. Das ist zu langsam! Zum Beispiel: Fibonacci(80) benötigt mehr als 2⁴⁰ = 1099511627776 rekursive Aufrufe.

Das obige Argument weist auf das entscheidende Problem hin: es ist überflüssig, Fibonacci(n) zweimal aufzurufen und die Antwort beim zweiten Mal komplett neu zu berechnen. Wir sollten uns eine Lösung einfallen lassen, bei der wir eben nicht Zeit damit verschwenden, die selbe Sache immer wieder neu zu berechnen.

Die Lösung

Lass uns versuchen, etwas in Python zu schreiben, das eher dem ähnelt, was wir in der Einleitung beschrieben haben. Wir hatten ja damit angefangen, 1, 1 aufzuschreiben. Dann haben wir die Folge erweitert, indem wir die letzen beiden Elemente miteinander addiert hatten. Der Code sieht dann folgendermaßen aus (du musst ihn wieder entwirren):

Es ist natürlich immer noch Raum für Verbesserungen, weil wir nicht die ganze Liste neu berechnen müssen bei jedem neuen Aufruf, aber es ist erst einmal gut genug, weil es schnell läuft, auch für große Werte von n!

Teil 2: Berechne keine überflüssigen Dinge, nicht ein einziges Mal.

Bei unserem zweiten Beispiel geht es darum, zu überprüfen, ob Zahlen Primzahlen sind. Das ist besonders wichtig im Bereich der Kryptographie und Computersicherheit. Eine Zahl ist genau dann eine Primzahl, wenn sie genau zwei Faktoren hat: 1 und sie selbst. Die ersten paar Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23. (21 ist keine Primzahl, weil sie die Faktoren 3 und 7 hat, sowie 1 und 21.)

Wie können wir mit Python überprüfen, ob eine Zahl eine Primzahl ist? Wir haben früher bereits gesehen, wie man Teilbarkeit berechnet

N % D == 0 # ist True falls D ein Teiler von N ist, sonst False

Mit dem folgenden Programm suchen wir systematisch, ob es für eine Zahl einen Teiler gibt (dann ist sie keine Primzahl):

Es funktioniert! Aber es ist auch zu langsam, soweit es große Zahlen betrifft. Wähle Testeingabe und tippe isItPrime(324635459) ins Eingabefenster. Das Programm wird nicht rechtzeitig fertig. Probiere das gleiche nochmal mit anderen Werten...du siehst, für Primzahlen, die größer sind als ungefähr 10000000, wird der Code nie fertig, weil der Bewerter die Teilbarkeits-Überprüfungsschleife nur 10 Millionen mal pro Sekunde ausführen kann. Wenn wir größere Zahlen überprüfen wollen, brauchen wir eine effizientere Idee. Lass uns den Code so schreiben, dass er sogar für Zahlen wie eine Billion funktioniert (1 000 000 000 000)!

Müssen wir wirklich alle Zahlen zwischen 2 und N-1 überprüfen, um herauszufinden, ob N eine Primzahl ist? Hinweis

Die Idee - und ein Argument

Wenn du den Hinweis gelesen hast und ein bißchen experimentiert hast, hast du vielleicht gemerkt, dass, wenn N keine Primzahl ist, das Programm üblicherweise einen ziemlich kleinen Teiler (verglichen mit N) gefunden hat. Zum Beispiel läuft die Funktion isItPrime(34827948723948723984729834) ziemlich schnell, obwohl die Eingabe riesig ist, und findet den Teiler D=2.

Vielleicht müssen wir gar nicht alle möglichen Teiler überprüfen. Gibt es vielleicht eine Regel, um die Zahl der Teiler einzuschränken, die wir überprüfen müssen, bevor wir sicher sein können, dass N eine Primzahl ist? Gottseidank ja! Es stellt sich nämlich heraus, dass, wenn N keine Primzahl ist, einer seiner Teiler maximal sqrt(N) beträgt. Warum? Naja, wenn N keine Primzahl ist, dann hat sie den Teiler A. Ein Teiler sein bedeutet, dass es eine andere Zahl B solcherart gibt, dass

A*B == N

Lass uns das Argument fortführen. Falls A <= sqrt(N) oder B <= sqrt(N), dann sind wir glücklich: wir haben einen Teiler von N gefunden, der klein ist, genau wie geplant. Und das ist auch die einzige Möglichkeit, denn andernfalls erhalten wir den Widerspruch

N = A*B > sqrt(N)*sqrt(N) > N

Toll! Also lass uns jetzt diese neue Idee in Python implementieren. Die einfachste Möglichkeit, das alte Vorgehen zu ändern, ist es, einen Test innerhalb der for Schleife zu erstellen: wenn D > sqrt(N) (oder gleichwertig, D*D > N), können wir einfach die Schleife verlassen (englisch: break out) und mit der Überprüfung aufhören.

Das Programm funktioniert jetzt auch für gigantische Primzahlen!

Letzte Übung

In dieser Übung kombinieren wir die Primzahlen der zweiten Hälfte dieser Lektion mit der listen-basierten Herangehensweise der ersten Hälfte. Dein Code sollte eine Tabelle der Länge 1000001 ausfüllen, so dass isPrime[N] gleich True ist, wenn N eine Primzahl ist, und False, wenn N teilbar ist, für alle N bis zu einer Million. (isPrime[0] und isPrime[1] sollte False sein.)

Klicke hier, um einen Tipp zu erhalten. Es ist ein ziemlich guter Tipp!

Dies ist die letze Übung auf der CSCircles Seite. Glückwünsche an alle, die alle Übungen bewältigt haben! Seht euch die Nachlesen-Seite an, wenn ihr Hinweise wollt, was ihr als nächstes machen könnt. Viel Spaß, viel Glück und gutes Coden!