Re[2]: [Tutor] fibonacci

[antonmuhin at rambler.ru]

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