Projekt Euler # 2 Python 3.5 Hilfe zur Latenz

Question

Ich bin neu in der Programmierung und versuche, die Projekt Euler-Übungen zu machen, um meine Kenntnisse über Kodierung zu verbessern. Ich bin auf verschiedene Lösungen in Bezug auf Projekt Euler # 2 gestoßen.

Allerdings möchte ich wissen, warum mein Code so viel länger dauert, um im Vergleich zu einer Lösung, die ich gefunden habe, zu berechnen.

Ich würde mich freuen, wenn jemand mich über die Unterschiede zwischen den beiden führen kann.

---

Mein Code:

def fib(n): 
if n==0: 
    return 0 
elif n == 1: 
    return 1 
else: 
    f=fib(n-1)+fib(n-2) 
    return f 

i=0 
store=[] 
while fib(i)<=4000000: 
    i += 1 
    if fib(i)%2 == 0: 
     store.append(fib(i)) 

print('The total is: '+str(sum(store))) 

---

Online-Lösung gefunden:

a = 1 
b = 2 
s = 0 
while b <= 4000000: 
if not b % 2: 
    s += b 
a, b = b, a + b 
print(s) 

Answer 1

Um berechnet fib(10), bei der Implementierung:

fib(10) = fib(9) + fib(8) 

, in dem fib(9) rekursiv berechnet:

fib(9) = fib(8) + fib(7) 

das Problem? Das Ergebnis von fib(8) muss zweimal berechnet werden! Um den Ausdruck weiter zu erweitern (z. B. um das Ergebnis von fib(8) zu erhalten), ist die redundante Berechnung groß, wenn die Anzahl groß ist.

---

Rekursion selbst ist nicht das Problem, aber Sie haben das Ergebnis kleiner Fibonacci-Zahlen zu speichern, anstatt auf den gleichen Ausdruck zu berechnen und auf. Eine mögliche Lösung besteht darin, ein Wörterbuch zu verwenden, um das Zwischenergebnis zu speichern.

Answer 2

Sie verwenden rekursive Aufrufe für eine Funktion, bei der die andere Lösung eine einfache iterative Schleife verwendet.

Die Ausführung eines Funktionsaufrufs ist mit einem gewissen Mehraufwand für den Aufruf und die Rückgabe verbunden. Für größere Zahlen von n werden Sie viele dieser Funktionsaufrufe haben.

Das Anhängen an eine Liste immer wieder und das Aufsummieren ist wahrscheinlich auch langsamer als über einen Akkumulator.

Answer 3

Ihre Lösung ruft jedes Mal eine rekursive Funktion (mit 2 Rekursionen) auf, wenn sie in Ihre while-Schleife geht. In der Schleife führen Sie dann dieselbe Funktion erneut aus. Die andere Lösung fügt nur Zahlen hinzu und führt dann eine Permutation durch. Ich schätze, du brauchst die Fibonacci nicht wirklich, aber wenn du darauf bestehst, führe sie nur einmal aus und speichere das Ergebnis, anstatt es erneut auszuführen. Plus Sie speichern alle Ihre Ergebnisse und summieren sie am Ende. Das kostet auch (nicht nur) Zeit, vielleicht müssen Sie keine Zwischenergebnisse speichern.

Answer 4

Wie einige andere Antworten darauf hingewiesen haben, verursacht die Rekursion, dass Ihre fib() Funktion sehr häufig aufgerufen wird, 111 561 532 mal tatsächlich. Dies wird leicht durch Hinzufügen eines Zählers angezeigt:

count = 0 

def fib(n): 
    global count 
    count += 1 

    if n==0: 

# the rest of your program 

print(count) 

Es gibt zwei Möglichkeiten, dies zu beheben; schreiben Sie Ihr Programm so um, dass es iterativ statt rekursiv ist (wie die andere Lösung, die Sie gepostet haben), oder cachen Sie Zwischenergebnisse von fib().

See, rufen Sie fib(8), was wiederum hat fib(7) und fib(6) zu nennen, etc, etc. Gerade die Berechnung fib(8) 67 Anrufe fib() nimmt!

Aber später, wenn Sie anrufen fib(9), dass auch Anrufe fib(8), die die ganze Arbeit immer wieder (67 mehr Anrufe zu fib()) zu tun hat. Das gerät schnell außer Kontrolle. Es wäre besser, wenn sich fib() daran erinnern könnte, dass es bereits fib(8) berechnet und sich das Ergebnis merkt. Dies ist bekannt als Caching oder Memoisierung.

Zum Glück hat Pythons Standardbibliothek einen Dekorateur nur für diesen Zweck, functools.lru_cache:

from functools import lru_cache 

@lru_cache() 
def fib(n): 
    if n==0: 

... 

Auf meinem Computer, Ihre Programmausführung geht von 111 561 532 Anrufungen von fib() in 27 Sekunden bis 35 Anrufungen in 0,028 Sekunden .