day16 - Python语言进阶

Python语言进阶

1. 数据结构和算法

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

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

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

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

     

     

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

     def select_sort(origin_items, comp=lambda x, y: x < y): """简单选择排序""" items = origin_items[:] for i in range(len(items) - 1): min_index = i for j in range(i + 1, len(items)): if comp(items[j], items[min_index]): min_index = j items[i], items[min_index] = items[min_index], items[i] return items

     def bubble_sort(origin_items, comp=lambda x, y: x > y): """高质量冒泡排序(搅拌排序)""" items = origin_items[:] for i in range(len(items) - 1): swapped = False for j in range(i, len(items) - 1 - i): if comp(items[j], items[j + 1]): items[j], items[j + 1] = items[j + 1], items[j] swapped = True if swapped: swapped = False for j in range(len(items) - 2 - i, i, -1): if comp(items[j - 1], items[j]): items[j], items[j - 1] = items[j - 1], items[j] swapped = True if not swapped: break return items

     def merge_sort(items, comp=lambda x, y: x <= y): """归并排序(分治法)""" if len(items) < 2: return items[:] mid = len(items) // 2 left = merge_sort(items[:mid], comp) right = merge_sort(items[mid:], comp) return merge(left, right, comp) def merge(items1, items2, comp): """合并(将两个有序的列表合并成一个有序的列表)""" items = [] index, index2 = 0, 0 while index1 < len(items1) and index2 < len(items2): if comp(items1[index1], items2[index2]): items.append(items1[index1]) index1 += 1 else: items.append(items2[index2]) index2 += 1 items += items1[index1:] items += items2[index2:] return items

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

     def bin_search(items, key):
         """折半查找""" start, end = 0, len(items) - 1 while start <= end: mid = (start + end) // 2 if key > items[mid]: start = mid + 1 elif key < items[mid]: end = mid - 1 else: return mid return -1

   • 使用生成式（推导式）语法

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

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

   • 嵌套的列表

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

     Python Tutor - VISUALIZE CODE AND GET LIVE HELP

   • heapq、itertools等的用法

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

     """
     迭代工具 - 排列 / 组合 / 笛卡尔积
     """
     import itertools
     
     itertools.permutations('ABCD') itertools.combinations('ABCDE', 3) itertools.product('ABCD', '123')

   • collections模块下的工具类

     """
     找出序列中出现次数最多的元素
     """
     from collections import Counter
     
     words = [ 'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes', 'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the', 'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into', 'my', 'eyes', "you're", 'under' ] counter = Counter(words) print(counter.most_common(3))

   • 常用算法：

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

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

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

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

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

     """
     贪婪法：在对问题求解时，总是做出在当前看来是最好的选择，不追求最优解，快速找到满意解。
     输入：
     20 6
     电脑 200 20
     收音机 20 4 钟 175 10 花瓶 50 2 书 10 1 油画 90 9 """ class Thing(object): """物品""" def __init__(self, name, price, weight): self.name = name self.price = price self.weight = weight @property def value(self): """价格重量比""" return self.price / self.weight def input_thing(): """输入物品信息""" name_str, price_str, weight_str = input().split() return name_str, int(price_str), int(weight_str) def main(): """主函数""" max_weight, num_of_things = map(int, input().split()) all_things = [] for _ in range(num_of_things): all_things.append(Thing(*input_thing())) all_things.sort(key=lambda x: x.value, reverse=True) total_weight = 0 total_price = 0 for thing in all_things: if total_weight + thing.weight <= max_weight: print(f'小偷拿走了{thing.name}') total_weight += thing.weight total_price += thing.price print(f'总价值: {total_price}美元') if __name__ == '__main__': main()

     分治法例子：快速排序。

     """
     快速排序 - 选择枢轴对元素进行划分，左边都比枢轴小右边都比枢轴大
     """
     def quick_sort(origin_items, comp=lambda x, y: x <= y): items = origin_items[:] _quick_sort(items, 0, len(items) - 1, comp) return items def _quick_sort(items, start, end, comp): if start < end: pos = _partition(items, start, end, comp) _quick_sort(items, start, pos - 1, comp) _quick_sort(items, pos + 1, end, comp) def _partition(items, start, end, comp): pivot = items[end] i = start - 1 for j in range(start, end): if comp(items[j], pivot): i += 1 items[i], items[j] = items[j], items[i] items[i + 1], items[end] = items[end], items[i + 1] return i + 1

     回溯法例子：骑士巡逻。

     """
     递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。
     """
     import sys
     import time
     
     SIZE = 5 total = 0 def print_board(board): for row in board: for col in row: print(str(col).center(4), end='') print() def patrol(board, row, col, step=1): if row >= 0 and row < SIZE and \ col >= 0 and col < SIZE and \ board[row][col] == 0: board[row][col] = step if step == SIZE * SIZE: global total total += 1 print(f'第{total}种走法: ') print_board(board) patrol(board, row - 2, col - 1, step + 1) patrol(board, row - 1, col - 2, step + 1) patrol(board, row + 1, col - 2, step + 1) patrol(board, row + 2, col - 1, step + 1) patrol(board, row + 2, col + 1, step + 1) patrol(board, row + 1, col + 2, step + 1) patrol(board, row - 1, col + 2, step + 1) patrol(board, row - 2, col + 1, step + 1) board[row][col] = 0 def main(): board = [[0] * SIZE for _ in range(SIZE)] patrol(board, SIZE - 1, SIZE - 1) if __name__ == '__main__': main()

     动态规划例子1：斐波拉切数列。（不使用动态规划将会是几何级数复杂度）

     """
     动态规划 - 适用于有重叠子问题和最优子结构性质的问题
     使用动态规划方法所耗时间往往远少于朴素解法(用空间换取时间)
     """
     def fib(num, temp={}): """用递归计算Fibonacci数""" if num in (1, 2): return 1 try: return temp[num] except KeyError: temp[num] = fib(num - 1) + fib(num - 2) return temp[num]

     动态规划例子2：子列表元素之和的最大值。（使用动态规划可以避免二重循环）

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

     输入：1 -2 3 5 -3 2

     输出：8

     输入：0 -2 3 5 -1 2

     输出：9

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

     输出：-2

     def main():
         items = list(map(int, input().split())) size = len(items) overall, partial = {}, {} overall[size - 1] = partial[size - 1] = items[size - 1] for i in range(size - 2, -1, -1): partial[i] = max(items[i], partial[i + 1] + items[i]) overall[i] = max(partial[i], overall[i + 1]) print(overall[0]) if __name__ == '__main__': main()

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：声明使用嵌套作用域的变量（嵌套作用域必须存在该变量，否则报错）。

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

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

     def record_time(func):
         """自定义装饰函数的装饰器""" @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) print(f'{func.__name__}: {time() - start}秒') return result return wrapper

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

     from functools import wraps
     from time import time
     
     
     def record(output): """自定义带参数的装饰器""" def decorate(func): @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) output(func.__name__, time() - start) return result return wrapper return decorate

     from functools import wraps
     from time import time
     
     
     class Record(): """自定义装饰器类(通过__call__魔术方法使得对象可以当成函数调用)""" def __init__(self, output): self.output = output def __call__(self, func): @wraps(func) def wrapper(*args, **kwargs): start = time() result = func(*args, **kwargs) self.output(func.__name__, time() - start) return result return wrapper

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

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

     from functools import wraps
     
     
     def singleton(cls):
         """装饰类的装饰器""" instances = {} @wraps(cls) def wrapper(*args, **kwargs): if cls not in instances: instances[cls] = cls(*args, **kwargs) return instances[cls] return wrapper @singleton class President(): """总统(单例类)""" pass

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

     from functools import wraps
     
     
     def singleton(cls):
         """线程安全的单例装饰器""" instances = {} locker = Lock() @wraps(cls) def wrapper(*args, **kwargs): if cls not in instances: with locker: if cls not in instances: instances[cls] = cls(*args, **kwargs) return instances[cls] return wrapper

3. 面向对象相关知识

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

     例子：工资结算系统。

     """
     月薪结算系统 - 部门经理每月15000 程序员每小时200 销售员1800底薪加销售额5%提成
     """
     from abc import ABCMeta, abstractmethod
     
     
     class Employee(metaclass=ABCMeta): """员工(抽象类)""" def __init__(self, name): self.name = name @abstractmethod def get_salary(self): """结算月薪(抽象方法)""" pass class Manager(Employee): """部门经理""" def get_salary(self): return 15000.0 class Programmer(Employee): """程序员""" def __init__(self, name, working_hour=0): self.working_hour = working_hour super().__init__(name) def get_salary(self): return 200.0 * self.working_hour class Salesman(Employee): """销售员""" def __init__(self, name, sales=0.0): self.sales = sales super().__init__(name) def get_salary(self): return 1800.0 + self.sales * 0.05 class EmployeeFactory(): """创建员工的工厂（工厂模式 - 通过工厂实现对象使用者和对象之间的解耦合）""" @staticmethod def create(emp_type, *args, **kwargs): """创建员工""" emp_type = emp_type.upper() emp = None if emp_type == 'M': emp = Manager(*args, **kwargs) elif emp_type == 'P': emp = Programmer(*args, **kwargs) elif emp_type == 'S': emp = Salesman(*args, **kwargs) return emp def main(): """主函数""" emps = [ EmployeeFactory.create('M', '曹操'), EmployeeFactory.create('P', '荀彧', 120), EmployeeFactory.create('P', '郭嘉', 85), EmployeeFactory.create('S', '典韦', 123000), ] for emp in emps: print('%s: %.2f元' % (emp.name, emp.get_salary())) if __name__ == '__main__': main()

   • 类与类之间的关系

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

     例子：扑克游戏。

     """
     经验：符号常量总是优于字面常量，枚举类型是定义符号常量的最佳选择
     """
     from enum import Enum, unique
     
     import random @unique class Suite(Enum): """花色""" SPADE, HEART, CLUB, DIAMOND = range(4) def __lt__(self, other): return self.value < other.value class Card(): """牌""" def __init__(self, suite, face): """初始化方法""" self.suite = suite self.face = face def show(self): """显示牌面""" suites = ['♠️', '♥️', '♣️', '♦️'] faces = ['', 'A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K'] return f'{suites[self.suite.value]} {faces[self.face]}' def __str__(self): return self.show() def __repr__(self): return self.show() class Poker(): """扑克""" def __init__(self): self.index = 0 self.cards = [Card(suite, face) for suite in Suite for face in range(1, 14)] def shuffle(self): """洗牌（随机乱序）""" random.shuffle(self.cards) self.index = 0 def deal(self): """发牌""" card = self.cards[self.index] self.index += 1 return card @property def has_more(self): return self.index < len(self.cards) class Player(): """玩家""" def __init__(self, name): self.name = name self.cards = [] def get_one(self, card): """摸一张牌""" self.cards.append(card) def sort(self, comp=lambda card: (card.suite, card.face)): """整理手上的牌""" self.cards.sort(key=comp) def main(): """主函数""" poker = Poker() poker.shuffle() players = [Player('东邪'), Player('西毒'), Player('南帝'), Player('北丐')] while poker.has_more: for player in players: player.get_one(poker.deal()) for player in players: player.sort() print(player.name, end