Fibonacci-Sequenz in eine Datei schreiben Python? - Python

Ich habe einige Schwierigkeiten gehabt, jeden zu bekommenNummer in der Fibonacci-Folge, um in eine Datei zu schreiben, ich weiß, dass ich etwas falsch mache, aber ich kann es nicht genau bestimmen. Gibt es einen effizienteren Ansatz? Jede Hilfe wird geschätzt.

import sys
import os
import time

known = {0:0, 1:1}

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

def fibonacci_fast(n):
f = open("fib500.txt", "w")
if n in known:
return known[n]
res = fibonacci_fast(n-1) + fibonacci_fast(n-2)
print res
if fibonacci_fast:
f.write(res)
known[n] = res
return res

def main():
time_start = time.time()
print fibonacci_slow(10)
time_end = time.time()
print "Time for slow fibonacci to complete ", time_end - time_start

time_start = time.time()
print fibonacci_fast(500)

time_end = time.time()
print "Time for fast fibonacci to complete ", time_end - time_start


if __name__ == "__main__":
main()

Antworten:

1 für die Antwort № 1

Sie müssen die Schrift in die Datei aufnehmendie Methode fibonacci_fast. Bei jedem Aufruf wird die Datei erneut geöffnet. Da Sie sie nicht geschlossen haben, kann nicht garantiert werden, dass sie in die Datei geschrieben wird.

In Bezug auf Geschwindigkeit ist Rekursion nicht für Ihre Berechnungen geeignet. Sie brauchen den rekursiven Aufruf nicht:

res = fibonacci_fast(n-1) + fibonacci_fast(n-2)

denn du hättest schon mit dem einfallen könnenRückgabewert dieser Anrufe. Es ist besser, von Anfang an zu arbeiten und zu arbeiten, bis Sie den gewünschten Wert erreicht haben, ohne den durch diese Art von Rekursion verursachten Overhead zu erleiden. Mit anderen Worten, ein iterativer Ansatz wäre schneller.

Wie Sie wahrscheinlich zu zeigen versuchen, ist das Generieren der n-ten Zahl in der Fibonacci-Sequenz kein guter Rekursionskandidat im Sinne von Geschwindigkeit / Optimierung.

Wenn Sie Ihr fibonacci_fast in etwas ändern:

def fibonacci_fast(n):
known = [0, 1]
count = 0
for i in range(n):
newNum = known[0] + known[1]
known[0] = known[1]
known[1] = newNum
return known[0]

und Ausführen Ihres Testskripts:

def main():
time_start = time.time()
print fibonacci_slow(20)
time_end = time.time()
print "Time for slow fibonacci to complete ", time_end - time_start

time_start = time.time()
print fibonacci_fast(20)
time_end = time.time()
print "Time for fast fibonacci to complete ", time_end - time_start

du erhältst:

6765
Time for slow fibonacci to complete  0.0043318271637
6765
Time for fast fibonacci to complete  0.00010085105896

und um es in eine Datei zu schreiben, können Sie ein Dateiargument hinzufügen, in das Sie schreiben können:

def fibonacci_fast(n, f):
known = [0, 1]
for i in range(n):
newNum = known[0] + known[1]
known[0] = known[1]
known[1] = newNum
f.write(str(known[0]) + " ")
return known[0]

und nenne es so:

f = open("fib.txt", "w")
fibonacci_fast(20, f)
f.close()

oder der "pythonic" Weg (der etwas schneller ist):

with open("fib.txt", "w") as f:
fibonacci_fast(20, f)

Sie können den großen Unterschied zwischen den beiden sehenrekursiver und iterativer Ansatz, wenn Sie versuchen, die 500ste Zahl in der Sequenz zu generieren. Es dauert Minuten (wenn nicht Stunden, ich habe nicht gewartet), um die rekursive Funktion zu beenden, aber nur einen Bruchteil einer Sekunde, um die iterative Methode auszuführen, selbst wenn sie in eine Datei geschrieben wird.

Weitere Informationen zur Fibonacci-Sequenz finden Sie hier Hier.

---

0 für die Antwort № 2

Ihre Rekursion ist etwas unbeholfen, berechnet jede Zahl viele Male neu. Es ist ein klassisches Problem, dieser iterative Algorithmus würde funktionieren:

def fib2file(n, fname):
with open(fname, "w") as of:
f1, f2, f3 = 0, 1, 0
for _ in range(n):
f1 = f2
f2 = f3
f3 = f1 + f2
of.write("%dn" % f3)

---