函数

1 默认参数

函数的参数中如果有默认参数,那么函数在定义的时候将被计算而不是等到函数被调用的时候


In [1]:
bigx = 10
def double_times(x = bigx):
    return x * 2
bigx = 1000
double_times()


Out[1]:
20

在可变的集合类型中(list和dictionary)中,如果默认参数为该类型,那么所有的操作调用该函数的操作将会发生变化


In [4]:
def foo(values, x=[]):
    for value in values:
        x.append(value)
    return x
foo([0,1,2])


Out[4]:
[0, 1, 2]

In [5]:
foo([4,5])


Out[5]:
[0, 1, 2, 4, 5]

In [8]:
def foo_fix(values, x=[]):
    if len(x) != 0:
        x = []
    for value in values:
        x.append(value)
    return x
foo_fix([0,1,2])


Out[8]:
[0, 1, 2]

In [9]:
foo_fix([4,5])


Out[9]:
[4, 5]

2 global 参数


In [14]:
x = 5 
def set_x(y):
    x = y
    print 'inner x is {}'.format(x)
set_x(10)
print 'global x is {}'.format(x)


inner x is 10
global x is 5

x = 5 表明为global变量,但是在set_x函数内部中,出现了x,但是其为局部变量,因此全局变量x并没有发生改变。


In [16]:
def set_global_x(y):
    global x
    x = y 
    print 'global x is {}'.format(x)
set_global_x(10)
print 'global x now is {}'.format(x)


global x is 10
global x now is 10

通过添加global关键字,使得global变量x发生了改变。

3 Exercise

Fibonacci sequence

$F_{n+1}=F_{n}+F_{n-1}$ 其中 $F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2 \cdots$

  • 递归版本
    算法时间时间复杂度高达 $T(n)=n^2$

In [1]:
def fib_recursive(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)
fib_recursive(10)


Out[1]:
55
  • 迭代版本
    算法时间复杂度为$T(n)=n$

In [3]:
def fib_iterator(n):
    g = 0
    h = 1
    i = 0
    while i < n:
        h = g + h 
        g = h - g
        i += 1
    return g
fib_iterator(10)


Out[3]:
55
  • 迭代器版本
    使用 yield 关键字可以实现迭代器

In [8]:
def fib_iter(n):
    g = 0
    h = 1 
    i = 0
    while i < n:
        h = g + h
        g = h -g
        i += 1
        yield g
for value in fib_iter(10):
    print value,


1 1 2 3 5 8 13 21 34 55
  • 矩阵求解法
    $$\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}$$
    令$u_{n+1}=Au_{n}$ 其中 $u_{n+1}=\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}$ 通过矩阵的迭代求解 $u_{n+1}=A^{n}u_{0}$,其中 $u_{0}=\begin{bmatrix}1 \\0 \end{bmatrix}$,对于$A^n$ 可以通过 $(A^{n/2})^{2}$ 方式求解,使得算法时间复杂度达到 $log(n)$

In [20]:
import numpy as np
a = np.array([[1,1],[1,0]])
def pow_n(n):
    if n == 1:
        return a 
    elif n % 2 == 0:
        half = pow_n(n/2)
        return half.dot(half)
    else:
        half = pow_n((n-1)/2)
        return a.dot(half).dot(half)
def fib_pow(n):
    a_n = pow_n(n)
    u_0 = np.array([1,0])
    return a_n.dot(u_0)[1]
fib_pow(10)


Out[20]:
55

Quick Sort


In [22]:
def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        left = [item for item  in array[1:] if item < pivot]
        right = [item for item  in array[1:] if item >= pivot]
        return quick_sort(left)+[pivot]+quick_sort(right)
quick_sort([10,11,3,21,9,22])


Out[22]:
[3, 9, 10, 11, 21, 22]

In [ ]: