KLucenの启示录

重要知识点#

• 生成式（推导式）的用法

  1
  prices = {
  2
      'AAPL': 191.88,
  3
      'GOOG': 1186.96,
  4
      'IBM': 149.24,
  5
      'ORCL': 48.44,
  6
      'ACN': 166.89,
  7
      'FB': 208.09,
  8
      'SYMC': 21.29
  9
  }
  10
  # 用股票价格大于100元的股票构造一个新的字典
  11
  prices2 = {key: value for key, value in prices.items() if value > 100}
  12
  print(prices2)

  说明：生成式（推导式）可以用来生成列表、集合和字典。

• 嵌套的列表的坑

  1
  names = ['关羽', '张飞', '赵云', '马超', '黄忠']
  2
  courses = ['语文', '数学', '英语']
  3
  # 录入五个学生三门课程的成绩
  4
  # 错误 - 参考http://pythontutor.com/visualize.html#mode=edit
  5
  # scores = [[None] * len(courses)] * len(names)
  6
  scores = [[None] * len(courses) for _ in range(len(names))]
  7
  for row, name in enumerate(names):
  8
      for col, course in enumerate(courses):
  9
          scores[row][col] = float(input(f'请输入{name}的{course}成绩: '))
  10
          print(scores)

  Python Tutor - VISUALIZE CODE AND GET LIVE HELP

• heapq模块（堆排序）

  1
  """
  2
  从列表中找出最大的或最小的N个元素
  3
  堆结构(大根堆/小根堆)
  4
  """
  5
  import heapq
  6
  
  7
  list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
  8
  list2 = [
  9
      {'name': 'IBM', 'shares': 100, 'price': 91.1},
  10
      {'name': 'AAPL', 'shares': 50, 'price': 543.22},
  11
      {'name': 'FB', 'shares': 200, 'price': 21.09},
  12
      {'name': 'HPQ', 'shares': 35, 'price': 31.75},
  13
      {'name': 'YHOO', 'shares': 45, 'price': 16.35},
  14
      {'name': 'ACME', 'shares': 75, 'price': 115.65}
  15
  ]
  16
  print(heapq.nlargest(3, list1))
  17
  print(heapq.nsmallest(3, list1))
  18
  print(heapq.nlargest(2, list2, key=lambda x: x['price']))
  19
  print(heapq.nlargest(2, list2, key=lambda x: x['shares']))

• itertools模块

  1
  """
  2
  迭代工具模块
  3
  """
  4
  import itertools
  5
  
  6
  # 产生ABCD的全排列
  7
  itertools.permutations('ABCD')
  8
  # 产生ABCDE的五选三组合
  9
  itertools.combinations('ABCDE', 3)
  10
  # 产生ABCD和123的笛卡尔积
  11
  itertools.product('ABCD', '123')
  12
  # 产生ABC的无限循环序列
  13
  itertools.cycle(('A', 'B', 'C'))

• collections模块

  常用的工具类：

  • namedtuple：命令元组，它是一个类工厂，接受类型的名称和属性列表来创建一个类。
  • deque：双端队列，是列表的替代实现。Python中的列表底层是基于数组来实现的，而deque底层是双向链表，因此当你需要在头尾添加和删除元素时，deque会表现出更好的性能，渐近时间复杂度为$O(1)$。
  • Counter：dict的子类，键是元素，值是元素的计数，它的most_common()方法可以帮助我们获取出现频率最高的元素。Counter和dict的继承关系我认为是值得商榷的，按照CARP原则，Counter跟dict的关系应该设计为关联关系更为合理。
  • OrderedDict：dict的子类，它记录了键值对插入的顺序，看起来既有字典的行为，也有链表的行为。
  • defaultdict：类似于字典类型，但是可以通过默认的工厂函数来获得键对应的默认值，相比字典中的setdefault()方法，这种做法更加高效。

  1
  """
  2
  找出序列中出现次数最多的元素
  3
  """
  4
  from collections import Counter
  5
  
  6
  words = [
  7
      'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
  8
      'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around',
  9
      'the', 'eyes', "don't", 'look', 'around', 'the', 'eyes',
  10
      'look', 'into', 'my', 'eyes', "you're", 'under'
  11
  ]
  12
  counter = Counter(words)
  13
  print(counter.most_common(3))

数据结构和算法#

• 算法：解决问题的方法和步骤

• 评价算法的好坏：渐近时间复杂度和渐近空间复杂度。

• 渐近时间复杂度的大O标记：

  • - 常量时间复杂度 - 布隆过滤器 / 哈希存储
  • - 对数时间复杂度 - 折半查找（二分查找）
  • - 线性时间复杂度 - 顺序查找 / 计数排序
  • - 对数线性时间复杂度 - 高级排序算法（归并排序、快速排序）
  • - 平方时间复杂度 - 简单排序算法（选择排序、插入排序、冒泡排序）
  • - 立方时间复杂度 - Floyd算法 / 矩阵乘法运算
  • - 几何级数时间复杂度 - 汉诺塔
  • - 阶乘时间复杂度 - 旅行经销商问题 - NPC
  

• 排序算法（选择、冒泡和归并）和查找算法（顺序和折半）

  1
  def select_sort(items, comp=lambda x, y: x < y):
  2
      """简单选择排序"""
  3
      items = items[:]
  4
      for i in range(len(items) - 1):
  5
          min_index = i
  6
          for j in range(i + 1, len(items)):
  7
              if comp(items[j], items[min_index]):
  8
                  min_index = j
  9
          items[i], items[min_index] = items[min_index], items[i]
  10
      return items

  1
  def bubble_sort(items, comp=lambda x, y: x > y):
  2
      """冒泡排序"""
  3
      items = items[:]
  4
      for i in range(len(items) - 1):
  5
          swapped = False
  6
          for j in range(len(items) - 1 - i):
  7
              if comp(items[j], items[j + 1]):
  8
                  items[j], items[j + 1] = items[j + 1], items[j]
  9
                  swapped = True
  10
          if not swapped:
  11
              break
  12
      return items

  1
  def bubble_sort(items, comp=lambda x, y: x > y):
  2
      """搅拌排序(冒泡排序升级版)"""
  3
      items = items[:]
  4
      for i in range(len(items) - 1):
  5
          swapped = False
  6
          for j in range(len(items) - 1 - i):
  7
              if comp(items[j], items[j + 1]):
  8
                  items[j], items[j + 1] = items[j + 1], items[j]
  9
                  swapped = True
  10
          if swapped:
  11
              swapped = False
  12
              for j in range(len(items) - 2 - i, i, -1):
  13
                  if comp(items[j - 1], items[j]):
  14
                      items[j], items[j - 1] = items[j - 1], items[j]
  15
                      swapped = True
  16
          if not swapped:
  17
              break
  18
      return items

  1
  def merge(items1, items2, comp=lambda x, y: x < y):
  2
      """合并(将两个有序的列表合并成一个有序的列表)"""
  3
      items = []
  4
      index1, index2 = 0, 0
  5
      while index1 < len(items1) and index2 < len(items2):
  6
          if comp(items1[index1], items2[index2]):
  7
              items.append(items1[index1])
  8
              index1 += 1
  9
          else:
  10
              items.append(items2[index2])
  11
              index2 += 1
  12
      items += items1[index1:]
  13
      items += items2[index2:]
  14
      return items
  15
  
  16
  
  17
  def merge_sort(items, comp=lambda x, y: x < y):
  18
      return _merge_sort(list(items), comp)
  19
  
  20
  
  21
  def _merge_sort(items, comp):
  22
      """归并排序"""
  23
      if len(items) < 2:
  24
          return items
  25
      mid = len(items) // 2
  26
      left = _merge_sort(items[:mid], comp)
  27
      right = _merge_sort(items[mid:], comp)
  28
      return merge(left, right, comp)

  1
  def seq_search(items, key):
  2
      """顺序查找"""
  3
      for index, item in enumerate(items):
  4
          if item == key:
  5
              return index
  6
      return -1

  1
  def bin_search(items, key):
  2
      """折半查找"""
  3
      start, end = 0, len(items) - 1
  4
      while start <= end:
  5
          mid = (start + end) // 2
  6
          if key > items[mid]:
  7
              start = mid + 1
  8
          elif key < items[mid]:
  9
              end = mid - 1
  10
          else:
  11
              return mid
  12
      return -1

• 常用算法：

  • 穷举法 - 又称为暴力破解法，对所有的可能性进行验证，直到找到正确答案。
  • 贪婪法 - 在对问题求解时，总是做出在当前看来
  • 最好的选择，不追求最优解，快速找到满意解。
  • 分治法 - 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到可以直接求解的程度，最后将子问题的解进行合并得到原问题的解。
  • 回溯法 - 回溯法又称为试探法，按选优条件向前搜索，当搜索到某一步发现原先选择并不优或达不到目标时，就退回一步重新选择。
  • 动态规划 - 基本思想也是将待求解问题分解成若干个子问题，先求解并保存这些子问题的解，避免产生大量的重复运算。

  穷举法例子：百钱百鸡和五人分鱼。

  1
  # 公鸡5元一只 母鸡3元一只 小鸡1元三只
  2
  # 用100元买100只鸡 问公鸡/母鸡/小鸡各多少只
  3
  for x in range(20):
  4
      for y in range(33):
  5
          z = 100 - x - y
  6
          if 5 * x + 3 * y + z // 3 == 100 and z % 3 == 0:
  7
              print(x, y, z)
  8
  
  9
  # A、B、C、D、E五人在某天夜里合伙捕鱼 最后疲惫不堪各自睡觉
  10
  # 第二天A第一个醒来 他将鱼分为5份 扔掉多余的1条 拿走自己的一份
  11
  # B第二个醒来 也将鱼分为5份 扔掉多余的1条 拿走自己的一份
  12
  # 然后C、D、E依次醒来也按同样的方式分鱼 问他们至少捕了多少条鱼
  13
  fish = 6
  14
  while True:
  15
      total = fish
  16
      enough = True
  17
      for _ in range(5):
  18
          if (total - 1) % 5 == 0:
  19
              total = (total - 1) // 5 * 4
  20
          else:
  21
              enough = False
  22
              break
  23
      if enough:
  24
          print(fish)
  25
          break
  26
      fish += 5

  贪婪法例子：假设小偷有一个背包，最多能装20公斤赃物，他闯入一户人家，发现如下表所示的物品。很显然，他不能把所有物品都装进背包，所以必须确定拿走哪些物品，留下哪些物品。

  名称	价格（美元）	重量（kg）
  电脑	200	20
  收音机	20	4
  钟	175	10
  花瓶	50	2
  书	10	1
  油画	90	9

  1
  """
  2
  贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。
  3
  输入：
  4
  20 6
  5
  电脑 200 20
  6
  收音机 20 4
  7
  钟 175 10
  8
  花瓶 50 2
  9
  书 10 1
  10
  油画 90 9
  11
  """
  12
  class Thing(object):
  13
      """物品"""
  14
  
  15
      def __init__(self, name, price, weight):
  16
          self.name = name
  17
          self.price = price
  18
          self.weight = weight
  19
  
  20
      @property
  21
      def value(self):
  22
          """价格重量比"""
  23
          return self.price / self.weight
  24
  
  25
  
  26
  def input_thing():
  27
      """输入物品信息"""
  28
      name_str, price_str, weight_str = input().split()
  29
      return name_str, int(price_str), int(weight_str)
  30
  
  31
  
  32
  def main():
  33
      """主函数"""
  34
      max_weight, num_of_things = map(int, input().split())
  35
      all_things = []
  36
      for _ in range(num_of_things):
  37
          all_things.append(Thing(*input_thing()))
  38
      all_things.sort(key=lambda x: x.value, reverse=True)
  39
      total_weight = 0
  40
      total_price = 0
  41
      for thing in all_things:
  42
          if total_weight + thing.weight <= max_weight:
  43
              print(f'小偷拿走了{thing.name}')
  44
              total_weight += thing.weight
  45
              total_price += thing.price
  46
      print(f'总价值: {total_price}美元')
  47
  
  48
  
  49
  if __name__ == '__main__':
  50
      main()

  分治法例子：快速排序。

  1
  """
  2
  快速排序 - 选择枢轴对元素进行划分，左边都比枢轴小右边都比枢轴大
  3
  """
  4
  def quick_sort(items, comp=lambda x, y: x <= y):
  5
      items = list(items)[:]
  6
      _quick_sort(items, 0, len(items) - 1, comp)
  7
      return items
  8
  
  9
  
  10
  def _quick_sort(items, start, end, comp):
  11
      if start < end:
  12
          pos = _partition(items, start, end, comp)
  13
          _quick_sort(items, start, pos - 1, comp)
  14
          _quick_sort(items, pos + 1, end, comp)
  15
  
  16
  
  17
  def _partition(items, start, end, comp):
  18
      pivot = items[end]
  19
      i = start - 1
  20
      for j in range(start, end):
  21
          if comp(items[j], pivot):
  22
              i += 1
  23
              items[i], items[j] = items[j], items[i]
  24
      items[i + 1], items[end] = items[end], items[i + 1]
  25
      return i + 1

  回溯法例子：骑士巡逻。

  1
  """
  2
  递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。
  3
  """
  4
  import sys
  5
  import time
  6
  
  7
  SIZE = 5
  8
  total = 0
  9
  
  10
  
  11
  def print_board(board):
  12
      for row in board:
  13
          for col in row:
  14
              print(str(col).center(4), end='')
  15
          print()
  16
  
  17
  
  18
  def patrol(board, row, col, step=1):
  19
      if row >= 0 and row < SIZE and \
  20
          col >= 0 and col < SIZE and \
  21
          board[row][col] == 0:
  22
          board[row][col] = step
  23
          if step == SIZE * SIZE:
  24
              global total
  25
              total += 1
  26
              print(f'第{total}种走法: ')
  27
              print_board(board)
  28
          patrol(board, row - 2, col - 1, step + 1)
  29
          patrol(board, row - 1, col - 2, step + 1)
  30
          patrol(board, row + 1, col - 2, step + 1)
  31
          patrol(board, row + 2, col - 1, step + 1)
  32
          patrol(board, row + 2, col + 1, step + 1)
  33
          patrol(board, row + 1, col + 2, step + 1)
  34
          patrol(board, row - 1, col + 2, step + 1)
  35
          patrol(board, row - 2, col + 1, step + 1)
  36
          board[row][col] = 0
  37
  
  38
  
  39
  def main():
  40
      board = [[0] * SIZE for _ in range(SIZE)]
  41
      patrol(board, SIZE - 1, SIZE - 1)
  42
  
  43
  
  44
  if __name__ == '__main__':
  45
      main()

  动态规划例子：子列表元素之和的最大值。

  说明：子列表指的是列表中索引（下标）连续的元素构成的列表；列表中的元素是int类型，可能包含正整数、0、负整数；程序输入列表中的元素，输出子列表元素求和的最大值，例如：

  输入：1 -2 3 5 -3 2

  输出：8

  输入：0 -2 3 5 -1 2

  输出：9

  输入：-9 -2 -3 -5 -3

  输出：-2

  1
  def main():
  2
      items = list(map(int, input().split()))
  3
      overall = partial = items[0]
  4
      for i in range(1, len(items)):
  5
          partial = max(items[i], partial + items[i])
  6
          overall = max(partial, overall)
  7
      print(overall)
  8
  
  9
  
  10
  if __name__ == '__main__':
  11
      main()

  说明：这个题目最容易想到的解法是使用二重循环，但是代码的时间性能将会变得非常的糟糕。使用动态规划的思想，仅仅是多用了两个变量，就将原来$O(N^2)$复杂度的问题变成了$O(N)$。

函数的使用方式#

• 将函数视为“一等公民”

  • 函数可以赋值给变量
  • 函数可以作为函数的参数
  • 函数可以作为函数的返回值

• 高阶函数的用法（filter、map以及它们的替代品）

  1
  items1 = list(map(lambda x: x ** 2, filter(lambda x: x % 2, range(1, 10))))
  2
  items2 = [x ** 2 for x in range(1, 10) if x % 2]

• 位置参数、可变参数、关键字参数、命名关键字参数

• 参数的元信息（代码可读性问题）

• 匿名函数和内联函数的用法（lambda函数）

• 闭包和作用域问题

  • Python搜索变量的LEGB顺序（Local >>> Embedded >>> Global >>> Built-in）

  • global和nonlocal关键字的作用

    global：声明或定义全局变量（要么直接使用现有的全局作用域的变量，要么定义一个变量放到全局作用域）。

    nonlocal：声明使用嵌套作用域的变量（嵌套作用域必须存在该变量，否则报错）。

• 装饰器函数（使用装饰器和取消装饰器）

  例子：输出函数执行时间的装饰器。

  1
  def record_time(func):
  2
      """自定义装饰函数的装饰器"""
  3
  
  4
      @wraps(func)
  5
      def wrapper(*args, **kwargs):
  6
          start = time()
  7
          result = func(*args, **kwargs)
  8
          print(f'{func.__name__}: {time() - start}秒')
  9
          return result
  10
  
  11
      return wrapper

  如果装饰器不希望跟print函数耦合，可以编写可以参数化的装饰器。

  1
  from functools import wraps
  2
  from time import time
  3
  
  4
  
  5
  def record(output):
  6
      """可以参数化的装饰器"""
  7
  
  8
    def decorate(func):
  9
  
  10
      @wraps(func)
  11
      def wrapper(*args, **kwargs):
  12
        start = time()
  13
        result = func(*args, **kwargs)
  14
        output(func.__name__, time() - start)
  15
        return result
  16
  
  17
      return wrapper
  18
  
  19
    return decorate

  1
  from functools import wraps
  2
  from time import time
  3
  
  4
  
  5
  class Record():
  6
      """通过定义类的方式定义装饰器"""
  7
  
  8
      def __init__(self, output):
  9
          self.output = output
  10
  
  11
      def __call__(self, func):
  12
  
  13
          @wraps(func)
  14
          def wrapper(*args, **kwargs):
  15
              start = time()
  16
              result = func(*args, **kwargs)
  17
              self.output(func.__name__, time() - start)
  18
              return result
  19
  
  20
          return wrapper

  说明：由于对带装饰功能的函数添加了@wraps装饰器，可以通过func.__wrapped__方式获得被装饰之前的函数或类来取消装饰器的作用。

  例子：用装饰器来实现单例模式。

  1
  from functools import wraps
  2
  
  3
  
  4
  def singleton(cls):
  5
      """装饰类的装饰器"""
  6
      instances = {}
  7
  
  8
      @wraps(cls)
  9
      def wrapper(*args, **kwargs):
  10
          if cls not in instances:
  11
              instances[cls] = cls(*args, **kwargs)
  12
          return instances[cls]
  13
  
  14
      return wrapper
  15
  
  16
  
  17
  @singleton
  18
  class President:
  19
      """总统(单例类)"""
  20
      pass

  提示：上面的代码中用到了闭包（closure），不知道你是否已经意识到了。还没有一个小问题就是，上面的代码并没有实现线程安全的单例，如果要实现线程安全的单例应该怎么做呢？

  线程安全的单例装饰器。

  1
  from functools import wraps
  2
  from threading import RLock
  3
  
  4
  
  5
  def singleton(cls):
  6
      """线程安全的单例装饰器"""
  7
      instances = {}
  8
      locker = RLock()
  9
  
  10
      @wraps(cls)
  11
      def wrapper(*args, **kwargs):
  12
          if cls not in instances:
  13
              with locker:
  14
                  if cls not in instances:
  15
                      instances[cls] = cls(*args, **kwargs)
  16
          return instances[cls]
  17
  
  18
      return wrapper

  提示：上面的代码用到了with上下文语法来进行锁操作，因为锁对象本身就是上下文管理器对象（支持__enter__和__exit__魔术方法）。在wrapper函数中，我们先做了一次不带锁的检查，然后再做带锁的检查，这样做比直接加锁检查性能要更好，如果对象已经创建就没有必须再去加锁而是直接返回该对象就可以了。

面向对象相关知识#

• 三大支柱：封装、继承、多态

  例子：工资结算系统。

  1
  """
  2
  月薪结算系统 - 部门经理每月15000 程序员每小时200 销售员1800底薪加销售额5%提成
  3
  """
  4
  from abc import ABCMeta, abstractmethod
  5
  
  6
  
  7
  class Employee(metaclass=ABCMeta):
  8
      """员工(抽象类)"""
  9
  
  10
      def __init__(self, name):
  11
          self.name = name
  12
  
  13
      @abstractmethod
  14
      def get_salary(self):
  15
          """结算月薪(抽象方法)"""
  16
          pass
  17
  
  18
  
  19
  class Manager(Employee):
  20
      """部门经理"""
  21
  
  22
      def get_salary(self):
  23
          return 15000.0
  24
  
  25
  
  26
  class Programmer(Employee):
  27
      """程序员"""
  28
  
  29
      def __init__(self, name, working_hour=0):
  30
          self.working_hour = working_hour
  31
          super().__init__(name)
  32
  
  33
      def get_salary(self):
  34
          return 200.0 * self.working_hour
  35
  
  36
  
  37
  class Salesman(Employee):
  38
      """销售员"""
  39
  
  40
      def __init__(self, name, sales=0.0):
  41
          self.sales = sales
  42
          super().__init__(name)
  43
  
  44
      def get_salary(self):
  45
          return 1800.0 + self.sales * 0.05
  46
  
  47
  
  48
  class EmployeeFactory:
  49
      """创建员工的工厂（工厂模式 - 通过工厂实现对象使用者和对象之间的解耦合）"""
  50
  
  51
      @staticmethod
  52
      def create(emp_type, *args, **kwargs):
  53
          """创建员工"""
  54
          all_emp_types = {'M': Manager, 'P': Programmer, 'S': Salesman}
  55
          cls = all_emp_types[emp_type.upper()]
  56
          return cls(*args, **kwargs) if cls else None
  57
  
  58
  
  59
  def main():
  60
      """主函数"""
  61
      emps = [
  62
          EmployeeFactory.create('M', '曹操'),
  63
          EmployeeFactory.create('P', '荀彧', 120),
  64
          EmployeeFactory.create('P', '郭嘉', 85),
  65
          EmployeeFactory.create('S', '典韦', 123000),
  66
      ]
  67
      for emp in emps:
  68
          print(f'{emp.name}: {emp.get_salary():.2f}元')
  69
  
  70
  
  71
  if __name__ == '__main__':
  72
      main()

• 类与类之间的关系

  • is-a关系：继承
  • has-a关系：关联 / 聚合 / 合成
  • use-a关系：依赖

  例子：扑克游戏。

  1
  """
  2
  经验：符号常量总是优于字面常量，枚举类型是定义符号常量的最佳选择
  3
  """
  4
  from enum import Enum, unique
  5
  
  6
  import random
  7
  
  8
  
  9
  @unique
  10
  class Suite(Enum):
  11
      """花色"""
  12
  
  13
      SPADE, HEART, CLUB, DIAMOND = range(4)
  14
  
  15
      def __lt__(self, other):
  16
          return self.value < other.value
  17
  
  18
  
  19
  class Card:
  20
      """牌"""
  21
  
  22
      def __init__(self, suite, face):
  23
          """初始化方法"""
  24
          self.suite = suite
  25
          self.face = face
  26
  
  27
      def show(self):
  28
          """显示牌面"""
  29
          suites = ['♠︎', '♥︎', '♣︎', '♦︎']
  30
          faces = ['', 'A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']
  31
          return f'{suites[self.suite.value]}{faces[self.face]}'
  32
  
  33
      def __repr__(self):
  34
          return self.show()
  35
  
  36
  
  37
  class Poker:
  38
      """扑克"""
  39
  
  40
      def __init__(self):
  41
          self.index = 0
  42
          self.cards = [Card(suite, face)
  43
                        for suite in Suite
  44
                        for face in range(1, 14)]
  45
  
  46
      def shuffle(self):
  47
          """洗牌（随机乱序）"""
  48
          random.shuffle(self.cards)
  49
          self.index = 0
  50
  
  51
      def deal(self):
  52
          """发牌"""
  53
          card = self.cards[self.index]
  54
          self.index += 1
  55
          return card
  56
  
  57
      @property
  58
      def has_more(self):
  59
          return self.index < len(self.cards)
  60
  
  61
  
  62
  class Player:
  63
      """玩家"""
  64
  
  65
      def __init__(self, name):
  66
          self.name = name
  67
          self.cards = []
  68
  
  69
      def get_one(self, card):
  70
          """摸一张牌"""
  71
          self.cards.append(card)
  72
  
  73
      def sort(self, comp=lambda card: (card.suite, card.face)):
  74
          """整理手上的牌"""
  75
          self.cards.sort(key=comp)
  76
  
  77
  
  78
  def main():
  79
      """主函数"""
  80
      poker = Poker()
  81
      poker.shuffle()
  82
      players = [Player('东邪'), Player('西毒'), Player('南帝'), Player('北丐')]
  83
      while poker.has_more:
  84
          for player in players:
  85
                  player.get_one(poker.deal())
  86
      for player in players:
  87
          player.sort()
  88
          print(player.name, end=': ')
  89
          print(player.cards)
  90
  
  91
  
  92
  if __name__ == '__main__':
  93
      main()

  说明：上面的代码中使用了Emoji字符来表示扑克牌的四种花色，在某些不支持Emoji字符的系统上可能无法显示。

• 对象的复制（深复制/深拷贝/深度克隆和浅复制/浅拷贝/影子克隆）

• 垃圾回收、循环引用和弱引用

  Python使用了自动化内存管理，这种管理机制以引用计数为基础，同时也引入了标记-清除和分代收集两种机制为辅的策略。

  1
  typedef struct _object {
  2
      /* 引用计数 */
  3
      int ob_refcnt;
  4
      /* 对象指针 */
  5
      struct _typeobject *ob_type;
  6
  } PyObject;

  1
  /* 增加引用计数的宏定义 */
  2
  #define Py_INCREF(op)   ((op)->ob_refcnt++)
  3
  /* 减少引用计数的宏定义 */
  4
  #define Py_DECREF(op) \ //减少计数
  5
      if (--(op)->ob_refcnt != 0) \
  6
          ; \
  7
      else \
  8
          __Py_Dealloc((PyObject *)(op))

  导致引用计数+1的情况：

  • 对象被创建，例如a = 23
  • 对象被引用，例如b = a
  • 对象被作为参数，传入到一个函数中，例如f(a)
  • 对象作为一个元素，存储在容器中，例如list1 = [a, a]

  导致引用计数-1的情况：

  • 对象的别名被显式销毁，例如del a
  • 对象的别名被赋予新的对象，例如a = 24
  • 一个对象离开它的作用域，例如f函数执行完毕时，f函数中的局部变量（全局变量不会）
  • 对象所在的容器被销毁，或从容器中删除对象

  引用计数可能会导致循环引用问题，而循环引用会导致内存泄露，如下面的代码所示。为了解决这个问题，Python中引入了“标记-清除”和“分代收集”。在创建一个对象的时候，对象被放在第一代中，如果在第一代的垃圾检查中对象存活了下来，该对象就会被放到第二代中，同理在第二代的垃圾检查中对象存活下来，该对象就会被放到第三代中。

  1
  # 循环引用会导致内存泄露 - Python除了引用技术还引入了标记清理和分代回收
  2
  # 在Python 3.6以前如果重写__del__魔术方法会导致循环引用处理失效
  3
  # 如果不想造成循环引用可以使用弱引用
  4
  list1 = []
  5
  list2 = []
  6
  list1.append(list2)
  7
  list2.append(list1)

  以下情况会导致垃圾回收：

  • 调用gc.collect()
  • gc模块的计数器达到阀值
  • 程序退出

  如果循环引用中两个对象都定义了__del__方法，gc模块不会销毁这些不可达对象，因为gc模块不知道应该先调用哪个对象的__del__方法，这个问题在Python 3.6中得到了解决。

  也可以通过weakref模块构造弱引用的方式来解决循环引用的问题。

• 魔法属性和方法（请参考《Python魔法方法指南》）

  有几个小问题请大家思考：

  • 自定义的对象能不能使用运算符做运算？
  • 自定义的对象能不能放到set中？能去重吗？
  • 自定义的对象能不能作为dict的键？
  • 自定义的对象能不能使用上下文语法？

• 混入（Mixin）

  例子：自定义字典限制只有在指定的key不存在时才能在字典中设置键值对。

  1
  class SetOnceMappingMixin:
  2
      """自定义混入类"""
  3
      __slots__ = ()
  4
  
  5
      def __setitem__(self, key, value):
  6
          if key in self:
  7
              raise KeyError(str(key) + ' already set')
  8
          return super().__setitem__(key, value)
  9
  
  10
  
  11
  class SetOnceDict(SetOnceMappingMixin, dict):
  12
      """自定义字典"""
  13
      pass
  14
  
  15
  
  16
  my_dict= SetOnceDict()
  17
  try:
  18
      my_dict['username'] = 'jackfrued'
  19
      my_dict['username'] = 'hellokitty'
  20
  except KeyError:
  21
      pass
  22
  print(my_dict)

• 元编程和元类

  对象是通过类创建的，类是通过元类创建的，元类提供了创建类的元信息。所有的类都直接或间接的继承自object，所有的元类都直接或间接的继承自type。

  例子：用元类实现单例模式。

  1
  import threading
  2
  
  3
  
  4
  class SingletonMeta(type):
  5
      """自定义元类"""
  6
  
  7
      def __init__(cls, *args, **kwargs):
  8
          cls.__instance = None
  9
          cls.__lock = threading.RLock()
  10
          super().__init__(*args, **kwargs)
  11
  
  12
      def __call__(cls, *args, **kwargs):
  13
          if cls.__instance is None:
  14
              with cls.__lock:
  15
                  if cls.__instance is None:
  16
                      cls.__instance = super().__call__(*args, **kwargs)
  17
          return cls.__instance
  18
  
  19
  
  20
  class President(metaclass=SingletonMeta):
  21
      """总统(单例类)"""
  22
  
  23
      pass

• 面向对象设计原则

  • 单一职责原则 （SRP）- 一个类只做该做的事情（类的设计要高内聚）
  • 开闭原则 （OCP）- 软件实体应该对扩展开发对修改关闭
  • 依赖倒转原则（DIP）- 面向抽象编程（在弱类型语言中已经被弱化）
  • 里氏替换原则（LSP） - 任何时候可以用子类对象替换掉父类对象
  • 接口隔离原则（ISP）- 接口要小而专不要大而全（Python中没有接口的概念）
  • 合成聚合复用原则（CARP） - 优先使用强关联关系而不是继承关系复用代码
  • 最少知识原则（迪米特法则，LoD）- 不要给没有必然联系的对象发消息

  说明：上面加粗的字母放在一起称为面向对象的SOLID原则。

• GoF设计模式

  • 创建型模式：单例、工厂、建造者、原型
  • 结构型模式：适配器、门面（外观）、代理
  • 行为型模式：迭代器、观察者、状态、策略

  例子：可插拔的哈希算法（策略模式）。

  1
  class StreamHasher:
  2
      """哈希摘要生成器"""
  3
  
  4
      def __init__(self, alg='md5', size=4096):
  5
          self.size = size
  6
          alg = alg.lower()
  7
          self.hasher = getattr(__import__('hashlib'), alg.lower())()
  8
  
  9
      def __call__(self, stream):
  10
          return self.to_digest(stream)
  11
  
  12
      def to_digest(self, stream):
  13
          """生成十六进制形式的摘要"""
  14
          for buf in iter(lambda: stream.read(self.size), b''):
  15
              self.hasher.update(buf)
  16
          return self.hasher.hexdigest()
  17
  
  18
  def main():
  19
      """主函数"""
  20
      hasher1 = StreamHasher()
  21
      with open('Python-3.7.6.tgz', 'rb') as stream:
  22
          print(hasher1.to_digest(stream))
  23
      hasher2 = StreamHasher('sha1')
  24
      with open('Python-3.7.6.tgz', 'rb') as stream:
  25
          print(hasher2(stream))
  26
  
  27
  
  28
  if __name__ == '__main__':
  29
      main()

迭代器和生成器#

• 迭代器是实现了迭代器协议的对象。

  • Python中没有像protocol或interface这样的定义协议的关键字。
  • Python中用魔术方法表示协议。
  • __iter__和__next__魔术方法就是迭代器协议。

  1
  class Fib(object):
  2
      """迭代器"""
  3
  
  4
      def __init__(self, num):
  5
          self.num = num
  6
          self.a, self.b = 0, 1
  7
          self.idx = 0
  8
  
  9
      def __iter__(self):
  10
          return self
  11
  
  12
      def __next__(self):
  13
          if self.idx < self.num:
  14
              self.a, self.b = self.b, self.a + self.b
  15
              self.idx += 1
  16
              return self.a
  17
          raise StopIteration()

• 生成器是语法简化版的迭代器。

  1
  def fib(num):
  2
      """生成器"""
  3
      a, b = 0, 1
  4
      for _ in range(num):
  5
          a, b = b, a + b
  6
          yield a

• 生成器进化为协程。

  生成器对象可以使用send()方法发送数据，发送的数据会成为生成器函数中通过yield表达式获得的值。这样，生成器就可以作为协程使用，协程简单的说就是可以相互协作的子程序。

  1
  def calc_avg():
  2
      """流式计算平均值"""
  3
      total, counter = 0, 0
  4
      avg_value = None
  5
      while True:
  6
          value = yield avg_value
  7
          total, counter = total + value, counter + 1
  8
          avg_value = total / counter
  9
  
  10
  
  11
  gen = calc_avg()
  12
  next(gen)
  13
  print(gen.send(10))
  14
  print(gen.send(20))
  15
  print(gen.send(30))

并发编程#

Python中实现并发编程的三种方案：多线程、多进程和异步I/O。并发编程的好处在于可以提升程序的执行效率以及改善用户体验；坏处在于并发的程序不容易开发和调试，同时对其他程序来说它并不友好。

• 多线程：Python中提供了Thread类并辅以Lock、Condition、Event、Semaphore和Barrier。Python中有GIL来防止多个线程同时执行本地字节码，这个锁对于CPython是必须的，因为CPython的内存管理并不是线程安全的，因为GIL的存在多线程并不能发挥CPU的多核特性。

  1
  """
  2
  面试题：进程和线程的区别和联系？
  3
  进程 - 操作系统分配内存的基本单位 - 一个进程可以包含一个或多个线程
  4
  线程 - 操作系统分配CPU的基本单位
  5
  并发编程（concurrent programming）
  6
  1. 提升执行性能 - 让程序中没有因果关系的部分可以并发的执行
  7
  2. 改善用户体验 - 让耗时间的操作不会造成程序的假死
  8
  """
  9
  import glob
  10
  import os
  11
  import threading
  12
  
  13
  from PIL import Image
  14
  
  15
  PREFIX = 'thumbnails'
  16
  
  17
  
  18
  def generate_thumbnail(infile, size, format='PNG'):
  19
      """生成指定图片文件的缩略图"""
  20
    file, ext = os.path.splitext(infile)
  21
    file = file[file.rfind('/') + 1:]
  22
    outfile = f'{PREFIX}/{file}_{size[0]}_{size[1]}.{ext}'
  23
    img = Image.open(infile)
  24
    img.thumbnail(size, Image.ANTIALIAS)
  25
    img.save(outfile, format)
  26
  
  27
  
  28
  def main():
  29
      """主函数"""
  30
    if not os.path.exists(PREFIX):
  31
      os.mkdir(PREFIX)
  32
    for infile in glob.glob('images/*.png'):
  33
      for size in (32, 64, 128):
  34
              # 创建并启动线程
  35
        threading.Thread(
  36
          target=generate_thumbnail,
  37
          args=(infile, (size, size))
  38
        ).start()
  39
  
  40
  
  41
  if __name__ == '__main__':
  42
    main()

  多个线程竞争资源的情况。

  1
  """
  2
  多线程程序如果没有竞争资源处理起来通常也比较简单
  3
  当多个线程竞争临界资源的时候如果缺乏必要的保护措施就会导致数据错乱
  4
  说明：临界资源就是被多个线程竞争的资源
  5
  """
  6
  import time
  7
  import threading
  8
  
  9
  from concurrent.futures import ThreadPoolExecutor
  10
  
  11
  
  12
  class Account(object):
  13
      """银行账户"""
  14
  
  15
      def __init__(self):
  16
          self.balance = 0.0
  17
          self.lock = threading.Lock()
  18
  
  19
      def deposit(self, money):
  20
          # 通过锁保护临界资源
  21
          with self.lock:
  22
              new_balance = self.balance + money
  23
              time.sleep(0.001)
  24
              self.balance = new_balance
  25
  
  26
  
  27
  def main():
  28
      """主函数"""
  29
      account = Account()
  30
      # 创建线程池
  31
      pool = ThreadPoolExecutor(max_workers=10)
  32
      futures = []
  33
      for _ in range(100):
  34
          future = pool.submit(account.deposit, 1)
  35
          futures.append(future)
  36
      # 关闭线程池
  37
      pool.shutdown()
  38
      for future in futures:
  39
          future.result()
  40
      print(account.balance)
  41
  
  42
  
  43
  if __name__ == '__main__':
  44
      main()

  修改上面的程序，启动5个线程向账户中存钱，5个线程从账户中取钱，取钱时如果余额不足就暂停线程进行等待。为了达到上述目标，需要对存钱和取钱的线程进行调度，在余额不足时取钱的线程暂停并释放锁，而存钱的线程将钱存入后要通知取钱的线程，使其从暂停状态被唤醒。可以使用threading模块的Condition来实现线程调度，该对象也是基于锁来创建的，代码如下所示：

  1
  """
  2
  多个线程竞争一个资源 - 保护临界资源 - 锁（Lock/RLock）
  3
  多个线程竞争多个资源（线程数>资源数） - 信号量（Semaphore）
  4
  多个线程的调度 - 暂停线程执行/唤醒等待中的线程 - Condition
  5
  """
  6
  from concurrent.futures import ThreadPoolExecutor
  7
  from random import randint
  8
  from time import sleep
  9
  
  10
  import threading
  11
  
  12
  
  13
  class Account:
  14
      """银行账户"""
  15
  
  16
      def __init__(self, balance=0):
  17
          self.balance = balance
  18
          lock = threading.RLock()
  19
          self.condition = threading.Condition(lock)
  20
  
  21
      def withdraw(self, money):
  22
          """取钱"""
  23
          with self.condition:
  24
              while money > self.balance:
  25
                  self.condition.wait()
  26
              new_balance = self.balance - money
  27
              sleep(0.001)
  28
              self.balance = new_balance
  29
  
  30
      def deposit(self, money):
  31
          """存钱"""
  32
          with self.condition:
  33
              new_balance = self.balance + money
  34
              sleep(0.001)
  35
              self.balance = new_balance
  36
              self.condition.notify_all()
  37
  
  38
  
  39
  def add_money(account):
  40
      while True:
  41
          money = randint(5, 10)
  42
          account.deposit(money)
  43
          print(threading.current_thread().name,
  44
                ':', money, '====>', account.balance)
  45
          sleep(0.5)
  46
  
  47
  
  48
  def sub_money(account):
  49
      while True:
  50
          money = randint(10, 30)
  51
          account.withdraw(money)
  52
          print(threading.current_thread().name,
  53
                ':', money, '<====', account.balance)
  54
          sleep(1)
  55
  
  56
  
  57
  def main():
  58
      account = Account()
  59
      with ThreadPoolExecutor(max_workers=15) as pool:
  60
          for _ in range(5):
  61
              pool.submit(add_money, account)
  62
          for _ in range(10):
  63
              pool.submit(sub_money, account)
  64
  
  65
  
  66
  if __name__ == '__main__':
  67
      main()

• 多进程：多进程可以有效的解决GIL的问题，实现多进程主要的类是Process，其他辅助的类跟threading模块中的类似，进程间共享数据可以使用管道、套接字等，在multiprocessing模块中有一个Queue类，它基于管道和锁机制提供了多个进程共享的队列。下面是官方文档上关于多进程和进程池的一个示例。

  1
  """
  2
  多进程和进程池的使用
  3
  多线程因为GIL的存在不能够发挥CPU的多核特性
  4
  对于计算密集型任务应该考虑使用多进程
  5
  time python3 example22.py
  6
  real    0m11.512s
  7
  user    0m39.319s
  8
  sys     0m0.169s
  9
  使用多进程后实际执行时间为11.512秒，而用户时间39.319秒约为实际执行时间的4倍
  10
  这就证明我们的程序通过多进程使用了CPU的多核特性，而且这台计算机配置了4核的CPU
  11
  """
  12
  import concurrent.futures
  13
  import math
  14
  
  15
  PRIMES = [
  16
      1116281,
  17
      1297337,
  18
      104395303,
  19
      472882027,
  20
      533000389,
  21
      817504243,
  22
      982451653,
  23
      112272535095293,
  24
      112582705942171,
  25
      112272535095293,
  26
      115280095190773,
  27
      115797848077099,
  28
      1099726899285419
  29
  ] * 5
  30
  
  31
  
  32
  def is_prime(n):
  33
      """判断素数"""
  34
      if n % 2 == 0:
  35
          return False
  36
  
  37
      sqrt_n = int(math.floor(math.sqrt(n)))
  38
      for i in range(3, sqrt_n + 1, 2):
  39
          if n % i == 0:
  40
              return False
  41
      return True
  42
  
  43
  
  44
  def main():
  45
      """主函数"""
  46
      with concurrent.futures.ProcessPoolExecutor() as executor:
  47
          for number, prime in zip(PRIMES, executor.map(is_prime, PRIMES)):
  48
              print('%d is prime: %s' % (number, prime))
  49
  
  50
  
  51
  if __name__ == '__main__':
  52
      main()

  重点：多线程和多进程的比较。

  以下情况需要使用多线程：

  1. 程序需要维护许多共享的状态（尤其是可变状态），Python中的列表、字典、集合都是线程安全的，所以使用线程而不是进程维护共享状态的代价相对较小。
  2. 程序会花费大量时间在I/O操作上，没有太多并行计算的需求且不需占用太多的内存。

  以下情况需要使用多进程：

  1. 程序执行计算密集型任务（如：字节码操作、数据处理、科学计算）。
  2. 程序的输入可以并行的分成块，并且可以将运算结果合并。
  3. 程序在内存使用方面没有任何限制且不强依赖于I/O操作（如：读写文件、套接字等）。

• 异步处理：从调度程序的任务队列中挑选任务，该调度程序以交叉的形式执行这些任务，我们并不能保证任务将以某种顺序去执行，因为执行顺序取决于队列中的一项任务是否愿意将 CPU 处理时间让位给另一项任务。异步任务通常通过多任务协作处理的方式来实现，由于执行时间和顺序的不确定，因此需要通过回调式编程或者future对象来获取任务执行的结果。Python 3 通过asyncio模块和await和async关键字（在 Python 3.7 中正式被列为关键字）来支持异步处理。

  1
  """
  2
  异步I/O - async / await
  3
  """
  4
  import asyncio
  5
  
  6
  
  7
  def num_generator(m, n):
  8
      """指定范围的数字生成器"""
  9
      yield from range(m, n + 1)
  10
  
  11
  
  12
  async def prime_filter(m, n):
  13
      """素数过滤器"""
  14
      primes = []
  15
      for i in num_generator(m, n):
  16
          flag = True
  17
          for j in range(2, int(i ** 0.5 + 1)):
  18
              if i % j == 0:
  19
                  flag = False
  20
                  break
  21
          if flag:
  22
              print('Prime =>', i)
  23
              primes.append(i)
  24
  
  25
          await asyncio.sleep(0.001)
  26
      return tuple(primes)
  27
  
  28
  
  29
  async def square_mapper(m, n):
  30
      """平方映射器"""
  31
      squares = []
  32
      for i in num_generator(m, n):
  33
          print('Square =>', i * i)
  34
          squares.append(i * i)
  35
  
  36
          await asyncio.sleep(0.001)
  37
      return squares
  38
  
  39
  
  40
  def main():
  41
      """主函数"""
  42
      loop = asyncio.get_event_loop()
  43
      future = asyncio.gather(prime_filter(2, 100), square_mapper(1, 100))
  44
      future.add_done_callback(lambda x: print(x.result()))
  45
      loop.run_until_complete(future)
  46
      loop.close()
  47
  
  48
  
  49
  if __name__ == '__main__':
  50
      main()

  说明：上面的代码使用get_event_loop函数获得系统默认的事件循环，通过gather函数可以获得一个future对象，future对象的add_done_callback可以添加执行完成时的回调函数，loop对象的run_until_complete方法可以等待通过future对象获得协程执行结果。

  Python 中有一个名为aiohttp的三方库，它提供了异步的 HTTP 客户端和服务器，这个三方库可以跟asyncio模块一起工作，并提供了对Future对象的支持。Python 3.6中引入了async和await来定义异步执行的函数以及创建异步上下文，在 Python 3.7 中它们正式成为了关键字。下面的代码异步的从5个URL中获取页面并通过正则表达式的命名捕获组提取了网站的标题。

  1
  import asyncio
  2
  import re
  3
  
  4
  import aiohttp
  5
  
  6
  PATTERN = re.compile(r'\<title\>(?P<title>.*)\<\/title\>')
  7
  
  8
  
  9
  async def fetch_page(session, url):
  10
      async with session.get(url, ssl=False) as resp:
  11
          return await resp.text()
  12
  
  13
  
  14
  async def show_title(url):
  15
      async with aiohttp.ClientSession() as session:
  16
          html = await fetch_page(session, url)
  17
          print(PATTERN.search(html).group('title'))
  18
  
  19
  
  20
  def main():
  21
      urls = ('https://www.python.org/',
  22
              'https://git-scm.com/',
  23
              'https://www.jd.com/',
  24
              'https://www.taobao.com/',
  25
              'https://www.douban.com/')
  26
      loop = asyncio.get_event_loop()
  27
      cos = [show_title(url) for url in urls]
  28
      loop.run_until_complete(asyncio.wait(cos))
  29
      loop.close()
  30
  
  31
  
  32
  if __name__ == '__main__':
  33
      main()

  重点：异步I/O与多进程的比较。

  当程序不需要真正的并发性或并行性，而是更多的依赖于异步处理和回调时，asyncio就是一种很好的选择。如果程序中有大量的等待与休眠时，也应该考虑asyncio，它很适合编写没有实时数据处理需求的 Web 应用服务器。

  Python 还有很多用于处理并行任务的三方库，例如：joblib、PyMP等。实际开发中，要提升系统的可扩展性和并发性通常有垂直扩展（增加单个节点的处理能力）和水平扩展（将单个节点变成多个节点）两种做法。可以通过消息队列来实现应用程序的解耦合，消息队列相当于是多线程同步队列的扩展版本，不同机器上的应用程序相当于就是线程，而共享的分布式消息队列就是原来程序中的Queue。消息队列（面向消息的中间件）的最流行和最标准化的实现是 AMQP（高级消息队列协议），AMQP 源于金融行业，提供了排队、路由、可靠传输、安全等功能，最著名的实现包括：Apache 的 ActiveMQ、RabbitMQ 等。

  要实现任务的异步化，可以使用名为Celery的三方库。Celery是 Python 编写的分布式任务队列，它使用分布式消息进行工作，可以基于 RabbitMQ 或 Redis 来作为后端的消息代理。