Yes. It finishes a little earlier than the one on the reference site, but I'm not sure, but I have to leave a memo. Reference http://d.hatena.ne.jp/sakurai_youhei/20130107/1357568535
op.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import sys
import io
import re
import math
####Memory usage and operating time check preparation
from guppy import hpy
import time
start = time.clock()
h = hpy()
####Up to here
#It seems to be posted
def fib(n):
if n < 2: return n
return fib(n-2) + fib(n-1)
#print fib(50)
def fib2(n):
a,b=0,1
return reduce(lambda x,y: x+[x[-1]+x[-2],], xrange(n-1), [a,b])[n]
print fib2(10000)
def fib3(n):
a,b=0,1
for i in range(n):
a,b=b,eval('a+b')
print a
#print fib3(500000)
#def fib4(n):
# n+=3
# f=[(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] #for
# i in range(2, n)]
# print f[-1]
#print fib4(500000)
def fib5(n):
a,b=0,1
for i in range(n):
a,b=b,a+b
print a
#print fib5(500000)
#if __name__ == 'main':
# print(fib(100))
####Memory usage and operating time output
end = time.clock()
print (h.heap())
print (end - start)
fib (n) and fib2 (n) are the first, and fib3 (n) is the pattern I tried with eval. I'm not sure because eval is used because the calculation result is taken out differently. I don't know.
| function | processing time | F(3)The value of the |
|---|---|---|
| fib() | 0.008658 seconds | 2 |
| fib2() | 0.011694 seconds | 2 |
| fib3() | 0.011055 seconds | 2 |
| function | processing time | F(10)The value of the |
|---|---|---|
| fib() | 0.010526 seconds | 55 |
| fib2() | 0.008879 seconds | 55 |
| fib3() | 0.011909 seconds | 55 |
| function | processing time | F(35)The value of the |
|---|---|---|
| fib() | 5.782845 seconds | 9227465 |
| fib2() | 0.011936 seconds | 9227465 |
| fib3() | 0.010569 seconds | 9227465 |
Pattern 1 seems to take a lot of time. .. .. Well, that's it. There is no point in writing the calculation result, and since it will be a large number like a fool, I will write down only the processing speed after that.
| function | processing time | F(50)The value of the |
|---|---|---|
| fib() | 7997.16923 seconds | - |
| fib2() | 0.009155 seconds | - |
| fib3() | 0.010594 seconds | - |
You don't have to try pattern 1 anymore. .. .. ..
| function | processing time | F(10000)The value of the |
|---|---|---|
| fib2() | 0.376591 seconds | - |
| fib3() | 0.111379 seconds | - |
| fib5() | 0.012429 seconds | - |
| function | processing time | F(100000)The value of the |
|---|---|---|
| fib2() | 215.1977 92 seconds | - |
| fib3() | 1.23247 seconds | - |
| fib5() | 0.176561 seconds | - |
| function | processing time | F(500000)The value of the |
|---|---|---|
| fib3() | 10.064515 seconds | - |
| fib5() | 3.950023 seconds | - |
bonus ･ When n = 777777 fib5() Processing speed 9.299923
It seems that the format and comparison method may not be fair. Well, when I have to remember how to write some patterns and worry about the processing speed, I wonder which pattern is faster.
13/12/15
Yes. The measured values for a, b = b, a + b, which I received in the comments, have been added to the table in the column of fib5 ().
Recommended Posts