Python 部分知识点总结（五）

一、高价函数和柯里化

1. First Class Object
           函数在 Python 中是一等公民
           函数也是对象，可调用的对象
           函数可以作为普通变量、参数、返回值等
2. 高阶函数
           数学概念 y=g(f(x))
           在数学和计算机科学中，高阶函数应该是至少满足下面一个条件的函数：
               接受一个或多个函数作为参数
               输出一个函数
3. sorted(iterable[,key][,reverse])
         返回一个新的列表，对一个可迭代对象的所有元素排序，排序规则为 key 定义的函数，reverse 表示是否排序翻转，sorted() 返回新列表，list.sort() 就地修改
4. filter(function,iterable) –> filter object
         过滤可迭代对象的元素，返回一个迭代器
         function 一个具有一个参数的函数，返回 bool
         >>> list(filter(lambda x:x%3==0,[1,9,55,150,-3,78,28,123]))   –>  [9, 150, -3, 78, 123]
5. map(func,*iterables)   –> map object
         对多个可迭代对象的元素按照指定的函数进行映射，返回一个迭代器
         >>> list(map(lambda x:2*x+1,range(5)))           –>  [1, 3, 5, 7, 9]
         >>> dict(map(lambda x:(x%5,x),range(500)))    –>  {0: 495, 1: 496, 2: 497, 3: 498, 4: 499}
6. 柯里化：指的是将原来接受两个参数的函数编程新的接受一个参数的函数的过程，新的函数返回一个以原有第二个参数的函数，z = f(x,y) 转换成 z = f(x)(y) 的形式，通过嵌套函数就可以把函数转换成柯里函数

二、装饰器

1. 最简单的用法
   def logger(fn):
       def wrapper(*args,**kwargs):
           print(‘BEGIN’)
           x = fn(*args,**kwargs)
           print(‘END’)
           return x
       return wrapper
   @logger
   def add(x,y):
       return x+y
   add(100,2)
2. 装饰器（无参）
            它是一个函数
            函数作为它的形参
            返回值也是一个函数
            可以使用 @functionname 方法，简化使用
3. 装饰器是高阶函数，但装饰器是对传入函数的功能的装饰（功能增强）
4. 文档字符串
           Python 是文档字符串 Documetation Strings
           在函数语句块的第一行，且习惯是多行的文本，所以多使用三引号
           惯例是首字母大写，第一行写概述，空一行，第三行写详细描述
           可以使用特殊属性 __doc__ 访问这个文档
5. 带参装饰器
            它是一个函数
            函数作为它的形参
            返回值是一个不带参的装饰器函数
            使用 @functionname(参数列表)  方式调用
            可以看做在装饰器外层又加了一层函数
6. functools.update_wrapper(wrapper,wrapped,assigned=WRAPPER_ASSIGNMENTS,updated=WRAPPER_UPDATES)
             类似 copy_properties 功能
             wrapper 包装函数、被更新者，wrapped 被包装函数、数据源
             元组 WRAPPER_ASSIGNMENTS 中是要被覆盖的属性：’__module__’（模块名）、’__name__’（名称）、’__qualname__’（限定名）、’__doc__’（文档）、’__annotations__’（参数注解）
             元组 WRAPPER_UPDATES 中是要被更新的属性，__dict__ 属性字典
             增加一个 __wrapped__ 属性，保留着 wrapped 函数
             使用的时候只需要加上一句：import functools   functools.update_wrapper(wrapper,fn)
7. @functools.wraps(wrapped,assigned=WRAPPER_ASSIGNMENTS,updated=WRAPPER_UPDATES)
                类似 copy_properties 功能
                wrapped 被包装函数
                元组 WRAPPER_ASSIGNMENTS 中是要被覆盖的属性：’__module__’（模块名）、’__name__’（名称）、’__qualname__’（限定名）、’__doc__’（文档）、’__annotations__’（参数注解）
                元组 WRAPPER_UPDATES 中是要被更新的属性，__dict__ 属性字典
                增加一个 __wrapped__ 属性，保留着 wrapped 函数
                使用的时候只需要加一句：import functools   @functools.wraps(fn)
8. partial 方法
             偏函数，把函数部分的参数固定下来，相当于为部分的参数添加了一个固定的默认值，形成一个新的函数并返回
             从 partial 生成的新函数，是对原函数的封装
   def partial(func,*args,**keywords):
       def newfunc(*fargs,**fkeywords):
           newkeywords = keywords.copy()
           newkeywords.update(fkeywords)  # 如果有关键字参数，就更新值
           return func(*(args + fargs),**newkeywords)  # 如果全是位置参数，就在后面追加
       newfunc.func = func  # 保留原函数
       newfunc.args = args  # 保留原函数的位置参数
       newfunc.keywords = keywords  # 保留原函数的关键字参数
       return newfunc
9. @functools.lru_cache(maxsize=128,typed=False)
              Least-recently-used 装饰器，lru 即最近最少使用，cache 缓存
              如果 maxsize 设置为 None，则禁用 LRU 功能，并且缓存可以无限制增长，当 maxsize 是 2 的幂时，LRU 功能执行的最好
              如果 typed 设置为 True，则不同类型的函数参数将单独缓存，如 f(3) 和 f(3.0)  将被视为具有不同结果的不同调用
              使用方法：import functols    @functools.lru_cache()
              通过一个字典缓存被装饰函数的调用和返回值
             lru_cache 装饰器应用
                   使用前提：同样的函数参数一定得到同样的结果；函数执行时间很长，且要多次执行
                   缺点：不支持缓存过期，key 无法过期、失效；不支持清除操作；不支持分布式，是一个单机的缓存
                   适用场景：单机上需要空间换时间的地方，可以用缓存来将计算变成快速的查询

三、参数注解

1. 函数定义的弊端
            Python 是动态语言，变量随时可以被赋值，且能赋值为不同的类型
            Python 不是静态编译型语言，变量类型是运行器决定的
2. 解决动态语言定义的弊端：增加文档 Documentation String
            这只是一个惯例，不是强制标准，不能要求程序员一定为函数提供说明文档
            函数定义更新了，文档未必同步更新
3. 解决动态语言定义的弊端：函数注解
           def add(x:int,y:int) -> int:
               ”’
               :param x:int
               :param y:int
               :return:int
               ”’
               return x + y
           add(4,5)                –>  9
           add(‘mag’,’edu’)   –> ‘magedu’
4. 函数注解
            Python 3.5 引入
            对函数的返回值进行类型注解
            对函数的返回值进行类型注解
            只对函数参数做第一个辅助的说明，并不对函数参数进行类型检查
            提供给第三方工具，做代码分析，发现隐藏的 bug
            函数注解的信息，保存在 __annotations__ 属性中
            add.__annotations__   –> {‘return’: str, ‘x’: int, ‘y’: str}
5. inspet 模块：提供获取对象信息的函数，可以检查函数和类、类型检查
            inspect.isfunction(add)，是否是函数
            inspect.ismethod(add)，是否是类的方法
            inspect.isgenerator(add)，是否是生成器对象
            inspect.isgeneratorfunction(add)，是否是生成器函数
            inspect.isclass(add)，是否是类
            inspect.ismodule(add)，是否是模块
            inspect.isbuiltin(add)，是否是内建对象
            signature：获取签名（函数签名包含了一个函数的信息，包括函数名、它的参数新类型、它所在的类型和名称空间及其他信息）
6. Parameter 对象
             保存在元组中，是只读的
             name，参数的名字
             annotation，参数的注解，可能没有定义
             default，参数的缺省值，可能没有定义
             empty，特殊的类，用来标记 default 属性或者注释 annotation 属性的空值
             kind，实参如何绑定到形参，就是形参的类型
                   POSITIONAL_ONLY，值必须是位置参数提供
                   POSITIONLY_OR_KEYWORD，值可以作为关键字或者位置参数提供
                   VAR_POSITIONLY，可变位置参数，对应 *args
                   KEYWORD_ONLY，keyword-only参数，对应 *  或者 *args 之后的出现的非可变关键字参数
                   VAR_KEYWORD，可变关键字参数，对应 **kwargs

四、堆排序

1. 堆（Heap）
            堆是一个完全二叉树
            每个非叶子结点都要大于或者等于其左右孩子结点的值称为 大顶堆
            每个非叶子结点都要小于或者等于其左右孩子结点的值称为 小顶堆
            根结点一定是大顶堆中的最大值，一定是小顶堆中的最小值
2. 构建大顶堆的核心算法
            度数为 2 的结点 A，如果它的左右孩子结点的最大值比它大，将这个最大值和该结点交换
            度数为 1 的结点 A，如果它的左孩子的值大于它，则交换
            如果结点 A 被交换到新的位置，还需要和其孩子结点重复上面的过程
3. 构建大顶堆的起点结点选择
            从完全二叉树的最后一个结点的双亲结点开始，即最后一层的最右边叶子结点的父结点开始
            结点数为 n，则起始结点的编号为 n//2
        构建大顶堆的下一个结点的选择
           从起始结点开始向左找其同层结点，到头后再从上一层的最右边结点开始继续向左逐个查找，直至根结点
        排序
           将大顶堆根结点这个最大值和最后一个叶子结点交换，那么最后一个叶子结点就是最大值，将这个叶子结点盘排除在待排序结点之外，然后从新的根结点开始，重新调整为大顶堆后，重复上一步
4. 总结
           是利用堆性质的一种选择排序，在堆顶选出最大值或者最小值
           由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏，平均时间复杂度为 O(nlogn)
           只是使用了一个交换用的空间，空间复杂度为 O(1)
           不稳定的排序算法