数据结构和算法
1，将序列分解成单独的变量
-
问题：需要把N个元素组成的元祖和序列，分解成N个单独的变量
-
解决方案：使用拆包的方式分解可迭代对象
>>> p = (4, 5) >>> a, b = p >>> a 4 >>> b 5 >>> data = ['xyb', 18, 180, ('mmm', 20, 165)] >>> name, age, tall, another = data >>> name 'xyb' >>> another ('mmm', 20, 165)不仅仅是元组和列表，只要是可迭代对象，都是可以进行分解操作的，包括字符串，文件，迭代器、、
>>> s = '1,2,3' >>> a, _, b, _, c = s >>> a '1' >>> b '2' >>> c '3' -
掌握：不需要的数据用
_来丢弃
2，从任意长度的可迭代对象中分解元素
-
问题 ：需要从某个可迭代对象中分解N个对象，但是这个对象的长度可能超过了N，会异常
-
解决方案 ：使用
*来配合拆包使用>>> data = ['xyb', 18, 13586971744, 19857100635] >>> name, age, *number = data >>> name 'xyb' >>> number [13586971744, 19857100635] -
掌握 ：通过
*_截取未知的数据>>> one, *_, last = socres >>> one 1 >>> last 8 >>> _ [5, 6, 7, 8, 10, 64, 21]
3，使用双向队列进行历史记录
-
问题 ：我们希望在迭代或者其他形式下保留最后几次时间内的记录，即历史记录
-
解决方案 ：使用双向队列 deque 来协助我们完成
from collections import deque # 1. 不给队列最大值，队列无限大 >>> q = deque() >>> q.append(5) >>> q.append(6) >>> q.append(7) >>> q.appendleft(0) >>> q deque([0, 5, 6, 7]) >>> q.pop() 7 # 2. 给了最大值 >>> q = deque(maxlen=3) >>> q.append(1) >>> q.append(2) >>> q.append(3) >>> q deque([1, 2, 3], maxlen=3) >>> q.append(4) >>> q deque([2, 3, 4], maxlen=3) -
在双向队列中，队列两端 添加 和 弹出 的复杂度都是O[1]
4，找到最大或最小的N个元素
-
问题 ：在集合中找出最大或最小的N个元素
-
解决方案 ：使用 heapq 模块中的两个函数–nlargest()–和--nsmallest()
>>> import heapq >>> nums = [1, 2, 5, 6, -8, 15, -32, 24, 6, 42, 0] >>> heapq.nlargest(3, nums) [42, 24, 15] >>> heapq.nsmallest(3, nums) [-32, -8, 0] # 1. 他还能接受一个key，从而在更复杂的数据结构上进行操作 >>> data = [ ... {'name': 'xyb', 'age': 18}, ... {'name': 'habby', 'age': 10}, ... {'name': 'yollw', 'age': 26} ... ] >>> heapq.nlargest(2, data, key=lambda x: x['age']) [{'name': 'yollw', 'age': 26}, {'name': 'xyb', 'age': 18}] >>> heapq.nsmallest(2, data, key=lambda x: x['age']) [{'name': 'habby', 'age': 10}, {'name': 'xyb', 'age': 18}] -
扩展 ：如果要寻找的数据N远远小于总数据，那么heapq.heapify()会有更好的性能
>>> nums = [4, 5, 6, 8, 2, 5, -5, -48, 0, -31, 51] >>> heap = heapq.heapify(nums) >>> heap = list(nums) >>> heapq.heapify(heap) # 底层以栈堆的顺序排列 >>> heap [-48, -31, -5, 0, 2, 5, 6, 8, 5, 4, 51] >>> heapq.heappop(heap) -48 >>> heapq.heappop(heap) -31 >>> heapq.heappop(heap) -5 >>> heapq.heappop(heap) 0 >>> heapq.heappop(heap) 2 >>> heapq.heappop(heap) 4
5，将一个键映射到多个值上面
-
问题：字典的每个键都能映射多个值
-
解决方案：创建 defaultdict(list) 这个字典
>>> d = defaultdict(list) >>> d['a'].append(1) >>> d defaultdict(<class 'list'>, {'a': [1]}) >>> d['b'].extend([1,2,3]) >>> d defaultdict(<class 'list'>, {'a': [1], 'b': [1, 2, 3]})
6，对字典的值进行比较
-
问题：我们想在字典上对数据进行各式各样的操作(求最大值，最小值，排序等)
-
prices = { 'apple': 42.6, 'binana': 42.6, 'piple': 42.6, 'aaa': 42.6, } # 1. 最大值，最小值 min(zip(prices.values(), prices.keys())) max(zip(prices.values(), prices.keys())) # 2. 按照值进行排序 sorted(zip(prices.values(), prices.keys()))解决方案② ：对 min 和 max 函数传递 key 这个参数
prices = { 'apple': 42.6, 'binana': 42.6, 'piple': 42.6, 'aaa': 42.6, } # 1. 返回键名 min(prices, key=lambda k: prices[k]) max(prices, key=lambda k: prices[k])
7，寻找两个字典的相同点
-
问题 ：有两个字典，我们想要在两个字典中找出他们的共同点（相同的键，值）
-
解决方案 ：用字典的 keys() 和 values() 来进行集合的操作，
字典的 keys 支持集合操作k1 = { 'x': 10, 'y': 15, 'z': 20, 'b': 80 } k2 = { 'w': 10, 'y': 15, 'z': 30, 'b': 80 } # 1. 两个字典相同的key k1.keys() & k2.keys() # 2. 两个字典key相同，value相同的项 k1.items() & k2.items() # 3. 过滤一个字典的某些项 {key: k1[key] for key in k1.keys() - {'b', 'z'}} k1 = { 'x': 10, 'y': 15, }
8，从序列中删除重复项且保持元素键顺序不变
-
问题：去除序列中重复项，并且保持序列的顺序不变
-
解决方案1 ：通过集合+生成器的方式实现（元素可以被hash时，能实现
__hash__的对象）def dedupe(items): seen = set() for item in items: if item not in seen: yield item seen.add(item) -
解决方案2 ：通过集合+生成器的方式实现（元素可以被hash时，能实现
__hash__的对象）def dedupe(items, key=None): seen = set() for item in items: val = item if key is None else key(item) # 关键一步 if val not in seen: yield val seen.add(val) -
高级用法：对于高级的数据类型，照样能够去重
a = [{'a': 1, 'y': 2}, {'a': 1, 'y': 6}, {'a': 1, 'y': 2}, {'a': 1, 'y': 2}] list(dedupe(a, key=lambda d: (d['a'], d['y'])))
9，对切片命名
-
问题：代码中有很多的 [0: 5, 2], [-4, -3, -1] 这样的硬编码切片，不容易我们回过头来看代码.
-
解决方案：利用
slice函数对切片命名s = [1, 2, 3, 4, 5, 6, 7] head = slice(0, 4, 1) s[head] # [1, 2, 3, 4] head.start # 0 head.stop # 4 head.step # 1 -
拓展 ：使用
indices能够固定一段长度，所有值都必须在一个边界范围内s = [1, 2, 3, 4, 5, 6, 7] head = slice(0, 5, 2) print(head.indices(len(s))) # (0, 5, 1) for i in range(*head.indices(len(s))): print('下表', i) print('值', s[i]) """ 下表 0 值 1 下表 2 值 3 下表 4 值 5 """
10，找出序列中频率最高的元素
-
问题 ：有一个元素序列，求出现次数最多的元素是什么
-
解决方案 ：利用
collection.Counter能够轻松实现-
most_counter() 找出频率最高的三个元素
from collections import Counter word = ['a', 'a', 'b', 'c', 'c', 'd'] counter = Counter(word) counter.most_common(2) # [('a', 2), ('c', 2)] counter['a'] # 查看次数 2 counter['d'] # 查看次数 1 -
Counter 的其他用法，counter 底层维护的是一个字典
# 1. 因为counter背后维护的是一个字典，用字典的赋值方式 s = ['a', 'b', 'c', 'd', 'a', 'b', 'c'] counter = Counter() for i in s: counter[i] += 1 print(counter) # Counter({'a': 2, 'b': 2, 'c': 2, 'd': 1}) # 2. 进行两个counter的数学计算 a = ['a', 'b', 'c', 'd'] b = ['b', 'c', 'e', 'h'] counter_a = Counter(a) counter_b = Counter(b) counter_a + counter_b # Counter({'a': 1, 'b': 2, 'c': 2, 'd': 1, 'e': 1, 'h': 1})
-
11，通过公共键对字典列表排序
-
问题 ：有一个字典列表，根据一个或多个字典中的值来对列表排序
-
解决方案①：使用 operator 中的 itemgetter 函数来排序
rows = [ {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'} ] from operator import itemgetter rows_by_fname = sorted(rows, key=itemgetter('fname')) rows_by_uid = sorted(rows, key=itemgetter('uid')) # 通过多行进行排序 rows_by_fname_uid = sorted(rows, key=itemgetter('lname', 'uid')) ...... [{'fname': 'B', 'iname': 'bbb', 'uid': '1006'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}] [{'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}]解决方案② 是要用
lambda + sorted，性能比上面的要慢一点rows = [ {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'} ] from operator import itemgetter rows_by_fname = sorted(rows, key=lambda k: k['fname']) rows_by_uid = sorted(rows, key=lambda k: k['uid']) # 通过多行进行排序 rows_by_fname_uid = sorted(rows, key=lambda x:(x['fname'], x['uid'])) ...... [{'fname': 'B', 'iname': 'bbb', 'uid': '1006'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, {'fname': 'D', 'iname': 'ddd', 'uid': '1000'}] [{'fname': 'D', 'iname': 'ddd', 'uid': '1000'}, {'fname': 'C', 'iname': 'aaa', 'uid': '1001'}, {'fname': 'C', 'iname': 'ccc', 'uid': '1002'}, {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}] -
拓展 ：
itemgetter和lambda的方法照样能够运用到 max 和 min 这两个函数上max(rows, key=lambda k: k['uid']) max(rows, key=itemgetter('uid')) {'fname': 'B', 'iname': 'bbb', 'uid': '1006'}
12，通过实例属性对实例排序
-
问题 ：对一个类的多个实例通过实例属性排序
-
解决方案 ：通过对 sorted 的 key 键传值，使用
lambda或者attrgetterfrom operator import itemgetter class User: def __init__(self, user_id): self.id = user_id def __repr__(self): return 'User ({})'.format(self.id) users = [User(5), User(10), User(8), User(1)] sorted(users, key=lambda u: u.id) sorted(users, key=attrgetter('id')) # [User (1), User (5), User (8), User (10)] -
拓展 ：
attrgetter和lambda的方法照样能够运用到 max 和 min 这两个函数上max(users, key=lambda u: u.id) max(users, key=attrgetter('u')) User (10)
13，根据字段将记录分组
-
解决 ：有一系列的字典或实例对象，根据某个特点的字段(比如日期)，来进行分组迭代
-
解决方案① ：通过
itertools.groupby()来对数据进行分组rows = [ {'address': '5412 N CLARK', 'date': '07/01/2012'}, {'address': '5254 E CLARK', 'date': '07/01/2012'}, {'address': '5312 N CLARK', 'date': '07/02/2012'}, {'address': '5482 S CLARK', 'date': '07/03/2012'}, {'address': '5484 N CLARK', 'date': '28/02/2012'} ] from itertools import groupby from operator import itemgetter rows.sort(key=itemgetter('date')) # 这一步必须排序，否则分组会出错 for date, items in groupby(rows, key=itemgetter('date')): print(date) for i in items: print(' '*4, i) -
解决方案② ：如果只是单存的对数据进行分组，不考虑内存，用
collections.defaultdictfrom collections import defaultdict rows_by_date = defaultdict(list) for row in rows: rows_by_date[row['date']].append(row) rows_by_date
14，筛选序列中的元素
-
问题 ： 序列中有些数据是我们需要的，有些是不需要的，根据特定条件筛选
-
解决方案① ：使用
列表推导式（原生输入不是很大的情况下）>>> my_list = [1, 2, 3, -5, 2, -10, -9, -12, 15] >>> [i for i in my_list if i > 0] [1, 2, 3, 2, 15] >>> [i for i in my_list if i < 0] [-5, -10, -9, -12] -
解决方案② ：输入数据非常大，使用
生成器表达式，惰性产生值>>> res = (i for i in my_list if i < 0) >>> res <generator object <genexpr> at 0x0000023C252D0E08> >>> for i in range(6): ... print(i) ... 0 1 2 3 4 5 -
解决方案③ ：筛选条件过于复杂，写成函数用
filter()函数进行过滤items = [', ', '**6', '-', '125', 'ss5', '12', '-10'] def parse(item): try: if int(item) > 10: return True except Exception: return False list(filter(parse, items)) # ['125', '12']-
拓展① ：生成表达式\列表推到式的
数值转换，三目运算# 1. 数值转换 >>> s = [1, 2, 5, 4, 6, 1, 3, 7] >>> [i**2 for i in s] [1, 4, 25, 16, 36, 1, 9, 49] # 2. 三目运算 >>> s = ['1', '2', 'd', 'aa', '6.6', '0.2', '**'] >>> [i if i.isdigit() else None for i in s] ['1', '2', None, None, None, None, None] -
拓展② ：
布尔序列+itertools.compress进行筛选，数据超出布尔列表不予计算from itertools import compress data = [ 'aa1', 'aa2', 'aa3', 'aa4', 'aa5', 'aa6', 'aa7', 'aa8', 'aa9', 'aa10' ] s = [1, 2, 5, 4, 6, 1, 3, 7] bool_list = [n > 5 for n in s] # [False, False, False, False, True, False, False, True] list(compress(data, bool_list)) # ['aa5', 'aa8']
-
15，从字典中提取值创建字典
-
问题 ：我们需要创建一个字典，其本身是另外一个字典的子集
-
解决方案① ：利用
字典推导式d = { 'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6 } {key: value for key, value in d.items() if value > 3} # {'d': 4, 'e': 5, 'f': 6} {key: value for key, value in d.items() if key in ['a', 'b', 'c']} # {'a': 1, 'b': 2, 'c': 3} -
解决方案② ：用
dict函数强制转换元组序列，速度比第一种快 2 倍！dict((k, v) for k, v in d.items() if v > 2) # {'c': 3, 'd': 4, 'e': 5, 'f': 6} -
解决方案③ ：比方案②更深奥的写法，
字典取值生成，比第一种快 1.6 倍key = {'a', 'b', 'c'} {key: d[key] for key in d.keys() & key} # 对key进行了一次交集运算 # {'c': 3, 'b': 2, 'a': 1}
16，给元组的值命名
-
问题 ：我们的代码是通过下表来访问元组或列表的，但是有时候会让我们难以阅读，我们希望像访问实例的属性那样访问元组的内容
-
解决方案① ：相对普通的元组，使用
nametuple命名元祖，只是增加极小的空间就能实现>>> from collections import namedtuple >>> User = namedtuple('User', ['name', 'gender', 'age']) >>> a = User('a', 'M', 20) >>> a.name 'a' >>> a.age 20尽管他看起来像创建了一个类并且做了一个实例化的操作，但是他支持普通元组的所有操作，列如索引和分解，拆包等等
nametuple 的别处用法，利用for循环解包数据创造命名元组
data = [ ('a', 1, 5), ('b', 6, 3), ('c', 2, 5), ('d', 3, 7), ('e', 4, 8), ] # 1. 不用命名元组，用下表取值，语义表达不明确 def comput_cost(records): total = 0.0 for rec in records: total += rec[1] * rec[2] return total comput_cost(data) # 86.0 # 2. 使用命名元组，拆包形式生成 User = namedtuple('User', ['name', 'data1', 'data2']) def comput_cost(records): total = 0.0 for rec in records: user = User(*rec) total += user.data1 * user.data2 return total # 86.0 -
拓展用法① ：
替代字典使用，占用内存更加小，比使用 __ slits __() 属性的类低那么一点# ！！！ 使用 nametuple 创建的替代字典用法需要是要内置 _replace() 方法才能修改值 >>> a = User('xyb', 20, 'F') >>> a.age = 21 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: can't set attribute >>> a._replace(age=21) User(name='xyb', age=21, gender='F') # 修改成功 -
拓展用法② ：用
_replace配合字典创建默认值的元组User = namedtuple('User', ['name', 'age', 'gender', 'number', 'date']) default_user = User('', '', '', None, None) def dict_to_tuple(d): return default_user._replace(**d) d = {'name': 'xyb', 'age': 20} dict_to_tuple(d) # User(name='xyb', age=20, gender='', number=None, date=None)
17，生成器表达式作为函数单独参数
-
问题 ：我们需要调用一个换算函数，但是首先得对数据做转换和筛选
-
解决思路 ：在
函数中使用生成器表达式# 1. 列如 sum 函数 nums = [1, 2, 3, 4, 5] sum(x * x for x in nums) # 2. any函数（只要传入的iterable对象的元素中有一个True就返回True） import os files = os.listdir() if any(name.endswith('.py') for name in files): print('python file') else: print('sorry no python') # 3. 比出最大值 data = [ {'name': 'A', 'age': 64}, {'name': 'B', 'age': 28}, {'name': 'C', 'age': 36}, {'name': 'D', 'age': 15}, ] min(item['age'] for item in data) # 4. 输出 CSV s = ['i', 'love', 'a', 'girl'] print(','.join(item) for item in s) -
分析 ：
为什么生成器表达式能直接作为函数的参数>>> nums = [1, 2, 3, 4, 5, 6] >>> s = sum(x * x for x in nums) >>> s 91 >>> s = sum((x * x for x in nums)) >>> s 91 # !!! 有没有 () 效果都是一样的 -
掌握 ：通过用生成器表达式替换函数中的 key
data = { 'a': 20, 'b': 25, 'c': 15, 'd': 30 } min(data[item] for item in data) min(data, key=lambda k: data[k])
18，将多个字典合并成单个字典
-
问题 ：有多个字典或映射，在逻辑上将他们合并成一个单独的结构，执行某种特定的操作，比如查找键，值是否存在
-
解决方案 ：使用
collections.ChainMap将两个字典从底层联系起来a = {'a': 1, 'b': 1} b = {'c': 1, 'b': 2} from collections import ChainMap c = ChainMap(a, b) len(c) list(c.keys()) # ['b', 'c', 'a'] list(c.values()) # [1, 1, 1]-
如果有两个字典有相同的键，值以第一个字典的键为准
-
如果要删除组合字典里面的键值对，只能移除第一个映射或者字典上
del c['a'] # √ del c['c'] # ×
-