Python基础教程：Day16-20：语言进阶
Python语言进阶
数据结构和算法
算法：解决问题的方法和步骤
评价算法的好坏：渐近时间复杂度和渐近空间复杂度。
渐近时间复杂度的大O标记：
排序算法（选择、冒泡和归并）和查找算法（顺序和折半）
使用生成式（推导式）语法
嵌套的列表
Python Tutor - VISUALIZE CODE AND GET LIVE HELP
heapq、itertools等的用法
collections模块下的工具类
常用算法：
穷举法 - 又称为暴力破解法，对所有的可能性进行验证，直到找到正确答案。
贪婪法 - 在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。
分治法 - 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到可以直接求解的程度，最后将子问题的解进行合并得到原问题的解。
回溯法 - 回溯法又称为试探法，按选优条件向前搜索，当搜索到某一步发现原先选择并不优或达不到目标时，就退回一步重新选择。
动态规划 - 基本思想也是将待求解问题分解成若干个子问题，先求解并保存这些子问题的解，避免产生大量的重复运算。
穷举法例子：百钱百鸡和五人分鱼。
贪婪法例子：假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。
| 名称 | 价格（美元） | 重量（kg） |
|---|---|---|
| 电脑 | 200 | 20 |
| 收音机 | 20 | 4 |
| 钟 | 175 | 10 |
| 花瓶 | 50 | 2 |
| 书 | 10 | 1 |
| 油画 | 90 | 9 |
分治法例子：快速排序。
回溯法例子：骑士巡逻。
递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。
动态规划例子1：斐波拉切数列。（不使用动态规划将会是几何级数复杂度）
动态规划例子2：子列表元素之和的最大值。（使用动态规划可以避免二重循环）
说明：子列表指的是列表中索引（下标）连续的元素构成的列表；列表中的元素是int类型，可能包含正整数、0、负整数；程序输入列表中的元素，输出子列表元素求和的最大值，例如：
输入：1 -2 3 5 -3 2
输出：8
输入：0 -2 3 5 -1 2
输出：9
输入：-9 -2 -3 -5 -3
输出：-2
函数的使用方式
将函数视为“一等公民”
函数可以赋值给变量
函数可以作为函数的参数
函数可以作为函数的返回值
高阶函数的用法（
filter、map以及它们的替代品）items1 = list(map(lambda x: x ** 2, filter(lambda x: x % 2, range(1, 10)))) items2 = [x ** 2 for x in range(1, 10) if x % 2]
位置参数、可变参数、关键字参数、命名关键字参数
参数的元信息（代码可读性问题）
匿名函数和内联函数的用法（
lambda函数）闭包和作用域问题
Python搜索变量的LEGB顺序（Local --> Embedded --> Global --> Built-in）
global和nonlocal关键字的作用global：声明或定义全局变量（要么直接使用现有的全局作用域的变量，要么定义一个变量放到全局作用域）。nonlocal：声明使用嵌套作用域的变量（嵌套作用域必须存在该变量，否则报错）。装饰器函数（使用装饰器和取消装饰器）
例子：输出函数执行时间的装饰器。
如果装饰器不希望跟print函数耦合，可以编写带参数的装饰器。
说明：由于对带装饰功能的函数添加了@wraps装饰器，可以通过
func.__wrapped__方式获得被装饰之前的函数或类来取消装饰器的作用。
例子：用装饰器来实现单例模式。
说明：上面的代码中用到了闭包（closure），不知道你是否已经意识到了。还没有一个小问题就是，上面的代码并没有实现线程安全的单例，如果要实现线程安全的单例应该怎么做呢？
面向对象相关知识
三大支柱：封装、继承、多态
例子：工资结算系统。
类与类之间的关系
is-a关系：继承
has-a关系：关联 / 聚合 / 合成
use-a关系：依赖
例子：扑克游戏。
对象的复制（深复制/深拷贝/深度克隆和浅复制/浅拷贝/影子克隆）
垃圾回收、循环引用和弱引用
Python使用了自动化内存管理，这种管理机制以引用计数为基础，同时也引入了标记-清除和分代收集两种机制为辅的策略。
导致引用计数+1的情况：
对象被创建，例如
a = 23对象被引用，例如
b = a对象被作为参数，传入到一个函数中，例如
f(a)对象作为一个元素，存储在容器中，例如
list1 = [a, a]
导致引用计数-1的情况：
对象的别名被显式销毁，例如
del a对象的别名被赋予新的对象，例如
a = 24一个对象离开它的作用域，例如f函数执行完毕时，f函数中的局部变量（全局变量不会）
对象所在的容器被销毁，或从容器中删除对象
引用计数可能会导致循环引用问题，而循环引用会导致内存泄露，如下面的代码所示。为了解决这个问题，Python中引入了“标记-清除”和“分代收集”。在创建一个对象的时候，对象被放在第一代中，如果在第一代的垃圾检查中对象存活了下来，该对象就会被放到第二代中，同理在第二代的垃圾检查中对象存活下来，该对象就会被放到第三代中。
以下情况会导致垃圾回收：
如果循环引用中两个对象都定义了
__del__方法，gc模块不会销毁这些不可达对象，因为gc模块不知道应该先调用哪个对象的__del__方法，这个问题在Python 3.6中得到了解决。也可以通过
weakref模块构造弱引用的方式来解决循环引用的问题。调用
gc.collect()gc模块的计数器达到阀值
程序退出
魔法属性和方法（请参考《Python魔法方法指南》）
有几个小问题请大家思考：
自定义的对象能不能使用运算符做运算？
自定义的对象能不能放到set中？能去重吗？
自定义的对象能不能作为dict的键？
自定义的对象能不能使用上下文语法？
混入（Mixin）
例子：自定义字典限制只有在指定的key不存在时才能在字典中设置键值对。
元编程和元类
例子：用元类实现单例模式。
面向对象设计原则
说明：上面加粗的字母放在一起称为面向对象的SOLID原则。
单一职责原则 （SRP）- 一个类只做该做的事情（类的设计要高内聚）
开闭原则 （OCP）- 软件实体应该对扩展开发对修改关闭
依赖倒转原则（DIP）- 面向抽象编程（在弱类型语言中已经被弱化）
里氏替换原则（LSP） - 任何时候可以用子类对象替换掉父类对象
接口隔离原则（ISP）- 接口要小而专不要大而全（Python中没有接口的概念）
合成聚合复用原则（CARP） - 优先使用强关联关系而不是继承关系复用代码
最少知识原则（迪米特法则，LoD）- 不要给没有必然联系的对象发消息
例子：可插拔的哈希算法。
创建型模式：单例、工厂、建造者、原型
结构型模式：适配器、门面（外观）、代理
行为型模式：迭代器、观察者、状态、策略
例子：可插拔的哈希算法。
GoF设计模式
迭代器和生成器
和迭代器相关的魔术方法（
__iter__和__next__）两种创建生成器的方式（生成器表达式和
yield关键字）
并发编程
Python中实现并发编程的三种方案：多线程、多进程和异步I/O。并发编程的好处在于可以提升程序的执行效率以及改善用户体验；坏处在于并发的程序不容易开发和调试，同时对其他程序来说它并不友好。
多线程：Python中提供了Thread类并辅以Lock、Condition、Event、Semaphore和Barrier。Python中有GIL来防止多个线程同时执行本地字节码，这个锁对于CPython是必须的，因为CPython的内存管理并不是线程安全的，因为GIL的存在多线程并不能发挥CPU的多核特性。
多个线程竞争资源的情况
修改上面的程序，启动5个线程向账户中存钱，5个线程从账户中取钱，取钱时如果余额不足就暂停线程进行等待。为了达到上述目标，需要对存钱和取钱的线程进行调度，在余额不足时取钱的线程暂停并释放锁，而存钱的线程将钱存入后要通知取钱的线程，使其从暂停状态被唤醒。可以使用threading模块的Condition来实现线程调度，该对象也是基于锁来创建的，代码如下所示：
多进程：多进程可以有效的解决GIL的问题，实现多进程主要的类是Process，其他辅助的类跟threading模块中的类似，进程间共享数据可以使用管道、套接字等，在multiprocessing模块中有一个Queue类，它基于管道和锁机制提供了多个进程共享的队列。下面是官方文档上关于多进程和进程池的一个示例。
说明：多线程和多进程的比较。
以下情况需要使用多线程：
以下情况需要使用多进程：
程序执行计算密集型任务（如：字节码操作、数据处理、科学计算）。
程序的输入可以并行的分成块，并且可以将运算结果合并。
程序在内存使用方面没有任何限制且不强依赖于I/O操作（如：读写文件、套接字等）。
程序需要维护许多共享的状态（尤其是可变状态），Python中的列表、字典、集合都是线程安全的，所以使用线程而不是进程维护共享状态的代价相对较小。
程序会花费大量时间在I/O操作上，没有太多并行计算的需求且不需占用太多的内存。
异步处理：从调度程序的任务队列中挑选任务，该调度程序以交叉的形式执行这些任务，我们并不能保证任务将以某种顺序去执行，因为执行顺序取决于队列中的一项任务是否愿意将CPU处理时间让位给另一项任务。异步任务通常通过多任务协作处理的方式来实现，由于执行时间和顺序的不确定，因此需要通过回调式编程或者
future对象来获取任务执行的结果。Python 3通过asyncio模块和await和async关键字（在Python 3.7中正式被列为关键字）来支持异步处理。
Python中有一个名为aiohttp的三方库，它提供了异步的HTTP客户端和服务器，这个三方库可以跟asyncio模块一起工作，并提供了对Future对象的支持。Python 3.6中引入了async和await来定义异步执行的函数以及创建异步上下文，在Python 3.7中它们正式成为了关键字。下面的代码异步的从5个URL中获取页面并通过正则表达式的命名捕获组提取了网站的标题。
说明：异步I/O与多进程的比较。
当程序不需要真正的并发性或并行性，而是更多的依赖于异步处理和回调时，asyncio就是一种很好的选择。如果程序中有大量的等待与休眠时，也应该考虑asyncio，它很适合编写没有实时数据处理需求的Web应用服务器。
Python还有很多用于处理并行任务的三方库，例如：joblib、PyMP等。实际开发中，要提升系统的可扩展性和并发性通常有垂直扩展（增加单个节点的处理能力）和水平扩展（将单个节点变成多个节点）两种做法。可以通过消息队列来实现应用程序的解耦合，消息队列相当于是多线程同步队列的扩展版本，不同机器上的应用程序相当于就是线程，而共享的分布式消息队列就是原来程序中的Queue。消息队列（面向消息的中间件）的最流行和最标准化的实现是AMQP（高级消息队列协议），AMQP源于金融行业，提供了排队、路由、可靠传输、安全等功能，最著名的实现包括：Apache的ActiveMQ、RabbitMQ等。
要实现任务的异步化，可以使用名为Celery的三方库。Celery是Python编写的分布式任务队列，它使用分布式消息进行工作，可以基于RabbitMQ或Redis来作为后端的消息代理。
