Last active
August 29, 2015 14:20
-
-
Save limboinf/a8ea401eca61de41e18e to your computer and use it in GitHub Desktop.
Fibonacci decorator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# -*- coding: utf-8 -*- | |
def memoize(f): | |
cache = {} | |
def helper(x): | |
if x not in cache: | |
cache[x] = f(x) | |
return cache[x] | |
return helper | |
@memoize | |
def fib(n): | |
if n in (0, 1): | |
return n | |
else: | |
return fib(n - 1) + fib(n - 2) | |
print fib(100) | |
""" | |
上面这个例子中,是一个斐波拉契数例的递归算法。我们知道,这个递归是相当没有效率的,因为会重复调用。 | |
比如:我们要计算fib(5),于是其分解成fib(4) + fib(3),而fib(4)分解成fib(3)+fib(2),fib(3)又分解成fib(2)+fib(1)…… | |
你可看到,基本上来说,fib(3), fib(2), fib(1)在整个递归过程中被调用了两次。 | |
而我们用decorator,在调用函数前查询一下缓存,如果没有才调用了,有了就从缓存中返回值。 | |
一下子,这个递归从二叉树式的递归成了线性的递归。 | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment