Seite 1 von 1
Fibonacci-Reihe bis in eine Tiefe von x
Verfasst: Sonntag 27. August 2006, 11:18
von Craven
Hi,
Ich brauche für ein andres Script die Zahlen der Fibonacci-Reihe bis zu einer Tiefe von x.
Mit diesem Script bekomme ich im Endeffekt das was ich brauche, allerdings dauert das bei einer Tiefe von 50 und höher, bis zu einer Stunde und mehr.
Code: Alles auswählen
import os, sys
path = "C:/Dokumente und Einstellungen/Craven/Desktop/Fibonacci.val"
file = open(path, "w+")
n = 100
V = float(raw_input("Geben Sie de Anzahl der Durchlaeufe ein: "))
def CompFibonacci(n):
x = 1
fibonacci = [0, 1]
while x <= V:
for i in xrange(2, n):
asd = fibonacci.append(fibonacci[-2] + fibonacci[-1])
print i, "---", x
n += 100
x += 1
else:
pass
file.write(str(fibonacci))
CompFibonacci(n)
Also dachte ich mir, dass man sozusagen die liste nach jedem Durchlauf an die Datei anhängt, dann die Liste löscht, damit der speicherverbraucht nicht so utopisch wie oben ist
Hat jemand nen Vorschlag, wie das konkret gehen könnte?
Danke
MfG,
Craven
Verfasst: Sonntag 27. August 2006, 12:05
von Maho
Das ist kein Wunder. Die funktion berechnet nicht die ersten 50 Zahlen, sondern die ersten 50*n (also etwa 150.000(!) Zahlen). Woher hast du die Funktion?
Code: Alles auswählen
def CompFibonacci():
n = float(raw_input("Geben Sie die Anzahl der Durchlaeufe ein: "))
fib = [0, 1]
for i in xrange(n):
fib.append(fib[-2]+fib[-1])
return fib
Diese Funktion berechnet die ersten n Fibonacci-Zahlen und gib sie als Liste zurück.
Verfasst: Sonntag 27. August 2006, 12:13
von Craven
Hi Maho
Dass das script nicht die 'ersten' 50 Zahlen berechnet, ist mir auch klar ^^
Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen
Genau deswegen will ich ja das ganze etwas Ressourcenfreundlicher machen.
Die Funktion hab ich zu 90% selber geschrieben
MfG,
Craven
Verfasst: Sonntag 27. August 2006, 12:39
von Crush
Craven hat geschrieben:Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen
Hi Craven,
Aber wozu steht denn das "n += 100" in Zeile 16? Das gibt dann ja nicht 50*100 Zahlen sondern 100+200+300+400+...+n*100 Zahlen!
(oder in pythoncode:
Code: Alles auswählen
def anzahl(n,p):
z = 0
for i in range(n):
z += (i+1)*p
return z
print anzahl(50,100)
)
Das wären dann 127'500 Zahlen.
Zum eigentlichen Problem fällt mir leider nichts ein, tut mir Leid ...
Crush
Verfasst: Sonntag 27. August 2006, 12:53
von Maho
Craven hat geschrieben:
Dass das script nicht die 'ersten' 50 Zahlen berechnet, ist mir auch klar ^^
Mit "einer Tiefe von 50" mein ich die Durchgänge, also in dem fall 50 * 100 Zahlen
Häh? Das ergibt ziemlich wenig sinn. Wenn du die ersten 5000 Zahlen haben willst, dann benutze eben n=5000. Obendrein berechnet deine Funktion ja nicht 50*100, sondern 50*(100-2), da du nur von 2 bis n gehen lässt.
Code: Alles auswählen
def CompFibonacci(path):
n = float(raw_input("Geben Sie die Anzahl der Durchlaeufe ein: "))
target = file(path, 'a')
a, b = 0, 1
print >> target, a
print >> target, b
for i in xrange(n):
a, b = b, a+b
print >> target, b
Hier, das ganze ohne Liste, und direkt in eine Datei gespeichert. Beachte bitte das die daten an die Datei angehängt werden. D.h. wenn die Datei bereits existiert, musst du selber für Ordnung sorgen.
EDIT: Was mir gerade eingefaellen ist: du könntest die Funktion natuerlich auch in einen Generator umwandeln, anstatt mit einer grossen Liste im Speicher zu hantieren, oder alles in einer Datei zwischenzuspeichern. Vorteil der Datei ist allerdings: du berechnest die Zahlen nur einmal, und kannst die Datei später immer wieder auslesen.
Code: Alles auswählen
def CompFibonacci(n=5000):
a, b = 0, 1
yield a
yield b
for i in xrange(V):
a, b = b, a+b
yield b
Verfasst: Sonntag 27. August 2006, 13:53
von Craven
Danke für die schnellen Antworten
Das ganze ist erst mal ein beta script, das ich heute um 3 in der früh nach einer 5 Tage LAN gemacht hab
Nicht dass ihr meint, ich würde sonst so nen Bockmist reinhauen ^^
Dass es nicht 5000 Zahlen sind, stimmt natürlich
Ich wollte eigentlich die Fibonacci-Reihe (rein theoretisch) bis ins Unendliche berechnen lassen, und gleichzeitig die Ressourcen schonen, durch etwas wie das zwischenspeichern der Zahlen, sozusagen ein Resuming-system.
Ich werde mich nochmal dahinter setzen, wenn ich genug Schlaf nachgeholt hab

Verfasst: Sonntag 27. August 2006, 14:24
von Maho
Code: Alles auswählen
def CompFibonacci(n, path):
try:
source = file(path)
a = int(source.readline())
b = int(source.readline())
source.close()
except IOError:
a, b = 0, 1
yield a
yield b
for i in xrange(n):
a, b = b, a+b
yield b
file(path, 'w').write('%s\n%s' % (a, b))
Berechnet n Zahlen und speichert zum Schluss die letzten beide Werte für den nächsten durchlauf. Beim start prüft die Funktion, ob eine Datei mit neuen startwerten existiert um diese dann ggf. zu nutzen.
Ist das in etwa das was du suchst?
Verfasst: Sonntag 27. August 2006, 14:46
von Crush
man könnte das so lösen:
Code: Alles auswählen
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def fib(a, b, n):
fib = [a,b]
for i in xrange(n-2):
fib.append(fib[-2]+fib[-1])
fib.pop(0)
return fib
f = open('dateiname','w')
f.write(str(fib(0, 1, 1000)))
f.close()
hier befinden sich in "fib" jeweils nur 2 Zahlen. Nach dem Berechnen der nächsten wird die erste Zahl entfernt (mit "fib.pop(0)). Mit "return fib[-1]" wird schliesslich die "(n-1)-te" und die n-te Fibonacci-Zahl zurückgegeben. Ach ja, und a und b sind die Startwerte.
Crush
Verfasst: Sonntag 27. August 2006, 22:28
von jAN
ich hab grad das hier gefunden... ich weis net ob dir das hilft aber trotzdem...
Code: Alles auswählen
class memoized(object):
"""Decorator that caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned, and
not re-evaluated.
"""
def __init__(self, func):
self.func = func
self.cache = {}
def __call__(self, *args):
try:
return self.cache[args]
except KeyError:
self.cache[args] = value = self.func(*args)
return value
except TypeError:
# uncachable -- for instance, passing a list as an argument.
# Better to not cache than to blow up entirely.
return self.func(*args)
def __repr__(self):
"""Return the function's docstring."""
return self.func.__doc__
@memoized
def fibonacci(n):
"Return the nth fibonacci number."
if n in (0, 1):
return n
return fibonacci(n-1) + fibonacci(n-2)
print fibonacci(12)
EDIT:
habs mal ausprobiert... es ist sinnlos für das aktuelle Problem...
Verfasst: Montag 28. August 2006, 00:55
von BlackJack
Alternativvorschlag, der wohl jede reine Python-Implementierung schlagen dürfte:
Code: Alles auswählen
import gmpy
def fibonacci(n=5000):
for i in xrange(n):
yield gmpy.fib(i)
Das berechnen von `fib(10000000)` braucht auf meiner lahmen Kiste gerade mal 2 Sekunden. Die Umwandlung der ca. 2 Millionen Ziffern in eine Zeichenkette dauert wesentlich länger.
Verfasst: Montag 28. August 2006, 06:17
von Maho
Vielleicht solltest du auch noch
http://sourceforge.net/projects/gmpy erwähnen.
Verfasst: Mittwoch 13. September 2006, 18:35
von Craven
Hier ist ein verspätetes Update, allerdings ist mir nicht ganz klar wie die Fehlermeldung zustande kommt.
Code: Alles auswählen
def cf(tiefe):
file2 = open(Pfad, "a+")
fibo = [1, 2]
counter = 0
try:
resuming(file2, fibo)
finally:
while counter <= tiefe:
fibos = fibo[-2] + fibo[-1]
fibo.append(fibos)
del fibo[0]
file2.write("%s" % fibo[-1])
file2.write("\r\n")
counter += 1
def resuming(file2, fibo):
try:
a = file2.readline(-1)
b = file2.readline(-2)
fibo = []
fibo.append(a, b)
return fibo
except:
pass
cf(int(raw_input("Anzahl der loops: ")))
Code: Alles auswählen
Traceback (most recent call last):
File "Fibonacci.py", line 37, in ?
cf(int(raw_input("Anzahl der loops: ")))
File "Fibonacci.py", line 23, in cf
file2.write("%r" % fibo[-1])
IOError: (0, 'Error')
wenn ich
Code: Alles auswählen
finally:
while counter <= tiefe:
fibos = fibo[-2] + fibo[-1]
fibo.append(fibos)
del fibo[0]
file2.write(fibo[-1])
file2.write("\r\n")
counter += 1
ausführe, kommt
Code: Alles auswählen
TypeError: argument 1 must be string or read-only character buffer, not int
Ich hoffe jemand von euch kann mir da raushelfen, ich komm nicht drauf
Danke schonmal für eure Hilfe
MfG,
Craven
edit:// Falsche Variable returned ^^
Verfasst: Mittwoch 13. September 2006, 18:50
von DatenMetzgerX
fibo[0] ist ein integer und '%r' fibo[0] übergibt einen string
sonst mach str(fibo[0])
Verfasst: Mittwoch 13. September 2006, 19:01
von Craven
Hi DatenMetzgerX
Du meinst so
?
Verfasst: Mittwoch 13. September 2006, 19:32
von DatenMetzgerX
genau!!!
Verfasst: Donnerstag 14. September 2006, 10:20
von Craven
Verfasst: Donnerstag 14. September 2006, 12:41
von BlackJack
Deine `resuming()` Funktion funktioniert nicht. Man kann nicht einfach Zeilen vom Dateiende her mit negativen Zahlen ansprechen. Die Angabe ist die Puffergrösse die Python zum lesen von Zeilen benutzen soll. Werte >0 geben die Maximallänge an, Werte <=0 haben keinen Effekt. Du liest dort immer die ersten beiden Zeilen ein.
Und 'a+' ist als Dateimodus höchst undefiniert. Man sollte Dateien die man mit 'a' öffnet nur schreiben, nicht lesen und kein `seek()` durchführen.
Verfasst: Donnerstag 14. September 2006, 17:51
von Craven
Hi Blackjack!
Danke für deine Antwort
Hast du eine Idee/Tipp, wie ich das realisieren könnte?
Ansonsten gehts auch ohne resuming, was eher als test gedacht war ...
MfG,
Craven
Verfasst: Donnerstag 14. September 2006, 21:07
von Michael Schneider
Craven hat geschrieben:Hast du eine Idee/Tipp, wie ich das realisieren könnte?
Ansonsten gehts auch ohne resuming, was eher als test gedacht war ...
Hi Craven,
erstmal generell statt "a+" sowas:
Code: Alles auswählen
try:
file2 = open(Pfad, "r+")
file2.seek(0,2) ## Cursor zum Dateiende
except IOError:
file2 = open(Pfad, "w+")
Ich habe mich noch nicht weiter in den Code reingedacht, aber wenn Du nur die beiden letzten Werte brauchst (zum Addieren), dann solltest Du die nicht dauernd speichern und neu lesen. Das bremst unnötig.
Grüße,
Michael
Verfasst: Freitag 15. September 2006, 14:52
von Ezechielpitau
Ansonsten gibt es auch eine nicht-rekursive Funktion zur Berechnung. Dann sinnvoll, wenn du nur den Wert für einzelne, sehr große Zahlen berechnen willst und nicht die ganze Reihe.
siehe Formel von Binet
http://www.ijon.de/mathe/fibonacci/node2.html#0002200