Numpy: Fibonacci-Folge rekursiv mit Dictionary

[theCed7]

Hi,

ich habe folgenden Code, der mir die Fibonacci-Folge rekurisv berechnet und schon berechnete Funktionen in eine Liste schreibt:

Code: Alles auswählen

memo = {0:0, 1:1}
def fibonacci_mem(n):
	if n not in memo:
		memo[n] = fibonacci_mem(n-1) + fibonacci_mem(n-2)
	return memo[n]

Nun würde ich statt der Liste gerne ein Numpy-Array verwenden, wobei ich mich mit NumPy noch nicht wirklich gut auskenne:

Code: Alles auswählen

import numpy

memo2 = numpy.array([[0,0], [1,1]])	
def fibonacci_num(n):
	if n not in memo2:
		memo2[n] = fibonacci_num(n-1) + fibonacci_num(n-2)
	return memo2[n]

Gibt mir folgendes zurück:

Code: Alles auswählen

[ced@Arch Python]$ ./info.py 
Traceback (most recent call last):
  File "./info.py", line 48, in <module>
    print(fibonacci_num(int(n)))
  File "./info.py", line 45, in fibonacci_num
    memo2[n] = fibonacci_num(n-1) + fibonacci_num(n-2)
  File "./info.py", line 45, in fibonacci_num
    memo2[n] = fibonacci_num(n-1) + fibonacci_num(n-2)
  File "./info.py", line 45, in fibonacci_num
    memo2[n] = fibonacci_num(n-1) + fibonacci_num(n-2)
  File "./info.py", line 45, in fibonacci_num
    memo2[n] = fibonacci_num(n-1) + fibonacci_num(n-2)
IndexError: index 2 is out of bounds for axis 0 with size 2
[ced@Arch Python]$ 

Ist ein 2-dimensionales Array der falsche Ansatz? Im Grunde muss ja nur jedem n der Wert fibonacci(n) zugeordnet werden...

[BlackJack]

@theCed7: Ein zweidimensionales Array ist der falsche Ansatz, denn in der einen Spalte von dem Arrays speicherst Du fortlaufende ganze Zahlen — warum?

Und der Fehler deutet darauf hin, dass ein Array auch gross genug sein muss um die Werte aufzunehmen. Du müsstest also das Array vorher entsprechend gross anlegen, beziehungsweise wenn nötig ein neues, grösseres anlegen, die alten Werte dort rüberkopieren und dann die bis zum neuen, grösseren `n` ergänzen.

Und *das* dann wenn es hier tatsächlich um Effizienz gehen sollte, dann besser nicht rekursiv, sondern iterativ.

Wobei Du bei einer Numpy-Lösung auch unbedingt darauf achten musst, ist dass die Zahlen nicht beliebig gross werden dürfen. Das funktioniert nicht für beliebig grosse `n`, selbst wenn man den Typ für die Elemente mit `numpy.uint64` vorgibt, statt sich mit dem impliziten Typ zufrieden zu geben den man bekommt wenn man nichts angibt.

[theCed7]

@theCed7: Ein zweidimensionales Array ist der falsche Ansatz, denn in der einen Spalte von dem Arrays speicherst Du fortlaufende ganze Zahlen — warum?

Und der Fehler deutet darauf hin, dass ein Array auch gross genug sein muss um die Werte aufzunehmen. Du müsstest also das Array vorher entsprechend gross anlegen, beziehungsweise wenn nötig ein neues, grösseres anlegen, die alten Werte dort rüberkopieren und dann die bis zum neuen, grösseren `n` ergänzen.

Könntest du das eventuell mal in Code fassen? Ich habe NumPy bisher nur für analytische Geometrie verwendet und mich mit Array noch zu wenig beschäftigt..

Und *das* dann wenn es hier tatsächlich um Effizienz gehen sollte, dann besser nicht rekursiv, sondern iterativ.

Ja, dass ist so ein bisschen die Idee dahinter. Ich habe die verschiedenen Funktionene (iterativ, rekursiv, rekursiv mit Liste) mal zeitlich verglichen und rekursiv mit Liste war tatsächlich ein bisschen schneller als iterativ, der Vorteil hat sich dann vor allem für größere n-Werte ausgespielt. Wobei irgendwann natürlich die recursion depth erschöpft ist..

[BlackJack]

@theCed7: Dann beschäftige Dich halt erst mal mit Numpy-Arrays wenn Du Dich damit nicht auskennst.

*Aber* als erstes solltest Du die Obergrenze für `n` ermitteln bis zu der man das überhaupt mit Numpy-Arrays sinnvoll lösen kann. Fibonaccizahlen werden sehr schnell sehr gross. Vielleicht ist mein System hier auch zu alt aber der grösste ganzzahlige Wertebreich von dem Numpy was ich hier installiert habe ist `uint64` und damit kommt man nicht einmal bis zur 100. Fibonaccizahl. Ich sehe den Sinn von Numpy-Arrays hier nicht wirklich.

Du könntest statt eines Wörterbuchs eine Liste verwenden um den Mehraufwand zwischen diesen beiden Typen zu sparen. Listen sind mit `append()` beziehungsweise `extend()` auch einfacher zu erweitern als Numpy-Arrays.

Ich würde mit einer Generatorfunktion anfangen die iterativ unendlich viele Fibonaccizahlen liefert. Und dann eine Liste mit bisher berechneten Werten bei `n` die noch nicht berechnet wurden, entsprechend erweitern. `itertools.islice()` kann dabei nützlich sein.

Das ”Gedächtnis” solltest Du als Attribut an die Funktion hängen statt es Modulglobal zu definieren. Dann muss man sich nicht für neue Funktionen neue Namen für `memo` ausdenken.