J'ai aussi essayé Accélérer le calcul de la séquence de Fibonacci (version Ruby) en Python.
Les définitions sont les mêmes.
python
#version normale
def fib1(n):
if n <= 1:
return n
n0, n1 = 0, 1
for _ in range(n):
n0, n1 = n1, n0+n1
return n0
#Version haute vitesse
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]]
Je peux le faire correctement.
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]
mesure du temps.
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
Plus de 10 fois plus rapide que Ruby!
D'ailleurs, en utilisant numpy, je n'ai pu calculer que 1476 (≒ 1,3e309).
c'est tout
Recommended Posts