Ich habe auch versucht, Fibonacci-Sequenzberechnung beschleunigen (Ruby-Version) in Python.
Die Definitionen sind gleich.
python
#normale Version
def fib1(n):
if n <= 1:
return n
n0, n1 = 0, 1
for _ in range(n):
n0, n1 = n1, n0+n1
return n0
#Hochgeschwindigkeitsversion
def fib2(n):
if n <= 1:
return n
result = [1, 0, 0, 1]
matrix = [1, 1, 1, 0]
while n > 0:
if n % 2:
result = mul(matrix, result)
matrix = mul(matrix, matrix)
n //= 2
return result[2]
def mul(a, b):
return [a[0]*b[0] + a[1]*b[2],
a[0]*b[1] + a[1]*b[3],
a[2]*b[0] + a[3]*b[2],
a[2]*b[1] + a[3]*b[3]]
Ich kann es richtig machen.
python
print([fib1(i) for i in range(11)])
print([fib2(i) for i in range(11)])
>>>
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Zeitmessung.
python
%timeit fib1(100000)
%timeit fib2(100000)
%timeit fib1(1000000)
%timeit fib2(1000000)
>>>
10 loops, best of 3: 75.7 ms per loop
100 loops, best of 3: 10.6 ms per loop
1 loops, best of 3: 6.9 s per loop
1 loops, best of 3: 374 ms per loop
Mehr als 10 mal schneller als Ruby!
Mit numpy konnte ich übrigens nur bis zu 1476 (≒ 1.3e309) berechnen.
das ist alles
Recommended Posts