-
-
Save dg/2341908 to your computer and use it in GitHub Desktop.
// fibonacci(40) takes 2 seconds in Node.js 0.6.14 | |
// http://en.wikipedia.org/wiki/Fibonacci_number | |
function fibonacci(n) { | |
return n < 2 ? n : fibonacci(n-2) + fibonacci(n-1); | |
} |
// fibonacci(40) takes 60 seconds in PHP 5.4.0 | |
// fibonacci(40) takes 21 seconds in PHP 7 | |
function fibonacci($n) { | |
return $n < 2 ? $n : fibonacci($n-2) + fibonacci($n-1); | |
} |
# fibonacci(40) takes 42 seconds in Python 3.2.2 | |
def fibonacci(n): | |
return n if n < 2 else fibonacci(n-1) + fibonacci(n-2) | |
# fibonacci(40) takes 18 seconds in Ruby 1.9.3 | |
def fibonacci(n) | |
n < 2 ? n : fibonacci(n-1) + fibonacci(n-2) | |
end |
Ked uz sa chceme precuravat, zvysil som N na 80 :)
#include <cstdio>
int main() {
long long a = 0, b = 1;
for (int i = 2; i <= 80; i++) {
long long c = a + b; a = b; b = c;
}
printf("%lld\n", b);
}
$ time ./a.out
23416728348467685
real 0m0.002s
user 0m0.000s
sys 0m0.000s
Tvoje ruby hlavne uz neda spravny vysledok :):
$time ruby fib.rb
23416728348467744
real 0m0.021s
user 0m0.017s
sys 0m0.003s
Fakt O(log N) algoritmus, co umocnuje matice sa mi teraz pisat nechce. Zvlast ked pre male N je uplne nezmyselny, ze ;)
Nakoniec aj umocnovanie matic:
def zero(m,n):
# Create zero matrix
new_matrix = [[0 for row in range(n)] for col in range(m)]
return new_matrix
def mult(matrix1,matrix2):
# Matrix multiplication
if len(matrix1[0]) != len(matrix2):
# Check matrix dimensions
print 'Matrices must be m*n and n*p to multiply!'
print len(matrix1[0])
print len(matrix2)
else:
# Multiply if correct dimensions
new_matrix = zero(len(matrix1),len(matrix2[0]))
for i in range(len(matrix1)):
for j in range(len(matrix2[0])):
for k in range(len(matrix2)):
new_matrix[i][j] += matrix1[i][k]*matrix2[k][j]
return new_matrix
base = [[1, 1], [1, 0]]
n = 100000
res = [[1, 0], [0, 1]]
while n > 0:
if n % 2 == 1:
res = mult(res, base)
base = mult(base, base)
n /= 2
print res[0][1]
$ time python2.7 mm.py >x
real 0m0.070s
user 0m0.063s
sys 0m0.003s
V porovnani s obycajnym ratanim:
n = 100000
a = 0
b = 1
for i in xrange(2, n+1):
c = a + b
a = b
b = c
print b
$ time python2.7 fib.py >y
real 0m0.260s
user 0m0.253s
sys 0m0.003s
Tvoj ruby kod spravi pre 100000 nasledovne:
$ time ruby fib.rb >z
fib.rb:5:in `to_i': Infinity (FloatDomainError)
from fib.rb:5:in `fibonacci'
from fib.rb:9:in `<main>'
real 0m0.024s
user 0m0.017s
sys 0m0.007s
@usamec: Ok beriem, ale stale to este neni uplne ono. http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms
O com mi vsak slo naozaj. Microbenchmarky a porovnavanie rychlosti jazykov su podla mna zlo, lebo ten cas co usetris na rychlosti kodu, nehra vo vacsine aplikacii ziadnu vyznamnu rolu. Lepsim algoritmom ziskas mnohonasobne viac.
@jsuchal to zní, jako by jsi chtěl říct, že použitý algoritmus není správný, nebo je snad dokonce hovadina. Nedává snad správné výsledky?
@dg Algoritmus je správny (ten vzorec si vieš vypočítať a overiť na papieri). Problém, ktorý vznikol je realizácia pre čísla s konečnou presnosťou. A áno, nedáva to teda pre vyššie čísla správne výsledky.
Správny algoritmus v pomalšom jazyku vie byť aj 30x rýchlejší ako hovadina trebárs aj v C.
PS. Je mi jasné, že tu ide skôr o rýchlosť jazyka pri rekurzívnych volaniach, ale ja som to nenazval "Fibonacci number benchmark" :D