Verständnisfrage

[evev]

Hi Leute,
habe mich soeben hier angemeldet, da ich keine Lösung zu meiner Frage finden konnte.
Ich arbeite zur Zeit mit dem Buch Think Python. Das Problem welche ich habe, bezieht sich auf den folgenden Code.
Ich verstehe nicht warum er alle Fibo-Zahlen ausgibt anstatt nur der vorgegebenen in known ={0:0,1:1} und der nZahl, beispielsweise n = 30.
er gibt einfach alles aus bis einschließlich 30 warum(Es ist doch keine for schleife bei der man sagt, von x bis y bitte alles)? Vielleicht kann mir das jemand erklären.

Code: Alles auswählen

known={0:0, 1:1}
def fibon(n):
    if n in known:
        return known[n]
    res = fibon(n-1)+fibon(n-2)
    known[n] = res
    return res
fibon(30)
print known

mfg

[BlackJack]

@evev: Die `fibon()`-Funktion berechnet die Zahl für das gegebene `n` (falls noch nicht in `known` vorhanden) und trägt sie in `known` ein. Dazu muss sie alle vorhergehenden Zahlen berechnen, weil die ja aufaddiert werden. Dazu ruft `fibon()` die Funktion `fibon()` für die beiden Vorgängerwerte auf, die in der Funktion `fibon()` berechnet und in `known` eingetragen werden. Dazu ruft `fibon()` die Funktion `fibon()` für die beiden Vorgängerwerte auf, die in der Funktion `fibon()` berechnet und in `known` eingetragen werden. Dazu ruft `fibon()` die Funktion `fibon()` für die beiden Vorgängerwerte auf, die in der Funktion `fibon()` berechnet und in `known` eingetragen werden. Dazu ruft `fibon()` die Funktion `fibon()` für die beiden Vorgängerwerte auf, die in der Funktion `fibon()` berechnet und in `known` eingetragen werden. Dazu ruft `fibon()` die Funktion `fibon()` für die beiden Vorgängerwerte auf, die in der Funktion `fibon()` berechnet und in `known` eingetragen werden…

Und so stehen am Ende dann alle Zahlen in `known`, denn die wurden für den ersten Aufruf von `fibon()` letztlich alle benötigt und dementsprechend auch berechnet. Vollzieh das am besten mal auf einem Blatt Papier nach. Vielleicht mit einer kleineren Zahl als 30. 4 oder 5 wäre gut.

Du solltest halt nicht `known` ausgeben, sondern den Rückgabewert von ``fibon(30)``, mit dem Du im Moment gar nichts machst und einfach ”verfallen” lässt.

[evev]

Danke BlackJack für deine einfache und schnelle Erklärung. Manchmal brauch man eben den richtigen Anstoß .
Mit der Known Ausgabe wollte ich nur schauen welche Zahlen vorhanden sind und das hatte mich irritiert, aber mit deiner Erklärung macht es Sinn.
Da er ja die Funktion(n-1) mit der von (n-2) addiert, muss diese erstmal generiert werden und da bei n = 30 die 29 und 28 nicht vorhanden sind werden diese erst berechnet und dann die n=27 n=26 n=25 usw.. oder täusche ich micht?

[Zizibee]

Das Ganze ist noch etwas verzweigter. In fibon(30) wird fibon(29) und fibon(28) aufgerufen. So weit so gut.
Jetzt wird aber in fibon(29) die Funktionen fibon(28) und fibon(27) aufgerufen( also n-1 und n-2)
fibon(28) aus der ersten Zeile ruft fibon(27) und fibon(26) auf (also wieder n-1 und n-2).
Daher sind wir jetzt in fibon(28), fibon(27), fibon(27) und fibon(26). Jedes dieser 4 Funktionen ruft jetzt wieder fibon(n-1) und fibon(n-2) auf, so dass dann schon acht Funktionen offen sind (+ die vier vorher + die zwei vorher + der erste Aufruf). Das alles geht so lange, bis man bei fibon(1) oder fibon(0) angelangt ist und dann geht jeder Zweig über return zurück zum Ursprung.

So jedenfalls habe ich das Ganze verstanden.

[BlackJack]

@Zizibee: Ganz so viele sind nicht ”offen” weil ja erst die linke Seite von jedem ``+`` ausgewertet wird und das geht bis 1 runter, das heisst wenn die rechte Seite vom ``+`` ausgewertet wird, dann ist das Ergebnis jeweils bereits in `known` vorhanden und es geht nicht auch dort jedes mal bis 1 runter. Das ist ja gerade der Sinn von `known`, das man sich ganz viele Aufrufe dadurch spart wenn man sich die Zwischenergebnisse merkt und nur rekursiv absteigt wenn man das Ergebnis nicht schon mal berechnet hatte.

[Zizibee]

@BlackJack: Danke für die Erklärung, wieder etwas dazu gelernt!

[evev]

Hi,
da ich ungern einen neuen Tread eröffnen möchte schreib ich hier gleich weiter, da die Überschrift die gleiche wäre.
Habe hier zwei Codes einer aus Think Python, der andere ist beim lösen der Aufgabe enstanden. Beide Codes geben so ziehmlich das selbe aus, nur läuft der aus dem Buch doppelt so schnell wie meiner . Auch wenn die Frage komisch kling, aber warum ist das so? Beide öffnen die gleiche txt Datei.

Code: Alles auswählen

import string
import time

# langsamer
start_time=time.time()
def give(z):
    x=open(z).read()
    return x
give('word1.txt')

def check_word(word):
    x={}

    for letter in string.ascii_letters: 
        x[letter]=0
        for b in word:
            if b in letter:
                x[letter] +=1
    return x

print check_word(give('word1.txt')),'%s second'%(time.time()- start_time)


# schneller
start_time=time.time()
def check_word(word):

    hist = {}
    for x in word:
        hist[x] = hist.get(x, 0) + 1
    return hist


print check_word(give('word1.txt')),'%s second'%(time.time()- start_time)

[Sirius3]

@evev: zähl mal die Anzahl der for-Schleifen in der ersten und in der zweiten Variante. Ach ja, beim ersten mal wird die Datei auch zweimal gelesen.

[evev]

liegt also nur an der 2ten for schleife? die alles verdoppelt?

[Sirius3]

@evev: nicht verdoppelt sondern verzweiundfünfzigfacht.

[evev]

@Sirius: Danke für die Erklärung.

[BlackJack]

@evev: Für eine kürzere Lösung würde sich `collections.Counter` anbieten.

[Sirius3]

so:

Code: Alles auswählen

from collections import Counter as check_word

[evev]

@ euch beide^^, habe jetzt alle 3 module durchlaufen lassen und die 2te Variante ist weiterhin die schnellere aber vielleichtt mach ich auch was falsch. Werde den code oben mal anpassen... Geht wohl nicht

Code: Alles auswählen

from collections import Counter
print Counter(give('word.txt')),'%s second'%(time.time()- start_time)

alles im allen
1. Variante 1.10799
2. Variante 0.17300
3. Variante 0.43099