Python für die Bioinformatik beherrschen

Kapitel 4. Die Fibonacci-Folge erstellen: Schreiben, Testen und Benchmarking von Algorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Das Schreiben einer Implementierung der Fibonacci-Folge ist ein weiterer Schritt auf dem Weg des Helden zum Programmierer.In der Beschreibung von Rosalind Fibonacci heißt es, dass der Ursprung der Folge eine mathematische Simulation der Kaninchenzucht war, die auf einigen wichtigen (und unrealistischen) Annahmen beruht:

• Der erste Monat beginnt mit einem Paar neugeborener Kaninchen.

• Kaninchen können sich nach einem Monat fortpflanzen.

• Jeden Monat paart sich jedes Kaninchen im fortpflanzungsfähigen Alter mit einem anderen Kaninchen im fortpflanzungsfähigen Alter.

• Genau einen Monat, nachdem sich zwei Kaninchen gepaart haben, produzieren sie einen Wurf in der gleichen Größe.

• Kaninchen sind unsterblich und hören nie auf, sich zu paaren.

Die Sequenz beginnt immer mit den Zahlen 0 und 1. Die nachfolgenden Zahlen können ad infinitum erzeugt werden, indem die beiden unmittelbar vorhergehenden Werte in der Liste addiert werden, wie in Abbildung 4-1 gezeigt.

Abbildung 4-1. Die ersten acht Zahlen der Fibonacci-Folge - nach der anfänglichen 0 und 1 werden die nachfolgenden Zahlen durch Addition der beiden vorherigen Zahlen gebildet

Wenn du im Internet nach Lösungen suchst, wirst du Dutzende verschiedener Wege finden, die Sequenz zu generieren. Ich möchte mich auf drei recht unterschiedliche Ansätze konzentrieren. Die erste Lösung verwendet einen imperativen Ansatz, bei dem der Algorithmus jeden Schritt strikt vorgibt.Die nächste Lösung verwendet eine Generatorfunktion und die letzte konzentriert sich auf eine rekursive Lösung. Die Rekursion ist zwar interessant, verlangsamt sich aber drastisch, wenn ich versuche, mehr von der Sequenz zu generieren, aber es stellt sich heraus, dass die Leistungsprobleme durch Caching gelöst werden können.

Du wirst lernen:

• Wie man Argumente manuell validiert und Fehler auslöst

• Wie man eine Liste als Stapel verwendet

• Wie man eine Generatorfunktion schreibt

• Wie man eine rekursive Funktion schreibt

• Warum rekursive Funktionen langsam sein können und wie man dies mit Memoisierung beheben kann

• Wie man Funktionsdekoratoren verwendet

Erste Schritte

Der Code und die Tests für dieses Kapitel befinden sich im Verzeichnis 04_fib. Beginne damit, die erste Lösung nach fib.py zu kopieren:

$ cd 04_fib/
$ cp solution1_list.py fib.py

Frag nach der Verwendung, um zu sehen, wie die Parameter definiert sind. Du kannst n und k verwenden, aber ich habe mich für die Namen generations und litter entschieden:

$ ./fib.py -h
usage: fib.py [-h] generations litter

Calculate Fibonacci

positional arguments:
  generations  Number of generations
  litter       Size of litter per generation

optional arguments:
  -h, --help   show this help message and exit

Dies wird das erste Programm sein, das Argumente akzeptiert, die keine Zeichenketten sind. Die Rosalind-Herausforderung besagt, dass das Programm zwei positive ganzzahlige Werte akzeptieren soll:

• n ≤ 40 für die Anzahl der Generationen

• k ≤ 5 für die Wurfgröße, die von den Paarungspartnern produziert wird

Versuche, nicht ganzzahlige Werte zu übergeben und beobachte, wie das Programm fehlschlägt:

$ ./fib.py foo
usage: fib.py [-h] generations litter
fib.py: error: argument generations: invalid int value: 'foo'

Du kannst es nicht sehen, aber das Programm hat nicht nur die kurze Nutzung und eine hilfreiche Fehlermeldung ausgegeben, sondern auch einen Exit-Wert ungleich Null. Auf der Unix-Befehlszeile zeigt ein Exit-Wert von 0 Erfolg an. Ich stelle mir das als "null Fehler" vor. In der Shell bash kann ich die Variable $? untersuchen, um den Exit-Status des letzten Prozesses zu sehen. Der Befehl echo Hello sollte zum Beispiel mit einem Wert von 0 enden, und das tut er auch:

$ echo Hello
Hello
$ echo $?
0

Probiere den zuvor fehlgeschlagenen Befehl erneut aus und prüfe dann $?:

$ ./fib.py foo
usage: fib.py [-h] generations litter
fib.py: error: argument generations: invalid int value: 'foo'
$ echo $?
2

Dass der Exit-Status 2 lautet, ist nicht so wichtig wie die Tatsache, dass der Wert nicht Null ist. Dies ist ein braves Programm, denn es weist ein ungültiges Argument zurück, gibt eine nützliche Fehlermeldung aus und beendet sich mit einem Status ungleich Null. Wäre dieses Programm Teil einer Pipeline von Datenverarbeitungsschritten (wie z. B. ein Makefile, das in Anhang A besprochen wird), würde ein Exit-Wert ungleich Null dazu führen, dass der gesamte Prozess angehalten wird, was eine gute Sache ist. Programme, die stillschweigend ungültige Werte akzeptieren und stillschweigend oder gar nicht fehlschlagen, können zu nicht reproduzierbaren Ergebnissen führen. Es ist äußerst wichtig, dass Programme ihre Argumente richtig überprüfen und sehr überzeugend fehlschlagen, wenn sie nicht fortfahren können.

Das Programm ist sehr streng, was die Art der Zahlen angeht, die es akzeptiert. Die Werte müssen ganzzahlig sein. Es lehnt auch alle Fließkommazahlen ab:

$ ./fib.py 5 3.2
usage: fib.py [-h] generations litter
fib.py: error: argument litter: invalid int value: '3.2'

Alle Befehlszeilenargumente für das Programm werden technisch gesehen als Zeichenketten empfangen. Auch wenn 5 in der Befehlszeile wie die Zahl 5 aussieht, handelt es sich um das Zeichen "5". Ich verlasse mich in dieser Situation auf argparse, um zu versuchen, den Wert von einer Zeichenkette in eine ganze Zahl umzuwandeln. Wenn das fehlschlägt, erzeugt argparse diese nützlichen Fehlermeldungen.

Außerdem lehnt das Programm Werte für die Parameter generations und litter ab, die nicht in den zulässigen Bereichen liegen. Beachte, dass die Fehlermeldung den Namen des Arguments und den fehlerhaften Wert enthält, um dem Benutzer genügend Rückmeldung zu geben, damit du das Problem beheben kannst:

$ ./fib.py -3 2
usage: fib.py [-h] generations litter
fib.py: error: generations "-3" must be between 1 and 40 
$ ./fib.py 5 10
usage: fib.py [-h] generations litter
fib.py: error: litter "10" must be between 1 and 5 

Das Argument generations von -3 liegt nicht in dem angegebenen Wertebereich.

Das litter Argument von 10 ist zu hoch.

Schau dir den ersten Teil der Lösung an, um zu sehen, wie das funktioniert:

import argparse
from typing import NamedTuple


class Args(NamedTuple):
    """ Command-line arguments """
    generations: int 
    litter: int 


def get_args() -> Args:
    """ Get command-line arguments """

    parser = argparse.ArgumentParser(
        description='Calculate Fibonacci',
        formatter_class=argparse.ArgumentDefaultsHelpFormatter)

    parser.add_argument('gen', 
                        metavar='generations',
                        type=int, 
                        help='Number of generations')

    parser.add_argument('litter', 
                        metavar='litter',
                        type=int,
                        help='Size of litter per generation')

    args = parser.parse_args() 

    if not 1 <= args.gen <= 40: 
        parser.error(f'generations "{args.gen}" must be between 1 and 40') 

    if not 1 <= args.litter <= 5: 
        parser.error(f'litter "{args.litter}" must be between 1 and 5') 

    return Args(generations=args.gen, litter=args.litter) 

Das Feld generations muss ein int sein.

Das Feld litter muss ebenfalls ein int sein.

Der Positionsparameter gen wird zuerst definiert und erhält daher den ersten Positionswert.

Die type=int gibt die erforderliche Klasse des Wertes an. Beachte, dass int die Klasse selbst angibt, nicht den Namen der Klasse.

Der Positionsparameter litter ist als zweiter definiert und erhält daher den zweiten Positionswert.

Versucht, die Argumente zu parsen. Jeder Fehlversuch führt zu Fehlermeldungen und dem Beenden des Programms mit einem Wert ungleich Null.

Der Wert args.gen ist jetzt ein echter int Wert, so dass du numerische Vergleiche mit ihm durchführen kannst. Prüfe, ob der Wert im zulässigen Bereich liegt.

Verwende die Funktion parser.error(), um einen Fehler zu erzeugen und das Programm zu beenden.

Überprüfe auch den Wert des Arguments args.litter.

Erzeuge eine Fehlermeldung, die Informationen enthält, die der/die Nutzer/in benötigt, um das Problem zu beheben.

Wenn das Programm es bis zu diesem Punkt schafft, dann sind die Argumente gültige ganzzahlige Werte im akzeptierten Bereich, also gib die Args zurück.

Ich könnte in der Funktion main() überprüfen, ob die Werte von generations und litter in den richtigen Bereichen liegen, aber ich ziehe es vor, so viele Argumente wie möglich in der Funktion get_args() zu überprüfen, damit ich mit der Funktion parser.error() nützliche Meldungen erzeugen und das Programm mit einem Wert ungleich Null beenden kann.

Entfernen Sie das Programm fib.py und beginnen Sie neu mit new.py oder deiner bevorzugten Methode zum Erstellen eines Programms:

$ new.py -fp 'Calculate Fibonacci' fib.py
Done, see new script "fib.py".

Du kannst die Definition von get_args() durch den vorhergehenden Code ersetzen und dann deine Funktion main() wie folgt ändern:

def main() -> None:
    args = get_args()
    print(f'generations = {args.generations}')
    print(f'litter = {args.litter}')

Führe dein Programm mit ungültigen Eingaben aus und überprüfe, ob du die oben gezeigten Fehlermeldungen siehst. Versuche dein Programm mit akzeptablen Werten und überprüfe, ob du diese Art von Ausgabe siehst:

$ ./fib.py 1 2
generations = 1
litter = 2

Führe pytest Du solltest die ersten vier Tests bestehen und den fünften fehlschlagen lassen:

$ pytest -xv
========================== test session starts ==========================
...
tests/fib_test.py::test_exists PASSED                             [ 14%]
tests/fib_test.py::test_usage PASSED                              [ 28%]
tests/fib_test.py::test_bad_generations PASSED                    [ 42%]
tests/fib_test.py::test_bad_litter PASSED                         [ 57%]
tests/fib_test.py::test_1 FAILED                                  [ 71%] 

=============================== FAILURES ================================
________________________________ test_1 _________________________________

    def test_1():
        """runs on good input"""

        rv, out = getstatusoutput(f'{RUN} 5 3') 
        assert rv == 0
>       assert out == '19' 
E       AssertionError: assert 'generations = 5\nlitter = 3' == '19' 
E         - 19    
E         + generations = 5 
E         + litter = 3

tests/fib_test.py:60: AssertionError
======================== short test summary info ========================
FAILED tests/fib_test.py::test_1 - AssertionError: assert 'generations...
!!!!!!!!!!!!!!!!!!!!!!! stopping after 1 failures !!!!!!!!!!!!!!!!!!!!!!!
====================== 1 failed, 4 passed in 0.38s ======================

Der erste fehlschlagende Test. Der Test bricht hier wegen des -x Flags ab.

Das Programm wird mit 5 für die Anzahl der Generationen und 3 für die Wurfgröße ausgeführt.

Die Ausgabe sollte 19 sein.

Das zeigt, dass die beiden verglichenen Zeichenfolgen nicht gleich sind.

Der erwartete Wert war 19.

Das ist die Ausgabe, die wir erhalten haben.

Die Ausgabe von pytest gibt sich große Mühe, genau zu zeigen, was schief gelaufen ist. Sie zeigt, wie das Programm ausgeführt wurde und was erwartet wurde, im Gegensatz zu dem, was produziert wurde. Das Programm soll 19 ausgeben, was die fünfte Zahl der Fibonacci-Folge ist, wenn man eine Wurfgröße von 3 verwendet. Wenn du das Programm selbst fertigstellen möchtest, kannst du gleich loslegen. Du solltest mit pytest um zu überprüfen, ob du alle Tests bestehst. Führe außerdem make test aus, um dein Programm mit pylint, flake8 und mypy zu überprüfen. Wenn du eine Anleitung brauchst, gehe ich auf den ersten beschriebenen Ansatz ein.

Ein zwingender Ansatz

In Abbildung 4-2 ist das Wachstum der Fibonacci-Folge dargestellt. Die kleineren Kaninchen stehen für nicht brütende Paare, die zu größeren, brütenden Paaren heranreifen müssen.

Abbildung 4-2. Eine Visualisierung des Wachstums der Fibonacci-Folge als Paarung von Kaninchen mit einer Wurfgröße von 1

Du siehst, dass ich die beiden vorherigen Zahlen kennen muss, um eine beliebige Zahl nach den ersten beiden zu erzeugen. Mit dieser Formel kann ich den Wert einer beliebigen Position n der Fibonacci-Folge(F) beschreiben:

$$F_n=F_{n-1}+F_{n-2}$$

Welche Datenstruktur in Python würde es mir ermöglichen, eine Reihe von Zahlen in der richtigen Reihenfolge zu halten und auf sie durch ihre Position zu verweisen?Eine Liste. Ich beginne mit_F1 = 0 und _F2 = 1:

>>> fib = [0, 1]

Der Wert _F3 ist _F2 +_F1 = 1 + 0 = 1. Wenn ich die nächste Zahl generiere, beziehe ich mich immer auf die letzten beiden Elemente der Folge. Am einfachsten ist es, eine negative Indizierung zu verwenden, um eine Position vom Ende der Liste anzugeben.Der letzte Wert in einer Liste steht immer an der Position -1:

>>> fib[-1]
1

Der vorletzte Wert steht unter -2:

>>> fib[-2]
0

Ich muss diesen Wert mit der Wurfgröße multiplizieren, um die Anzahl der Nachkommen zu berechnen, die diese Generation hervorgebracht hat. Für den Anfang gehe ich von einer Wurfgröße von 1 aus:

>>> litter = 1
>>> fib[-2] * litter
0

Ich möchte diese beiden Zahlen zusammenzählen und das Ergebnis an die Liste anhängen:

>>> fib.append((fib[-2] * litter) + fib[-1])
>>> fib
[0, 1, 1]

Wenn ich das noch einmal mache, kann ich sehen, dass sich die richtige Reihenfolge abzeichnet:

>>> fib.append((fib[-2] * litter) + fib[-1])
>>> fib
[0, 1, 1, 2]

Ich muss diesen Vorgang generations Mal wiederholen. (Technisch gesehen sind es generations-1 Mal, da Python eine 0-basierte Indizierung verwendet.) Ich kann die Funktion range() von Python verwenden, um eine Liste von Zahlen von 0 bis zum Endwert zu erzeugen. Ich rufe diese Funktion nur als Nebeneffekt auf, um eine bestimmte Anzahl von Iterationen durchzuführen, und benötige daher die von der Funktion range() erzeugten Werte nicht. Es ist üblich, die Variable Unterstrich (_) zu verwenden, um anzuzeigen, dass man einen Wert ignorieren will:

>>> fib = [0, 1]
>>> litter = 1
>>> generations = 5
>>> for _ in range(generations - 1):
...     fib.append((fib[-2] * litter) + fib[-1])
...
>>> fib
[0, 1, 1, 2, 3, 5]

Das sollte ausreichen, um eine Lösung zu erstellen, die die Tests besteht. Im nächsten Abschnitt werde ich zwei weitere Lösungen vorstellen, die einige sehr interessante Teile von Python beleuchten.

Lösungen

Alle folgenden Lösungen haben dieselbe get_args() wie die zuvor gezeigten.

Lösung 1: Eine imperative Lösung mit einer Liste als Stapel

So habe ich meine imperative Lösung geschrieben.Ich verwende eine Liste als eine Art Stapel, um vergangene Werte zu speichern. Ich brauche nicht alle Werte, sondern nur die letzten beiden, aber es ist ziemlich einfach, die Liste zu vergrößern und auf die letzten beiden Werte zu verweisen:

def main() -> None:
    args = get_args()

    fib = [0, 1] 
    for _ in range(args.generations - 1): 
        fib.append((fib[-2] * args.litter) + fib[-1]) 

    print(fib[-1]) 

Beginne mit 0 und 1.

Verwende die Funktion range(), um die richtige Anzahl von Schleifen zu erstellen.

Füge den nächsten Wert an die Sequenz an.

Druckt die letzte Nummer der Folge.

Ich habe den Variablennamen _ in der for Schleife verwendet, um anzuzeigen, dass ich die Variable nicht verwenden will. Der Unterstrich ist ein gültiger Bezeichner in Python, und es ist auch üblich, damit einen Wegwerfwert zu kennzeichnen. Linting-Tools könnten zum Beispiel sehen, dass ich einer Variablen einen Wert zugewiesen, sie aber nie benutzt habe, was normalerweise auf einen möglichen Fehler hinweisen würde. Die Unterstrichvariable zeigt, dass ich nicht vorhabe, den Wert zu verwenden. In diesem Fall verwende ich die Funktion nur als Nebeneffekt, um die benötigte Anzahl von Schleifen zu erzeugen. range()

Dies gilt als imperative Lösung, weil der Code jede Anweisung des Algorithmus direkt kodiert.Wenn du die rekursive Lösung liest, wirst du sehen, dass der Algorithmus auf eine deklarativere Weise geschrieben werden kann, was auch unbeabsichtigte Konsequenzen hat, die ich behandeln muss.

Eine kleine Abwandlung davon wäre, diesen Code innerhalb einer Funktion zu platzieren, die ich fib() nenne. Beachte, dass es in Python möglich ist, eine Funktion innerhalb einer anderen Funktion zu deklarieren, wie hier fib() innerhalb von main(). Ich tue das, damit ich den Parameter args.litter referenzieren kann und eine Schließung erzeuge, weil die Funktion den Laufzeitwert der Wurfgröße erfasst:

def main() -> None:
    args = get_args()

    def fib(n: int) -> int: 
        nums = [0, 1] 
        for _ in range(n - 1): 
            nums.append((nums[-2] * args.litter) + nums[-1]) 
        return nums[-1] 

    print(fib(args.generations)) 

Erstelle eine Funktion namens fib(), die einen ganzzahligen Parameter n akzeptiert und eine ganze Zahl zurückgibt.

Dies ist derselbe Code wie zuvor. Beachte, dass diese Liste nums heißt, damit sie nicht mit dem Funktionsnamen kollidiert.

Verwende die Funktion range(), um die Generationen zu iterieren. Verwende _, um die Werte zu ignorieren.

Die Funktion verweist auf den Parameter args.litter und erstellt so eine Schließung.

Verwende return, um den endgültigen Wert an den Anrufer zurückzuschicken.

Rufe die Funktion fib() mit dem Parameter args.generations auf.

Der Geltungsbereich der Funktion fib() im vorangegangenen Beispiel ist auf die Funktion main() beschränkt.Der Geltungsbereich bezieht sich auf den Teil des Programms, in dem ein bestimmter Funktionsname oder eine Variable sichtbar oder legal ist.

Ich muss keine Schließung verwenden. So kann ich die gleiche Idee mit einer Standardfunktion ausdrücken:

def main() -> None:
    args = get_args()

    print(fib(args.generations, args.litter)) 

def fib(n: int, litter: int) -> int: 
    nums = [0, 1]
    for _ in range(n - 1):
        nums.append((nums[-2] * litter) + nums[-1])

    return nums[-1]

Die Funktion fib() muss mit zwei Argumenten aufgerufen werden.

Die Funktion benötigt sowohl die Anzahl der Generationen als auch die Wurfgröße. Der Funktionsrumpf ist im Wesentlichen derselbe.

Im vorangegangenen Code siehst du, dass ich zwei Argumente an fib() übergeben muss, während die Closure nur ein Argument benötigte, weil litter erfasst wurde. Werte zu binden und die Anzahl der Parameter zu reduzieren, ist ein triftiger Grund für die Erstellung einer Closure. Ein weiterer Grund, eine Closure zu schreiben, ist, den Geltungsbereich einer Funktion zu begrenzen. Die Closure-Definition von fib() ist nur innerhalb der Funktion main() gültig, aber die vorhergehende Version ist im ganzen Programm sichtbar. Eine Funktion innerhalb einer anderen Funktion zu verstecken, macht es schwieriger, sie zu testen. In diesem Fall ist die Funktion fib() fast das gesamte Programm, also wurden die Tests bereits in tests/fib_test.py geschrieben.

Lösung 2: Erstellen einer Generatorfunktion

In der vorherigen Lösung habe ich die Fibonacci-Folge bis zum gewünschten Wert erzeugt und dann aufgehört; die Folge ist jedoch unendlich. Könnte ich eine Funktion erstellen, die alle Zahlen der Folge erzeugt? Technisch gesehen ja, aber sie würde nie enden, da sie unendlich ist und so weiter.

In Python gibt es eine Möglichkeit, eine Funktion anzuhalten, die eine möglicherweise unendliche Sequenz erzeugt. Ich kann yield verwenden, um einen Wert aus einer Funktion zurückzugeben und die Funktion vorübergehend zu verlassen, um später mit demselben Zustand fortzufahren, wenn der nächste Wert angefordert wird.Diese Art von Funktion wird Generator genannt, und hier ist, wie ich sie verwenden kann, um die Sequenz zu erzeugen:

def fib(k: int) -> Generator[int, None, None]: 
    x, y = 0, 1 
    yield x 

    while True: 
        yield y 
        x, y = y * k, x + y 

Die Typsignatur zeigt an, dass die Funktion den Parameter k (Wurfgröße) annimmt, der ein int sein muss. Sie gibt eine spezielle Funktion vom Typ Generator zurück, die int Werte liefert und keine Sende- oder Rückgabetypen hat.

Ich brauche nur die letzten beiden Generationen zu verfolgen, die ich mit 0 und 1 initialisiere.

Gib die 0 ab.

Erstelle eine Endlosschleife.

Erhalte die letzte Generation.

Setze x (zwei Generationen zurück) auf die aktuelle Generation mal die Wurfgröße. Setze y (eine Generation zurück) auf die Summe der beiden aktuellen Generationen.

Ein Generator verhält sich wie ein Iterator, der die vom Code angeforderten Werte produziert, bis er erschöpft ist.Da dieser Generator nur Ausbeutewerte erzeugt, sind die Sende- und Rückgabetypen None. Ansonsten macht dieser Code genau das, was die erste Version des Programms gemacht hat, nur innerhalb einer schicken Generatorfunktion. In Abbildung 4-3 siehst du, wie die Funktion für zwei verschiedene Wurfgrößen funktioniert.

Abbildung 4-3. Eine Darstellung, wie sich der Zustand des fib() Generators im Laufe der Zeit verändert (n=5) für zwei Wurfgrößen (k=1 und k=3)

Die Typsignatur für Generator sieht ein bisschen kompliziert aus, da sie Typen für yield, send und return definiert. Ich muss hier nicht weiter darauf eingehen, aber ich empfehle dir, die Dokumentation des Moduls typing zu lesen.

So verwendest du es:

def main() -> None:
    args = get_args()
    gen = fib(args.litter) 
    seq = [next(gen) for _ in range(args.generations + 1)] 
    print(seq[-1]) 

Die Funktion fib() nimmt die Wurfgröße als Argument und gibt einen Generator zurück.

Verwende die Funktion next(), um den nächsten Wert von einem Generator abzurufen. Verwende ein Listenverständnis, um dies so oft zu tun, bis die Sequenz den gewünschten Wert erreicht hat.

Druckt die letzte Nummer in der Folge.

Die Funktion range() ist anders, weil in der ersten Version bereits 0 und 1 vorhanden waren. Hier muss ich den Generator zwei weitere Male aufrufen, um diese Werte zu erzeugen.

Obwohl ich das Listenverständnis bevorzuge, brauche ich nicht die ganze Liste, sondern nur den Endwert, also hätte ich es auch so schreiben können:

def main() -> None:
    args = get_args()
    gen = fib(args.litter)
    answer = 0 
    for _ in range(args.generations + 1): 
        answer = next(gen) 
    print(answer) 

Initialisiere die Antwort auf 0.

Erstelle die richtige Anzahl von Schleifen.

Erhalte den Wert für die aktuelle Generation.

Drucke die Antwort aus.

Da es häufig vorkommt, dass man eine Funktion wiederholt aufruft, um eine Liste zu erzeugen, gibt es eine Funktion, die das für uns erledigt. Die Funktion itertools.islice() "Make an iterator that returns selected elements from the iterable:

def main() -> None:
    args = get_args()
    seq = list(islice(fib(args.litter), args.generations + 1)) 
    print(seq[-1]) 

Das erste Argument von islice() ist die Funktion, die aufgerufen werden soll, und das zweite Argument ist die Anzahl der Aufrufe der Funktion. Die Funktion ist faul, also verwende ich list(), um die Werte zu erzwingen.

Drucke den letzten Wert.

Da ich die Variable seq nur ein einziges Mal verwende, könnte ich auf diese Zuweisung verzichten. Wenn ein Benchmarking ergeben würde, dass die folgende Version am besten funktioniert, wäre ich vielleicht bereit, einen Einzeiler zu schreiben:

def main() -> None:
    args = get_args()
    print(list(islice(fib(args.litter), args.generations + 1))[-1])

Cleverer Code macht Spaß, kann aber unlesbar werden.¹ Du wurdest gewarnt.

Generatoren sind cool, aber komplexer als das Erzeugen einer Liste. Sie sind der richtige Weg, um eine sehr große oder potenziell unendliche Folge von Werten zu erzeugen, weil sie faul sind und den nächsten Wert nur dann berechnen, wenn dein Code es erfordert.

Lösung 3: Rekursion und Memoisierung verwenden

Es gibt noch viele weitere lustige Möglichkeiten, einen Algorithmus zu schreiben, der eine unendliche Reihe von Zahlen erzeugt, aber ich zeige dir nur eine weitere, bei der eine Funktion sich selbst aufruft: die Rekursion:

def main() -> None:
    args = get_args()

    def fib(n: int) -> int: 
        return 1 if n in (1, 2) \ 
            else fib(n - 2) * args.litter + fib(n - 1) 

    print(fib(args.generations)) 

Definiere eine Funktion namens fib(), die die Nummer der gewünschten Generation als int annimmt und eine int zurückgibt.

Wenn die Generation 1 oder 2 ist, gib 1 zurück. Dies ist der wichtige Basisfall, der keinen rekursiven Aufruf vornimmt.

In allen anderen Fällen rufst du die Funktion fib() zweimal auf, einmal für zwei Generationen zurück und einmal für die vorherige Generation. Beziehe die Wurfgröße wie zuvor mit ein.

Druckt die Ergebnisse der Funktion fib() für die angegebenen Generationen.

Hier ist ein weiteres Beispiel, in dem ich eine Funktion fib() als Schließung innerhalb der Funktion main() definiere, um den Wert args.litter innerhalb der Funktion fib() zu verwenden. Damit schließe ich args.litter und binde den Wert an die Funktion. Hätte ich die Funktion außerhalb der Funktion main() definiert, hätte ich das Argument args.litter bei den rekursiven Aufrufen übergeben müssen.

Das ist eine wirklich elegante Lösung, die in so ziemlich jedem Einführungskurs in Informatik gelehrt wird. Es macht Spaß, sie zu studieren, aber es stellt sich heraus, dass sie verdammt langsam ist, weil die Funktion so oft aufgerufen wird. Das heißt, fib(5) muss fib(4) und fib(3) aufrufen, um diese Werte zu addieren. fib(4) muss wiederum fib(3) und fib(2) aufrufen und so weiter.Abbildung 4-4 zeigt, dass fib(5) 14 Funktionsaufrufe benötigt, um 5 verschiedene Werte zu erzeugen. fib(2) wird zum Beispiel dreimal berechnet, aber wir müssen es nur einmal berechnen.

Abbildung 4-4. Der Aufrufstapel für fib(5) führt zu vielen rekursiven Aufrufen der Funktion, wobei deren Anzahl mit steigendem Eingabewert ungefähr exponentiell zunimmt

Um das Problem zu verdeutlichen, werde ich stichprobenartig untersuchen, wie lange dieses Programm braucht, um bis zum Maximum n von 40 fertig zu werden. Auch hier verwende ich eine for Schleife in bash, um dir zu zeigen, wie ich ein solches Programm üblicherweise auf der Kommandozeile benchmarken würde:

$ for n in 10 20 30 40;
> do echo "==> $n <==" && time ./solution3_recursion.py $n 1
> done
==> 10 <==
55

real	0m0.045s
user	0m0.032s
sys	0m0.011s
==> 20 <==
6765

real	0m0.041s
user	0m0.031s
sys	0m0.009s
==> 30 <==
832040

real	0m0.292s
user	0m0.281s
sys	0m0.009s
==> 40 <==
102334155

real	0m31.629s
user	0m31.505s
sys	0m0.043s

Der Sprung von 0,29s für n=30 auf 31s für n=40 ist gewaltig. Stell dir vor, du kommst auf 50 und mehr. Ich muss entweder einen Weg finden, dies zu beschleunigen, oder alle Hoffnung auf Rekursion aufgeben. Die Lösung ist, die zuvor berechneten Ergebnisse zwischenzuspeichern. Das nennt man Memoisierung, und es gibt viele Möglichkeiten, dies zu implementieren. Die folgende ist eine Methode. Beachte, dass du typing.Callable importieren musst:

def memoize(f: Callable) -> Callable: 
    """ Memoize a function """

    cache = {} 

    def memo(x): 
        if x not in cache: 
            cache[x] = f(x) 
        return cache[x] 

    return memo 

Definiere eine Funktion, die eine Funktion annimmt (etwas, das aufrufbar ist) und eine Funktion zurückgibt.

Verwende ein Wörterbuch, um zwischengespeicherte Werte zu speichern.

Definiere memo() als eine Schließung um den Cache. Die Funktion erhält beim Aufruf einige Parameter x.

Sieh nach, ob der Wert des Arguments im Cache ist.

Wenn nicht, rufe die Funktion mit dem Argument auf und setze den Cache für diesen Argumentwert auf das Ergebnis.

Gibt den zwischengespeicherten Wert für das Argument zurück.

Gib die neue Funktion zurück.

Beachte, dass die Funktion memoize() eine neue Funktion zurückgibt. In Python gelten Funktionen als Objekte erster Klasse, d.h. sie können wie andere Arten von Variablen verwendet werden - du kannst sie als Argumente übergeben und ihre Definitionen überschreiben. Die Funktion memoize() ist ein Beispiel für eine Funktion höherer Ordnung (HOF), da sie andere Funktionen als Argumente annimmt. Ich werde im Laufe des Buches weitere HOFs wie filter() und map() verwenden.

Um die Funktion memoize() zu verwenden, definiere ich fib() und definiere sie dann mit der memoisierten Version neu. Wenn du dies ausführst, wirst du ein fast sofortiges Ergebnis sehen, egal wie hoch n ist:

def main() -> None:
    args = get_args()

    def fib(n: int) -> int:
        return 1 if n in (1, 2) else fib(n - 2) * args.litter + fib(n - 1)

    fib = memoize(fib) 

    print(fib(args.generations))

Überschreibe die bestehende fib() Definition mit der memoisierten Funktion.

Eine bevorzugte Methode, um dies zu erreichen, ist die Verwendung eines Dekorators, also einer Funktion, die eine andere Funktion verändert:

def main() -> None:
    args = get_args()

    @memoize 
    def fib(n: int) -> int:
        return 1 if n in (1, 2) else fib(n - 2) * args.litter + fib(n - 1)

    print(fib(args.generations))

Schmücke die Funktion fib() mit der Funktion memoize() aus.

So viel Spaß es auch macht, Memoisierungsfunktionen zu schreiben, es stellt sich wieder einmal heraus, dass dies ein so häufiges Bedürfnis ist, dass andere es bereits für uns gelöst haben. Ich kann die Funktion memoize() entfernen und stattdessen die Funktion functools.lru_cache (least-recently-used cache) importieren:

from functools import lru_cache

Schmücke die Funktion fib() mit der Funktion lru_cache() aus, um eine Memoisierung mit minimaler Ablenkung zu erhalten:

def main() -> None:
    args = get_args()

    @lru_cache() 
    def fib(n: int) -> int:
        return 1 if n in (1, 2) else fib(n - 2) * args.litter + fib(n - 1)

    print(fib(args.generations))

Memoize die Funktion fib() über die Dekoration mit der Funktion lru_cache(). Beachte, dass Python 3.6 die Klammern benötigt, aber 3.8 und spätere Versionen nicht.

Benchmarking der Lösungen

Welche ist die schnellste Lösung? Ich habe dir gezeigt, wie du eine for Schleife in bash mit dem time Befehl verwenden kannst, um die Laufzeiten der Befehle zu vergleichen:

$ for py in ./solution1_list.py ./solution2_generator_islice.py \
./solution3_recursion_lru_cache.py; do echo $py && time $py 40 5; done
./solution1_list.py
148277527396903091

real	0m0.070s
user	0m0.043s
sys	0m0.016s
./solution2_generator_islice.py
148277527396903091

real	0m0.049s
user	0m0.033s
sys	0m0.013s
./solution3_recursion_lru_cache.py
148277527396903091

real	0m0.041s
user	0m0.030s
sys	0m0.010s

Es sieht so aus, als ob die rekursive Lösung mit LRU-Caching am schnellsten ist, aber auch hier habe ich nur sehr wenige Daten - nur einen Durchlauf pro Programm. Außerdem muss ich diese Daten mit dem Auge betrachten und herausfinden, welche die schnellste ist.

Es gibt einen besseren Weg. Ich habe ein Tool namens hyperfine um jeden Befehl mehrmals auszuführen und die Ergebnisse zu vergleichen:

$ hyperfine -L prg ./solution1_list.py,./solution2_generator_islice.py,\
./solution3_recursion_lru_cache.py '{prg} 40 5' --prepare 'rm -rf __pycache__'
Benchmark #1: ./solution1_list.py 40 5
  Time (mean ± σ):      38.1 ms ±   1.1 ms    [User: 28.3 ms, System: 8.2 ms]
  Range (min … max):    36.6 ms …  42.8 ms    60 runs

Benchmark #2: ./solution2_generator_islice.py 40 5
  Time (mean ± σ):      38.0 ms ±   0.6 ms    [User: 28.2 ms, System: 8.1 ms]
  Range (min … max):    36.7 ms …  39.2 ms    66 runs

Benchmark #3: ./solution3_recursion_lru_cache.py 40 5
  Time (mean ± σ):      37.9 ms ±   0.6 ms    [User: 28.1 ms, System: 8.1 ms]
  Range (min … max):    36.6 ms …  39.4 ms    65 runs

Summary
  './solution3_recursion_lru_cache.py 40 5' ran
    1.00 ± 0.02 times faster than './solution2_generator_islice.py 40 5'
    1.01 ± 0.03 times faster than './solution1_list.py 40 5'

Anscheinend hat hyperfine jeden Befehl 60-66 Mal ausgeführt, die Ergebnisse gemittelt und festgestellt, dass das Programm solution3_recursion_lru_cache.py vielleicht etwas schneller ist. Ein weiteres Benchmarking-Tool, das du vielleicht nützlich findest, ist benchDu kannst aber auch im Internet nach anderen Benchmarking-Tools suchen, die deinem Geschmack eher entsprechen.Welches Tool du auch immer verwendest, Benchmarking und Testen sind wichtig, um Annahmen über deinen Code zu überprüfen.

Ich habe die Option --prepare verwendet, um hyperfine anzuweisen, das pycache-Verzeichnis zu entfernen, bevor die Befehle ausgeführt werden. Das ist ein Verzeichnis, das Python erstellt, um den Bytecode des Programms zwischenzuspeichern. Wenn sich der Quellcode eines Programms seit der letzten Ausführung nicht geändert hat, kann Python die Kompilierung überspringen und die Bytecode-Version verwenden, die im pycache-Verzeichnis existiert. Ich musste dies entfernen, da hyperfine bei der Ausführung der Befehle statistische Ausreißer feststellte, die wahrscheinlich auf Caching-Effekte zurückzuführen waren.

Das Gute, das Schlechte und das Hässliche testen

Für jede Herausforderung hoffe ich, dass du einen Teil deiner Zeit damit verbringst, die Tests durchzulesen.Zu lernen, wie man Tests entwirft und schreibt, ist genauso wichtig wie alles andere, was ich dir zeige. Wie ich bereits erwähnt habe, überprüfen meine ersten Tests, ob das erwartete Programm existiert und auf Anfrage Verwendungsnachweise produziert. Danach gebe ich in der Regel ungültige Eingaben ein, um sicherzustellen, dass das Programm fehlschlägt. Ich möchte die Tests für falsche n und k Parameter hervorheben. Sie sind im Wesentlichen gleich, daher zeige ich nur den ersten, da er demonstriert, wie man zufällig einen ungültigen Integer-Wert auswählt - einen, der möglicherweise negativ oder zu hoch ist:

def test_bad_n():
    """ Dies when n is bad """

    n = random.choice(list(range(-10, 0)) + list(range(41, 50))) 
    k = random.randint(1, 5) 
    rv, out = getstatusoutput(f'{RUN} {n} {k}') 
    assert rv != 0 
    assert out.lower().startswith('usage:') 
    assert re.search(f'n "{n}" must be between 1 and 40', out) 

Verbinde die beiden Listen mit den ungültigen Zahlenbereichen und wähle zufällig einen Wert aus.

Wähle eine zufällige ganze Zahl im Bereich von 1 bis 5 (beide Grenzen inklusive).

Führe das Programm mit den Argumenten aus und zeichne die Ausgabe auf.

Vergewissere dich, dass das Programm einen Fehler gemeldet hat (Exit-Wert ungleich Null).

Prüfe, ob die Ausgabe mit einer Verwendungsanweisung beginnt.

Achte auf eine Fehlermeldung, die das Problem mit dem Argument n beschreibt.

Ich verwende beim Testen oft gerne zufällig ausgewählte ungültige Werte. Das kommt zum Teil daher, dass ich Tests für Schüler/innen schreibe, damit sie keine Programme schreiben, die bei einer einzigen falschen Eingabe fehlschlagen, aber ich finde auch, dass es mir hilft, nicht versehentlich für einen bestimmten Eingabewert zu programmieren. Ich habe das Modul random noch nicht behandelt, aber es bietet dir eine Möglichkeit, pseudozufällige Entscheidungen zu treffen. Zuerst musst du das Modul importieren:

>>> import random

Du kannst zum Beispiel random.randint() verwenden, um eine einzelne Ganzzahl aus einem bestimmten Bereich auszuwählen:

>>> random.randint(1, 5)
2
>>> random.randint(1, 5)
5

Oder verwende die Funktion random.choice(), um einen einzelnen Wert zufällig aus einer Folge auszuwählen. Hier wollte ich einen unzusammenhängenden Bereich negativer Zahlen konstruieren, der von einem Bereich positiver Zahlen getrennt ist:

>>> random.choice(list(range(-10, 0)) + list(range(41, 50)))
46
>>> random.choice(list(range(-10, 0)) + list(range(41, 50)))
-1

Die folgenden Tests liefern alle guten Input für das Programm. Zum Beispiel:

def test_2():
    """ Runs on good input """

    rv, out = getstatusoutput(f'{RUN} 30 4') 
    assert rv == 0 
    assert out == '436390025825' 

Das sind die Werte, die ich beim Versuch, die Rosalind-Herausforderung zu lösen, erhalten habe.

Das Programm sollte an dieser Eingabe nicht fehlschlagen.

Das ist die richtige Antwort von Rosalind.

Testen ist, wie die Dokumentation, ein Liebesbrief an dein zukünftiges Ich. So mühsam Testen auch sein mag, du wirst es zu schätzen wissen, wenn Tests fehlschlagen, wenn du versuchst, eine Funktion hinzuzufügen und dabei versehentlich etwas kaputt machst, das vorher funktioniert hat. Wenn du fleißig Tests schreibst und durchführst, kannst du verhindern, dass du kaputte Programme einsetzt.

Ausführen der Testsuite für alle Lösungen

Du hast gesehen, dass ich in jedem Kapitel mehrere Lösungen schreibe, um verschiedene Wege zu finden, die Probleme zu lösen. Ich verlasse mich voll und ganz auf meine Tests, um sicherzustellen, dass meine Programme korrekt sind. Vielleicht bist du neugierig, wie ich den Prozess des Testens jeder einzelnen Lösung automatisiert habe. Sieh dir das Makefile an und suche das Ziel all:

$ cat Makefile
.PHONY: test

test:
	python3 -m pytest -xv --flake8 --pylint --mypy fib.py tests/fib_test.py

all:
    ../bin/all_test.py fib.py

Das Programm all_test.py überschreibt das Programm fib.py mit jeder Lösung, bevor es die Testsuite ausführt. Dadurch könnte deine Lösung überschrieben werden. Vergewissere dich, dass du deine Version in Git einstellst oder zumindest eine Kopie machst, bevor du make all ausführst, sonst könntest du deine Arbeit verlieren.

Das Folgende ist das Programm all_test.py, das vom Ziel all ausgeführt wird. Ich unterteile es in zwei Teile, beginnend mit dem ersten Teil bis get_args(). Das meiste davon sollte inzwischen bekannt sein:

#!/usr/bin/env python3
""" Run the test suite on all solution*.py """

import argparse
import os
import re
import shutil
import sys
from subprocess import getstatusoutput
from functools import partial
from typing import NamedTuple


class Args(NamedTuple):
    """ Command-line arguments """
    program: str 
    quiet: bool 


# --------------------------------------------------
def get_args() -> Args:
    """ Get command-line arguments """

    parser = argparse.ArgumentParser(
        description='Run the test suite on all solution*.py',
        formatter_class=argparse.ArgumentDefaultsHelpFormatter)

    parser.add_argument('program', metavar='prg', help='Program to test') 

    parser.add_argument('-q', '--quiet', action='store_true', help='Be quiet') 

    args = parser.parse_args()

    return Args(args.program, args.quiet)

Der Name des zu prüfenden Programms, der in diesem Fall fib.py lautet.

Ein boolescher Wert von True oder False, um mehr oder weniger Output zu erzeugen.

Der Standardtyp ist str.

Die action='store_true' macht dies zu einem booleschen Flag. Wenn das Flag vorhanden ist, ist der Wert True, andernfalls ist er False.

Die Funktion main() ist der Ort, an dem die Prüfung stattfindet:

def main() -> None:
    args = get_args()
    cwd = os.getcwd() 
    solutions = list( 
        filter(partial(re.match, r'solution.*\.py'), os.listdir(cwd))) 

    for solution in sorted(solutions): 
        print(f'==> {solution} <==')
        shutil.copyfile(solution, os.path.join(cwd, args.program)) 
        subprocess.run(['chmod', '+x', args.program], check=True) 
        rv, out = getstatusoutput('make test') 
        if rv != 0: 
            sys.exit(out) 

        if not args.quiet: 
            print(out)

    print('Done.') 

Ermittelt das aktuelle Arbeitsverzeichnis. Das ist das Verzeichnis 04_fib, wenn du dich beim Ausführen des Befehls in diesem Verzeichnis befindest.

Finde alle solution*.py Dateien im aktuellen Verzeichnis.

Sowohl filter() als auch partial() sind HOFs; ich werde sie als nächstes erklären.

Die Dateinamen werden in zufälliger Reihenfolge sein, also durchlaufe die sortierten Dateien.

Kopiere die Datei solution*.py auf den Dateinamen der Prüfung.

Mache das Programm ausführbar.

Führe den Befehl make test aus und zeichne den Rückgabewert und die Ausgabe auf.

Schau nach, ob der Rückgabewert nicht 0 ist.

Beende das Programm, indem du die Testausgabe ausdruckst und einen Wert ungleich Null zurückgibst.

Wenn das Programm nicht still sein soll, drucke die Testausgabe aus.

Lass den Benutzer wissen, dass das Programm normal beendet wird.

Im vorangegangenen Code verwende ich sys.exit(), um das Programm sofort anzuhalten, eine Fehlermeldung auszugeben und einen Exit-Wert ungleich Null zurückzuliefern. In der Dokumentation findest du, dass du sys.exit() ohne Argumente, mit einem Integer-Wert oder einem Objekt wie einem String aufrufen kannst, was ich hier verwende:

exit(status=None, /)
    Exit the interpreter by raising SystemExit(status).

    If the status is omitted or None, it defaults to zero (i.e., success).
    If the status is an integer, it will be used as the system exit status.
    If it is another kind of object, it will be printed and the system
    exit status will be one (i.e., failure).

Das vorangegangene Programm verwendet auch die Funktionen filter() oder partial(), die ich noch nicht behandelt habe. Beides sind HOFs. Ich erkläre, wie und warum ich sie verwende. Zunächst gibt die Funktion os.listdir() den gesamten Inhalt eines Verzeichnisses zurück, einschließlich Dateien und Verzeichnisse:

>>> import os
>>> files = os.listdir()

Das ist eine ganze Menge, also importiere ich die Funktion pprint() aus dem Modul pprint, um das hübsch auszudrucken:

>>> from pprint import pprint
>>> pprint(files)
['solution3_recursion_memoize_decorator.py',
 'solution2_generator_for_loop.py',
 '.pytest_cache',
 'Makefile',
 'solution2_generator_islice.py',
 'tests',
 '__pycache__',
 'fib.py',
 'README.md',
 'solution3_recursion_memoize.py',
 'bench.html',
 'solution2_generator.py',
 '.mypy_cache',
 '.gitignore',
 'solution1_list.py',
 'solution3_recursion_lru_cache.py',
 'solution3_recursion.py']

Ich möchte nach Namen filtern, die mit solution beginnen und mit .py enden.In der Befehlszeile würde ich dieses Muster mit einem Dateiglob wie solution*.py, abgleichen, wobei * für null oder mehr beliebige Zeichen steht und . ein Punkt ist. Eine Version dieses Musters mit regulären Ausdrücken ist die etwas kompliziertere solution.*\.py, bei der . (Punkt) ein Regex-Metazeichen ist, das ein beliebiges Zeichen darstellt, und * (Stern oder Asterisk) für null oder mehr steht (siehe Abbildung 4-5). Um einen buchstäblichen Punkt anzugeben, muss ich ihn mit einem Backslash (\.) abschließen. Beachte, dass es ratsam ist, den r-String(raw string) zu verwenden, um dieses Muster einzuschließen.

Abbildung 4-5. Ein regulärer Ausdruck, um Dateien zu finden, die dem Dateiglob entsprechen solution*.py

Wenn der Treffer erfolgreich ist, wird ein re.Match Objekt zurückgegeben:

>>> import re
>>> re.match(r'solution.*\.py', 'solution1.py')
<re.Match object; span=(0, 12), match='solution1.py'>

Wenn ein Treffer fehlschlägt, wird der Wert None zurückgegeben. Ich muss hier type() verwenden, weil der Wert None in der REPL nicht angezeigt wird:

>>> type(re.match(r'solution.*\.py', 'fib.py'))
<class 'NoneType'>

Ich möchte diesen Abgleich auf alle Dateien anwenden, die von os.listdir() zurückgegeben werden. Ich kann mit filter() und dem Schlüsselwort lambda eine anonyme Funktion erstellen. Jeder Dateiname in files wird als name Argument in der Übereinstimmung verwendet. Die Funktion filter() gibt nur Elemente zurück, die einen wahrheitsgemäßen Wert von der gegebenen Funktion zurückgeben, so dass die Dateinamen, die None zurückgeben, wenn die Übereinstimmung fehlschlägt, ausgeschlossen werden:

>>> pprint(list(filter(lambda name: re.match(r'solution.*\.py', name), files)))
['solution3_recursion_memoize_decorator.py',
 'solution2_generator_for_loop.py',
 'solution2_generator_islice.py',
 'solution3_recursion_memoize.py',
 'solution2_generator.py',
 'solution1_list.py',
 'solution3_recursion_lru_cache.py',
 'solution3_recursion.py']

Du siehst, dass die Funktion re.match() zwei Argumente benötigt - ein Muster und eine Zeichenkette, die übereinstimmen soll. Mit der Funktion partial() kann ich die Funktion teilweise anwenden, und das Ergebnis ist eine neue Funktion.Die Funktion operator.add() erwartet zum Beispiel zwei Werte und gibt deren Summe zurück:

>>> import operator
>>> operator.add(1, 2)
3

Ich kann eine Funktion erstellen, die 1 zu einem beliebigen Wert addiert, etwa so:

>>> from functools import partial
>>> succ = partial(op.add, 1)

Die Funktion succ() benötigt ein Argument und gibt den Nachfolger zurück:

>>> succ(3)
4
>>> succ(succ(3))
5

Ebenso kann ich eine Funktion f() erstellen, die die Funktion re.match() mit ihrem ersten Argument, einem regulären Ausdrucksmuster, teilweise anwendet:

>>> f = partial(re.match, r'solution.*\.py')

Die Funktion f() wartet auf eine Zeichenkette, um die Übereinstimmung anzuwenden:

>>> type(f('solution1.py'))
<class 're.Match'>
>>> type(f('fib.py'))
<class 'NoneType'>

Wenn du sie ohne ein Argument aufrufst, bekommst du eine Ausnahme:

>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: match() missing 1 required positional argument: 'string'

Ich kann die lambda durch die teilweise angewandte Funktion als erstes Argument für filter() ersetzen:

>>> pprint(list(filter(f, files)))
['solution3_recursion_memoize_decorator.py',
 'solution2_generator_for_loop.py',
 'solution2_generator_islice.py',
 'solution3_recursion_memoize.py',
 'solution2_generator.py',
 'solution1_list.py',
 'solution3_recursion_lru_cache.py',
 'solution3_recursion.py']

Mein Programmierstil orientiert sich stark an den Ideen der funktionalen Programmierung. Ich finde, dieser Stil ist wie das Spielen mit LEGO-Steinen - kleine, gut definierte und getestete Funktionen können zu größeren Programmen zusammengesetzt werden, die gut funktionieren.

Weiter gehen

Es gibt viele verschiedene Programmierstile, wie z.B. prozedural, funktional, objektorientiert usw. Selbst innerhalb einer objektorientierten Sprache wie Python kann ich sehr unterschiedliche Ansätze verwenden, um Code zu schreiben. Die erste Lösung könnte man als dynamischen Programmieransatz bezeichnen, weil du versuchst, das größere Problem zu lösen, indem du zuerst kleinere Probleme löst. Wenn du rekursive Funktionen interessant findest, ist das Tower of Hanoi-Problem eine weitere klassische Übung. Rein funktionale Sprachen wie Haskell vermeiden meist Konstrukte wie for Schleifen und verlassen sich stark auf Rekursion und Funktionen höherer Ordnung.Sowohl gesprochene als auch Programmiersprachen prägen die Art und Weise, wie wir denken, und ich möchte dich ermutigen, dieses Problem mit anderen Sprachen zu lösen, die du kennst, um zu sehen, wie du andere Lösungen schreiben könntest.

Überprüfung

Die wichtigsten Punkte aus diesem Kapitel:

• Innerhalb der Funktion get_args() kannst du eine manuelle Validierung der Argumente durchführen und die Funktion parser.error() verwenden, um manuell argparse Fehler zu erzeugen.

• Du kannst eine Liste als Stapel verwenden, indem du Elemente ein- und ausschiebst.

• Die Verwendung von yield in einer Funktion macht sie zu einem Generator. Wenn die Funktion einen Wert liefert, wird der Wert zurückgegeben und der Zustand der Funktion bleibt erhalten, bis der nächste Wert angefordert wird. Generatoren können verwendet werden, um einen potenziell unendlichen Strom von Werten zu erzeugen.

• Eine rekursive Funktion ruft sich selbst auf, und die Rekursion kann zu ernsthaften Leistungsproblemen führen. Eine Lösung ist die Memoisierung, um Werte zwischenzuspeichern und Neuberechnungen zu vermeiden.

• Funktionen höherer Ordnung sind Funktionen, die andere Funktionen als Argumente annehmen.

• Die Funktionsdekoratoren von Python wenden HOFs auf andere Funktionen an.

• Benchmarking ist eine wichtige Technik, um den leistungsstärksten Algorithmus zu ermitteln. Mit den Tools hyperfine und bench kannst du die Laufzeiten von Befehlen über viele Iterationen hinweg vergleichen.

• Das Modul random bietet viele Funktionen für die pseudozufällige Auswahl von Werten.

¹ Wie die legendären David St. Hubbins und Nigel Tufnel feststellten: "Es ist ein schmaler Grat zwischen dumm und clever".