一、常见的内置函数

1. 查看内置函数：

>>> print(dir(__builtins__))
>>> li = dir(__builtins__)
>>> li.index('abs')     #80
>>> li[80:]
['abs', 'all', 'any', 'ascii', 'bin', 'bool', 'bytearray', 'bytes', 'callable', 'chr', 'classmethod', 'compile', 'complex', 'copyright', 'credits', 'delattr', 'dict', 'dir', 'divmod', 'enumerate', 'eval', 'exec', 'exit', 'filter', 'float', 'format', 'frozenset', 'getattr', 'globals', 'hasattr', 'hash', 'help', 'hex', 'id', 'input', 'int', 'isinstance', 'issubclass', 'iter', 'len', 'license', 'list', 'locals', 'map', 'max', 'memoryview', 'min', 'next', 'object', 'oct', 'open', 'ord', 'pow', 'print', 'property', 'quit', 'range', 'repr', 'reversed', 'round', 'set', 'setattr', 'slice', 'sorted', 'staticmethod', 'str', 'sum', 'super', 'tuple', 'type', 'vars', 'zip']
>>> len(li[80:])    #72

2. 常见函数：

len 求长度
min 求最小值
max 求最大值
sorted  排序
reversed 反向
sum  求和

>>> help(sum)   #求和一个可迭代对象，start从哪开始。
Help on built-in function sum in module builtins:
sum(iterable, start=0, /)
    Return the sum of a 'start' value (default: 0) plus an iterable of numbers
    
    When the iterable is empty, return the start value.
    This function is intended specifically for use with numeric values and may
    reject non-numeric types.
>>> sum([1,2,3,4])  10
>>> sum([1,2,3,4],10)   20

3. 进制转换函数:

4. 补充：

(1) enumerate()

  enumerate(iterable[, start]) -> iterator for index, value of iterable
  返回一个可以枚举的对象(一个元组(index, value))

>>> enumerate([1,2,3,4])        # <enumerate object at 0x00000193373611F8>
>>> list(enumerate([1,2,3,4]))          #[(0, 1), (1, 2), (2, 3), (3, 4)]
>>> list(enumerate(['a','b','c']))      #[(0, 'a'), (1, 'b'), (2, 'c')]
>>> list(enumerate(['a','b','c'],5))    #[(5, 'a'), (6, 'b'), (7, 'c')]
>>> list(enumerate({'a','b','c'},5))    #[(5, 'a'), (6, 'c'), (7, 'b')]
>>> list(enumerate({'a':1,'b':1,'c':1},5))  #[(5, 'a'), (6, 'b'), (7, 'c')]

(2) filter()

  filter(function or None, iterable) --> filter object
  过滤器 将可迭代对象经过函数的过滤再返回一个filter object
  参数(筛选函数，筛选对象)

>>> filter(lambda x:x>2,[1,2,3,4,5])    
    #<filter object at 0x0000019337348EB8>
>>> list(filter(lambda x:x>2,[1,2,3,4,5])   # [3, 4, 5]
>>> list(filter(fun,[1,2,3,4,5])    #这里只是放一个函数体
>>> list(filter(None,[1,2,3,4,5]))  #[1, 2, 3, 4, 5]

(3) map()

  <b><i>map(func, *iterables) --> map object</i></b>
  加工。
  对于参数iterable中的每个元素都应用fuction函数，并返回一个map对象

>>> map(str,[1,2,3])    #<map object at 0x0000019337348D68>
>>> list(map(str,[1,2,3]))  #['1', '2', '3']

(4) zip()

  zip(iter1 [,iter2 [...]]) --> zip object
  将对象逐一配对

>>> zip([1,2,3])    #<zip object at 0x000001933733F808>
>>> list(zip([1,2,3]))  #[(1,), (2,), (3,)]
>>> list(zip([1,2,3],[11,22,33]))   #[(1, 11), (2, 22), (3, 33)]
>>> list(zip([1,2,3],[11,22,33],'a'))   #[(1, 11, 'a')]后面两个没有配了
>>> list(zip([1,2,3],[11,22,33],'aaaaa'))   
    #[(1, 11, 'a'), (2, 22, 'a'), (3, 33, 'a')] 

  配对的参数可多不可少

二、作用域

  变量到底是什么呢？可将其视为指向值的名称。因此，执行赋值语句x=1后，名称x指向值1。这几乎与使用字典一样(字典中的键指向值)，只是你使用的是"看不见"的字典。实际上，这种解释已经离真相不远。有一个名为vars的内置函数，它返回这个不可见的字典：

>>> x = 1
>>> scope = vars()
>>> scope['x']  #1

  警告：一般而言，不应修改vars返回的字典，因为根据Python官方文档的说法，这样做的结果是不确定的。
  这种"看不见的字典"称为命名空间或作用域。在Python中，程序的变量并不是在任何位置都可以访问的，访问权限决定于这个变量是在哪里赋值的，代码中变量被赋值的位置决定哪些范围的对象可以访问这个变量，这个范围就是命名空间。
  那么有多少个命名空间呢？除全局作用域外，每个函数调用都将创建一个，函数中定义的变量等可以认为都是存储在这个命名空间中的，这些变量的调用不会影响到全局变量。

1. 局部变量与全局变量

  变量的作用域决定哪一部分程序可以访问特定的变量名称。

>>> x=1   #全局
>>> def fun1():
        y = 2 # 局部
        print(x,y)
>>> fun1()  #1 2

  全局能够进入局部变量。

>>> x = 1
>>> def foo(): x = 42
>>> foo()
>>> x   #1

  在这里，函数foo修改了变量x，但当你最终查看时，他根本没变。这是因为调用foo时创建了一个新的命名空间，供foo中的代码块使用。赋值语句x=42是在这个内部作用域(局部命名空间)中执行的，不影响外部(全局)作用域内的x。
  在函数内使用的变量只能被函数内部引用，不能再函数外引用，这个变量的作用域是局部的，也称为局部变量。
  在函数外，一段代码最开始赋值的变量可以被多个函数引用，这就是全局变量。
  全局变量可以在整个程序范围内访问。参数类似于局部变量，因此参数与全局变量同名不会有任何问题。
  函数中使用某个变量时，如果参数中的局部变量与全局变量同名，默认使用局部变量。
  如果只是想读取这种变量的值(不去重新关联它)，通常不会有任何问题。

>>> def combine(parameter): print(parameter + external)
>>> external = 'berry'
>>> combine('Shurb')    #Shrubbery

  警告：像这样访问全局变量是众多bug的根源。务必慎用全局变量。
  遮盖问题：
  如果有一个局部变量或参数与你要访问的全局变量同名，就无法直接访问全局变量，因为它被局部变量遮住了。
  例如，在前面的示例中，如果有一个名为parameter的全局变量，就无法在函数combine中访问它，因为有一个与之同名的参数。然而，必要时可使用globals()['parameter']来访问它。

>>> def combine(parameter): print(parameter + globals()['parameter'])
>>> external = 'berry'
>>> combine('Shurb')    #Shrubbery

  重新关联全局变量(使其指向新值)是另一码事。在函数内部给变量赋值时，该变量默认为局部变量，除非你明确告诉Python它是全局变量。那么如何告知呢？
  如果你想指明使用全局变量，可以使用globals()['全局变量名']，或者global 变量名。这个函数返回一个包含全局变量的字典。(locals返回一个包含局部变量的字典。)

>>> def fun2():
    a = 1
    print(a)
>>> a   #NameError: name 'a' is not defined
>>> fun2()  #1
>>> a   #NameError: name 'a' is not defined

  局部变量不能进入全局,

>>> x = 1
>>> def change_global():
        global x
        x = x + 1
>>> change_global()
>>> x   #2

  如果要进，也要global。

2. 作用域嵌套

  另外，Python是支持函数嵌套使用的,即可将一个函数放在另一个函数内，如下所示：

>>> def foo():
        def bar():
            print('hello')
        bar()

  嵌套的用处不大，但有一个很突出的用途，使用一个函数来创建另一个函数。这意味着可像下面这样编写函数：

>>> def multiplier(factor):
        def multiplyByFactor(number):
            return number * factor
        return multiplyByFactor     #返回函数体
>>> multiplier()    
    # <function multiplier.<locals>.multiplyByFactor at 0x0000019337373E18>

  在这里，一个函数位于另一个函数中，且外面的函数返回里层的函数。也就是返回一个函数体，而不是调用它。重要的是，返回的函数能够访问其定义所在的作用域。换而言之，它携带着自己所在的环境(和相关的局部变量)。
  每当外部函数被调用时，都将重新定义内部的函数，而变量factor的值也可能不同。由于Python的嵌套作用域，可在内部函数中访问这个来自外部局部作用域(multiplier)的变量，如下所示：

>>> double = multiplier(2)
>>> double(5)   #10
>>> trible = multiplier(3)
>>> trible(3)   #9
>>> multiplier(5)(4)    #20

  像multiplyByFactor这样存储其所在作用域的函数成为闭包。俩个函数 嵌套。

>>> def test1():
        a = 1
        print('局部外层')
        # test2()不能放在这里，因为函数还没有定义
        def test2():
            b = 2
            a += 1
            print('局部内层', a,b)
        test2()

  打印一行，然后报错。局部外层能进入局部里层,但是不能修改。通常，不能给外部作用域内的变量赋值。

>>> def test1():
    a = 1
    print('局部外层')
    # test2()不能放在这里，因为函数还没有定义
    def test2():
        b = 2
        nonlocal a
        a += 1
        print('局部内层', a,b)
    test2()

  但如果一定要这样做，可使用关键字nonlocal。这个关键字的用法和global很像，让你能够给外部作用域(非全局作用域)内的变量赋值。(作用于局部)。
  使用global情况：

• 全局变量可以在函数内部访问，但是不能改变
• 如果在函数内部想修改全局变量，可以用global来修饰变量
• 局部变量只能在局部进行访问修改。
• 如果在函数外部，想访问局部变量，也可以用global，将局部变量声明为全局变量

  使用nonlocal的情况：

• 当里层局部，需要修改外层局部时，需要使用nonlocal。 (如嵌套函数)

3. 回调函数

  俩个函数 不嵌套

>>> def test12():
        print('我是第一个函数')
>>> def fun12(a):
        a()
        print('我是老二')
>>> fun(test1)  
    # 我是第一个函数
    # 我是老二

  闭包加回调函数组成装饰器。

三、递归

  递归意味着引用自身，即自己调用自己。例如：

>>> def recursion():
        return recursion()

  这个函数中的递归称为无穷递归，因为它从理论上说永远不会结束。这类递归称作无穷递归，实际操作一会儿程序就崩溃了。因为每次调用函数都会用掉一点内存，当内存空间被占满，程序就会报异常。
  如果一个函数在内部调用自身，这个函数就称作递归函数。

  有用的递归函数通常包含下面两部分：

• 基线条件(针对最小的问题)：满足这种条件时函数将直接返回一个值。（这样就避免了无限调用的可能）
• 递归条件：包含一个或多个调用，这些调用旨在解决问题的一部分。

  这里的关键是，通过将问题分解为较小的部分，可避免递归没完没了，因为问题终将被分解成基线条件可以解决的最小问题。
  其实函数每次被调用时都会创建一个新命名空间，也就是当函数调用自身时，实际上运行的是两个不同的函数(也可以说一个函数具有两个不同的命名空间)。

递归的核心：

1. 递归推导式
2. 递归终止条件

1. 两个经典案例：阶乘和幂

  阶乘：当然，你可以用循环的思想来写，像下面这样

>>> def factorial(n):
    result = n
    for i in range(1,n):
        result *= i
    return result

  它是这样做的：首先将result设置为n，再将其依次乘以1到n-1的每个数字，最后返回result。关于阶乘的数学定义为：1的阶乘为1。对于大于1的数字n其阶乘为n-1的阶乘再乘以n。
这里我们换一种思路，用递归来实现：

>>> def factorial(n):
    if n == 1:      #基线条件，满足即退出函数
        return 1
    else:
        return  n * factorial(n – 1)

  我们再来定义幂的运算(就是和内置函数pow一样的效果)。幂运算的定义是power(x,n)(x的n次幂)是将数字x自乘n-1次的结果，即将n个x相乘的结果。

>>> def power(x, n):
        result = 1
        for i in range(n):
            result *= x
        return result

  递归式定义为对于任何数字x，power(x,0)都为1。n>0时，power(x,n)为power(x,n-1)与x的乘积。

>>> def power(x, n):
    if n == 0:
        return  1
    else:
        return x * power(x, n-1)

  当然，你可以明显的看到，递归大部分情况是可以用循环代替的，而且循环在时间复杂度可能更好一点，但是当你掌握了递归，你就会爱上这种简洁的表达方式。
  提示：如果函数或算法复杂难懂，在实现前用自己的话进行明确的定义将大有裨益。以这种"准编程语言"编写的程序通常称为伪代码。
  在大多数情况下，使用循环的效率可能更高。然而，在很多情况下，使用递归的可读性更高，且有时要高得多。递归函数的优点是定义简单，逻辑清晰。

>>> def fact(n):
        if n == 1:
            return 1
        return n * fact(n – 1)

  使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈(stack)这种数据结构实现的。每当进入一个函数调用，栈就会加一层栈帧；每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，因此递归调用的次数过多会导致栈溢出。

>>> fact(1000)
Traceback (most recent call last):
  File "<pyshell#15>", line 1, in <module>
    fact(1000)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#13>", line 2, in fact
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

  异常提示超过最大递归深度。
  解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果一样，把循环看成是一种特殊尾递归函数也可以。
  尾递归是指在函数返回时调用函数本身，并且return语句不能包含表达式。这样，编译器或解释器就可以对尾递归进行优化，使递归本身无论调用多少次都只占用一个栈帧，从而避免栈溢出的情况。

>>> def fact(n):
        return fact_iter(n,1)
>>> def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

  可以看到，return fact_iter(num - 1, num * product)仅返回递归函数本身， num - 1和num * product在函数调用前就会被计算，不影响函数调用。
  由操作结果看到，调用尾递归时如果做了优化，栈就不会增长，因此无论多少次调用都不会导致栈溢出。

2. 另一个经典案例：二分查找

  例如，对方心里想着一个1-100的数字，你必须猜出是哪个。实际上只需要猜7次。首先问：这个数字大于50吗？如果答案是肯定的，再问：这个数字大于75吗？不断将可能的区间减半，知道猜对为止。你无需过多地思考就能成功。
  这里的关键是，这种算法自然而然地引出了递归式定义和实现。先来回顾一下定义，确保知道该如何做。

• 如果上限和下限相同，就说明它们都指向数字所在的位置，因此将这个数字返回。
• 否则，找出区间的中间位置(上限和下限的平均值)，再确定数字在左半部分还是有半部分。然后继续在数字所在的那部分中查找。

  在这个递归案例中，关键在于元素是经过排序的。找出中间的元素后，只需将其与要查找的数字进行比较即可。如果要查找的数字更大，肯定在右边；如果更小，它必然在左边。递归部分为"继续在数字所在的那部分中查找"，因为查找方式与定义所指定的完全相同。(请注意，这种查找算法返回数字应该在的位置。如果这个数字不在序列中，那么这个位置上的自然是另一个数字。)
  现在可以实现二分查找了。

>>> def search(sequence, number, lower=0, upper=None):
    if upper is None: upper = len(sequence) - 1
    if lower == upper:
        assert number == sequence[upper]
        return upper
    else:
        middle = (lower + upper) // 2
        if number > sequence[middle]:
            return search(sequence, number, middle + 1, upper)
        else:
            return search(sequence, number, lower, middle)

  提示：实际上，模块bisect提供了标准的二分查找实现。

3. 函数式编程

  在Python中，通常不会如此倚重函数(而是创建自定义对象，这将在下一章详细介绍)，但完全可以这样做。
  Python提供了一些有助于这种函数式编程的函数：map、filter和reduce。在较新的Python版本中，函数map和filter的用途并不大，应该使用列表推导来替代它们。你可使用map将序列的所有元素传递给函数。

>>> list(map(str, range(10)))   #与[str(i)for i in range(10)]等价
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

  你可使用filter根据布尔函数的返回值对元素进行过滤。

>>> def func(x):
        return x.isalnum()
>>> seq = ["foo", "x41", "?!", "***"]
>>> list(filter(func, seq)) #['foo', 'x41']

  就这个示例而言，如果转而使用列表推导，就无需创建前述自定义函数。

>>> [x for x in seq if x.isalnum()] #['foo', 'x41']

  实际上，Python提供了一种名为lambda表达式的功能，让你能够创建内嵌的简单函数(主要供map、filter和reduce使用)

>>> filter(lambda x: x.isalnum(), seq)  #['foo', 'x41']

  然而，使用列表推导的可读性不是更高吗？
  要使用列表推导来替换函数reduce不那么容易，而这个函数提供的功能即便能用到，也用的不多。它使用指定的函数将序列的前两个元素合二为一，再将结果与第3个元素合二为一，以此类推，直到处理完整个序列并得到一个结果。例如，如果你要将序列中的所有数相加，可结合使用reduce和lambda x,y:x+y。

>>> numbers = [1,2,3,4]
>>> from functools import reduce
>>> reduce(lambda x,y: x+y,numbers) #10

  就这个示例而言，还不如使用内置函数sum。

四、匿名函数

  匿名函数就是不再使用def语句这样的标准形式定义一个函数。
  Python使用lambda创建匿名函数。lambda只是表达式，函数体比def简单很多。
  lambda的主体是一个表达式，而不是一个代码块，仅能在lambda表达式中封装优先的逻辑。  lambda函数拥有自己的命名空间，不能访问自有参数列表之外或全局命名空间的参数。
  lambda函数的语法只包含一个语句：lambda [args1[,args2,…argn]]:expression
  看一个求两个数和的示例。

>>> def func(x,y):
        return x+y
>>> lambda x,y:x+y

  可以看出，使用lambda表达编写的代码比使用def语句少。
  比如求一个列表中大于3的元素，通过函数式编程实现，运用filter。

>>> def func(x):
        return x>3
>>> f_list = filter(func,[1,2,3,4,5])
>>> print([item for item in f_list])

  如果使用匿名函数，

>>> print([item for item in filter(lambda x:x>3,[1,2,3,4,5])

  从上面的操作可以看出，lambda一般应用于函数式编程，代码简介，常和filter等函数结合使用。
  我们对lambda进行解析。在表达式中
  x为lambda函数的一个参数，:为分割符，x>3为返回值，item for item in filter是filter函数的取值方式。

一般情况多考虑使用匿名函数：

• 程序一次性使用、不需要定义函数名时，用匿名函数可以节省内存中变量定义空间。
• 如果想让程序更加简洁，使用匿名函数就可以做到。

匿名函数有3个规则要记住：

1. 一般有一行表达式，必须有返回值
2. 不能有return
3. 可以没有参数，也可以有一个或多个参数

  下面来看几个匿名函数的示例。
无参匿名函数：

>>> t = lambda :True
>>> t()     #True

带参数匿名函数

>>> lambda x : x**3
>>> lambda x,y,z : x+y+z
>>> lambda x,y=3 : x*y

匿名函数调用：

>>> c = lambda x,y,z : x*y*z    
>>> c(2,3,4)    #24

五、偏函数

  偏函数通过模块functools被用户调用。
  偏函数是将所要承载的函数作为partial()函数的第一个参数，原函数的各个参数一次作为partial()函数的后续参数，除非使用关键字参数。
  在这个例子里，将实现一个取余函数，取得整数100对不同数m的100%m的余数。

>>> from functools import partial
>>> def mod(n,m):
        return n%m
>>> mod_by_100 = partial(mod,100)
>>> print(mod(100,7)    #2
>>> print(mod_by_100(7))    #2

  由执行结果看到，使用偏函数所需代码量比自定义函数更少、更简洁。

六、快速排序

  快速排序是一种分治排序算法。该算法首先选取一个划分元素(pivot)；然后重排列表，将其划分为3个部分，即left(小于划分元素pivot的部分)，pivot、right(大于划分元素pivot的部分)，此时划分元素pivot已经在列表的最终位置上；最后分别对left和right两部分进行递归排序。
  其中，划分元素的选取直接影响快速排序算法的效率，通常选择列表的第一个元素、中间元素或最后一个元素作为划分元素，当然也有更复杂的选择方式。划分过程根据划分元素重排列表，是快速排序算法的关键所在。
  快速排序算法的优点是原位排序(只使用很小的辅助栈)，平均时间复杂度为O(n log n)。快速排序算法的缺点是不稳定，最坏情况下时间复杂度为O(n2)

>>> def quicksort(L):
    qsort(L, 0, len(L) - 1)

>>> def qsort(L, first, last):
    if first < last:
        split = partition(L, first, last)
        qsort(L, first, split - 1)
        qsort(L, split + 1, last)

>>> def partition(L, first, last):
    # 选取列表中的第一个元素作为划分元素
    pivot = L[first]
    leftmark = first + 1
    rightmark = last
    while True:
        while L[leftmark] <= pivot:
            # 如果列表中存在与划分元素相等的元素，让它位于left部分
            # 以下检测用于划分元素pivot是列表中的最大元素时
            # 放置leftmark越界
            if leftmark == rightmark:
                break
            leftmark += 1
            while L[rightmark] > pivot:
                # 这里不需要检测，划分元素pivot是列表中的最小元素时
                # rightmark自动停在first处
                rightmark -= 1
            if leftmark < rightmark:
                # 此时，leftmark处的元素大于pivot
                # rightmark处的元素小于等于pivot，交换两者
                L[leftmark], L[rightmark] = L[rightmark], L[leftmark]
            else:
                break
        # 交换first处的划分元素与rightmark处的元素
        L[first], L[rightmark] = L[rightmark], L[first]
        # 返回划分元素pivot的最终位置
        return rightmark
>>> num_list = [5,-4,6,3,7,11,1,2]
>>> quicksort(num_list)
>>> print(num_list)     #[-4, 1, 2, 3, 5, 7, 6, 11]