Re[2]: [Tutor] fibonacci
antonmuhin at rambler.ru
antonmuhin at rambler.ru" <antonmuhin@rambler.ru
Sat Feb 15 07:14:02 2003
Hello everybody,
Oneliner was really chalenging. Here some oneliners with time comparisons:
from __future__ import generators
from time import clock
import unittest
def fib0(n, x0 = 0, x1 = 1):
"""Almost classical fibs"""
for i in range(n):
x0, x1 = x1, x0 + x1
return x0
def fib1(n, x0 = 0, x1 = 1, n0 = 0):
"""Incorrect one-liner: try fib1(2, -1, 1) to see the bug
ternary operator hotly discussed now would be good for one-liners :)
"""
return ((n0 < n) and fib1(n, x1, x0 + x1, n0 + 1)) or x0
def fib1b(n, x0 = 0, x1 = 1, n0 = 0):
"""Fixed varinat of the previous one-liner"""
return (((n0 < n) and (fib1b(n, x1, x0 + x1, n0 + 1),)) or (x0,))[0]
def fib2(n, x0 = 0, x1 = 1):
"""Functional variant, too many lambdas and () though"""
return ((reduce(lambda f, g: (lambda x: f(g(x))), [lambda p: (p[1], p[0] + p[1])]*n, lambda p: p))((x0, x1)))[0]
"""Some notes:
1. lambda f, g: (lambda x: f(g(x))) --- functions' composition
2. [lambda p: (p[1], p[0] + p[1])]*n --- n of fib's steps
"""
def fib2b(n, x0 = 0, x1 = 1):
"""Another functional variant"""
return ((reduce(
lambda f, g: (lambda x, y: f(*g(x, y))),
[lambda x, y: (y, x + y)]*n,
lambda x, y: (x, y)))(x0, x1))[0]
# Technical stuff
def allFibs():
def isFib(name, obj):
return callable(obj) and name.startswith("fib")
g = globals().copy()
for name, obj in g.iteritems():
if isFib(name, obj):
yield obj
def main():
def clockFunction(f, n = 239):
t0 = clock()
for i in range(n): f(i)
return clock() - t0
print "*** Clock functions ****************"
clock()
stat = [(clockFunction(f), f.func_name) for f in allFibs()]
stat.sort()
for t, name in stat:
print "%s\t%.5f" % (name, t)
class FibsTestCase(unittest.TestCase):
def setUp(self):
self.__fibs = [obj for obj in allFibs()]
self.__paragon = fib0
self.__n = 239
def __fibTest(self, x0, x1):
for f in self.__fibs:
for i in range(self.__n):
self.assertEqual(
f(i, x0, x1), self.__paragon(i, x0, x1),
"Function %s(%d, %d, %d): oops..." % (f.func_name, i, x0, x1)
)
def testStandardFibs(self):
self.__fibTest(1, 1)
def testMoreSophisticatedFibs(self):
self.__fibTest(-1, 1)
if __name__ == "__main__":
main()
unittest.main()
--
Best regards,
anton mailto:antonmuhin@rambler.ru