写在前面
- 给小伙伴推荐
Python书单，发现了这本书 - 开卷获益，有一种想全部读完,呼之欲出的感受
- 这么好的书在身边，居然都没看过,懊悔不已....
- 遂连夜拜读，受益匪浅，这里整理笔记
- 本文为数据结构和算法章节第二部分
「 我的手机里，最初是有网抑云的，上学时，不开心，会听应景的歌，偶尔看评论，虽不会唱，有种被感同身受。后来，手机存储不够清理，提示卸载不常用的软件就卸载了，恍惚，好久不听歌了，想起在哪看到，有些人二十岁就死了，等到八十岁才被埋。--------山河已无恙」
第一章 数据结构和算法
Python内置了许多非常有用的数据结构，比如列表(list)、集合(set)以及字典(dictionary)、元组(tuple)。在collections模块中也包含了针对各种数据结构的解决方案。
对切片命名
「我们的代码到处都是硬编码的切片索引，我们想将它们清理干净」
即通过对切片变量的定义，把可变的部分抽离出来。一般来说，内置的slice()函数会创建一个切片对象，可以用在任何允许进行切片操作的地方。
>>> recode='343534534532423435346547543534534534534564634534'
>>> int(recode[12:14]) * float(recode[10:13])
13608.0
>>> a = slice(12,14)
>>> b = slice(10,13)
>>> int(recode[a]) * float(recode[b])
13608.0
查看切片对象属性
代码语言：javascript复制>>> a.start
12
>>> a.stop
14
>>> a.step
>>>
通过使用indices(size)方法将切片映射到特定大小的序列上。
代码语言：javascript复制>>> s = "liruilong"
>>> a.indices(len(s))
(9, 9, 1)
>>>
找出序列中出现次数最多的元素
「怎样找出一个序列中出现次数最多的元素呢？」
collections.Counter 类就是专门为这类问题而设计的，它甚至有一个有用的most_common()方法直接给了你答案。
出现频率最高的 3 个单词
代码语言：javascript复制>>> 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'
... ]
>>> from collections import Counter
>>> word_counts = Counter(words)
>>> word_counts.most_common(3)
[('eyes', 8), ('the', 5), ('look', 4)]
>>> word_counts.most_common(1)
[('eyes', 8)]
作为输入，Counter 对象可以接受任意的hashable序列对象。在底层实现上，一个Counter对象就是一个字典，将元素映射到它出现的次数上
>>> word_counts
Counter({'eyes': 8, 'the': 5, 'look': 4, 'into': 3, 'my': 3, 'around': 2, 'not': 1, "don't": 1, "you're": 1, 'under': 1})
>>>
可以整合其他的容器来统计数据,下面为在原有基础上整合一个列表
代码语言：javascript复制>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> for word in morewords:
... word_counts[word] = 1
...
>>> word_counts
Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2, 'around': 2, "don't": 1, "you're": 1, 'under': 1, 'why': 1, 'are': 1, 'you': 1, 'looking': 1, 'in': 1})
>>>
当然，也可以通过update()方法,我们可以看到，update方法并没有替换原来的value，而是进行了累加，和字典的update方法有区别
>>> word_counts.update(morewords)
>>> word_counts
Counter({'eyes': 10, 'my': 5, 'the': 5, 'look': 4, 'into': 3, 'not': 3, 'around': 2, 'why': 2, 'are': 2, 'you': 2, 'looking': 2, 'in': 2, "don't": 1, "you're": 1, 'under': 1})
>>>
Counter生成的数据字典可以进行数据运算，只是针对相同Key的Value而言
代码语言：javascript复制>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> 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'
... ]
>>> from collections import Counter
>>> Counter(words) Counter(morewords)
Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2, 'around': 2, "don't": 1, "you're": 1, 'under': 1, 'why': 1, 'are': 1, 'you': 1, 'looking': 1, 'in': 1})
>>>
通过某个关键字排序一个字典列表
「你有一个字典列表，你想根据某个或某几个字典字段来排序这个列表。」
通过使用 operator 模块的 itemgetter 函数，可以非常容易的排序这样的数据结构。感觉和heapq模块中的函数nlargest()和nsmallest()有些类似
>>> rows = [
... {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
... {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
... {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
... {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
... ]
>>> from operator import itemgetter
>>> sorted(rows, key=itemgetter('fname'))
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]
rows 被传递给接受一个关键字参数的sorted()内置函数,参数是 callable 类型，从rows中接受一个单一元素，然后返回被用来排序的值,itemgetter() 函数就是负责创建这个 callable 对象的。
>>> sorted(rows, key=itemgetter('uid'))
[{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}]
itemgetter() 函数也支持多个 keys，如果你传入多个索引参数给 itemgetter() ，它生成的 callable 对象会返回一个包含所有元素值的元组，并且 sorted() 函数会根据这个元组中元素顺序去排序比如下面的代码
>>> sorted(rows, key=itemgetter('lname','fname'))
[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>>
itemgetter() 有时候也可以用 lambda 表达式代替
代码语言：javascript复制>>> sorted(rows, key=lambda r: r['fname'])
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]
>>> sorted(rows, key=lambda r: (r['lname'],r['fname']))
[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>>
使用 itemgetter() 方式会运行的稍微快点。同样适用于 min() 和 max() 等函数
代码语言：javascript复制>>> import heapq
>>> heapq.nsmallest(2,rows,key=itemgetter('fname'))
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>> min(rows,key=itemgetter('fname'))
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>>>
排序不支持原生比较的对象
「你想排序类型相同的对象，但是他们不支持原生的比较操作」
内置的 sorted() 函数有一个关键字参数 key ，可以传入一个 callable 对象给它,这个 callable 对象对每个传入的对象返回一个值，这个值会被 sorted 用来排序
代码语言：javascript复制#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File : user.py
@Time : 2022/04/29 19:35:33
@Author : Li Ruilong
@Version : 1.0
@Contact : 1224965096@qq.com
@Desc : None
"""
# here put the import lib
class User:
def __init__(self, user_id):
self.user_id = user_id
def __repr__(self):
return 'User({})'.format(self.user_id)
def sort_notcompare():
users = [User(23), User(3), User(99)]
print(users)
print(sorted(users, key=lambda u: u.user_id))
if __name__ == "__main__" :
sort_notcompare()
============
[User(23), User(3), User(99)]
[User(3), User(23), User(99)]
另外一种方式是使用 operator.attrgetter() 来代替 lambda 函数：
代码语言：javascript复制 from operator import attrgetter
print(sorted(users, key=attrgetter('user_id')))
attrgetter() 函数通常会运行的快点，并且还能同时允许多个字段进行比较
代码语言：javascript复制sorted(users, key=attrgetter('last_name', 'first_name'))
跟 operator.itemgetter() 函数作用于字典类型很类似 ,同样适用于像 min() 和 max() 之类
通过某个字段将记录分组
「你有一个字典或者实例的序列，然后你想根据某个特定的字段比如 date 来分组迭代访问。」
itertools.groupby() 函数对于这样的数据分组操作非常实用。为了演示，假设你已经有了下列的字典列表
代码语言：javascript复制>>> rows = [
... {'address': '5412 N CLARK', 'date': '07/01/2012'},
... {'address': '5148 N CLARK', 'date': '07/04/2012'},
... {'address': '5800 E 58TH', 'date': '07/02/2012'},
... {'address': '2122 N CLARK', 'date': '07/03/2012'},
... {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
... {'address': '1060 W ADDISON', 'date': '07/02/2012'},
... {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
... {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
... ]
>>> from operator import itemgetter
>>> from itertools import groupby
>>> rows.sort(key=itemgetter('date'))
>>> for date, items in groupby(rows, key=itemgetter('date')):
... print(date)
... for i in items:
... print(' ', i)
...
07/01/2012
{'address': '5412 N CLARK', 'date': '07/01/2012'}
{'address': '4801 N BROADWAY', 'date': '07/01/2012'}
07/02/2012
{'address': '5800 E 58TH', 'date': '07/02/2012'}
{'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'}
{'address': '1060 W ADDISON', 'date': '07/02/2012'}
07/03/2012
{'address': '2122 N CLARK', 'date': '07/03/2012'}
07/04/2012
{'address': '5148 N CLARK', 'date': '07/04/2012'}
{'address': '1039 W GRANVILLE', 'date': '07/04/2012'}
>>>
groupby()函数扫描整个序列并且查找连续相同值(或者根据指定key函数返回值相同)的元素序列。在每次选代的时候,它会返回一个值和一个选代器对象,这个选代器对象可以生成元素值全部等于上面那个值的组中所有对象。
「一个非常重要的准备步骤是要根据指定的字段将数据排序」 。因为groupby()仅仅检查连续的元素
如果你仅仅只是想根据date字段将数据分组到一个大的数据结构中去,并且允许随机访问,最好使用defaultdict()来构建一个多值字典
>>> from collections import defaultdict
>>> rows_by_date = defaultdict(list)
>>> rows = [
N CLARK', 'date': '07/03/... {'address': '5412 N CLARK', 'date': '07/01/2012'},
... {'address': '5148 N CLARK', 'date': '07/04/2012'},
... {'address': '5800 E 58TH', 'date': '07/02/2012'},
... {'address': '2122 N CLARK', 'date': '07/03/2012'},
... {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
... {'address': '1060 W ADDISON', 'date': '07/02/2012'},
... {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
... {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
... ]
>>> for row in rows:
... rows_by_date[row['date']].append(row)
...
>>> rows_by_date
defaultdict(<class 'list'>,
{'07/01/2012': [
{'address': '5412 N CLARK', 'date': '07/01/2012'
},
{'address': '4801 N BROADWAY', 'date': '07/01/2012'
}
], '07/04/2012': [
{'address': '5148 N CLARK', 'date': '07/04/2012'
},
{'address': '1039 W GRANVILLE', 'date': '07/04/2012'
}
], '07/02/2012': [
{'address': '5800 E 58TH', 'date': '07/02/2012'
},
{'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'
},
{'address': '1060 W ADDISON', 'date': '07/02/2012'
}
], '07/03/2012': [
{'address': '2122 N CLARK', 'date': '07/03/2012'
}
]
})
>>>
过滤序列元素
「你有一个数据序列，想利用一些规则从中提取出需要的值或者是缩短序列」
最简单的过滤序列元素的方法就是使用列表推导
代码语言：javascript复制>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> [n for n in mylist if n > 0]
[1, 4, 10, 2, 3]
>>> [n for n in mylist if n < 0]
[-5, -7, -1]
>>>
潜在缺陷就是如果输入非常大的时候会产生一个非常大的结果集，占用大量内存,可以用生成器表达式迭代产生过滤的元素。
代码语言：javascript复制>>> pos = (n for n in mylist if n > 0)
>>> pos
<generator object <genexpr> at 0x7f3a14e538e0>
>>> for i in pos:
... print(i)
...
1
4
10
2
3
>>>
过滤规则比较复杂,将过滤代码放到一个函数中，然后使用内建的filter()函数
values = ['1', '2', '-3', '-', '4', 'N/A', '5']
def is_int(val):
try:
x = int(val)
return True
except ValueError:
return False
# filter() 函数创建了一个迭代器
ivals = list(filter(is_int, values))
print(ivals)
在过滤的时候转换数据
代码语言：javascript复制>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> import math
>>> [math.sqrt(n) for n in mylist if n > 0]
[1.0, 2.0, 3.1622776601683795, 1.4142135623730951, 1.7320508075688772]
>>>
过滤操作的一个变种就是将不符合条件的值用新的值代替，
代码语言：javascript复制>>> [n if n > 0 else 0 for n in mylist]
[1, 4, 0, 10, 0, 2, 3, 0]
>>> [n if n < 0 else 0 for n in mylist]
[0, 0, -5, 0, -7, 0, 0, -1]
>>>
itertools.compress(),它以一个 iterable 对象和一个相对应的 Boolean 选择器序列作为输入参数.然后输出 iterable 对象中对应选择器为 True 的元素当你需要用另外一个相关联的序列来过滤某个序列的时候，这个函数是非常有用的
>>> addresses = [
... '5412 N CLARK',
... '5148 N CLARK',
... '5800 E 58TH',
... '2122 N CLARK'
... '5645 N RAVENSWOOD',
... '1060 W ADDISON',
... '4801 N BROADWAY',
... '1039 W GRANVILLE',
... ]
>>> counts = [ 0, 3, 10, 4, 1, 7, 6, 1]
>>> from itertools import compress
>>> more5 = [n > 5 for n in counts]
>>> more5
[False, False, True, False, False, True, True, False]
>>> list(compress(addresses, more5))
['5800 E 58TH', '4801 N BROADWAY', '1039 W GRANVILLE']
>>>
compress() 也是返回的一个迭代器
从字典中提取子集
「你想构造一个字典，它是另外一个字典的子集」
是使用字典推导
代码语言：javascript复制>>> prices = {
... 'ACME': 45.23,
... 'AAPL': 612.78,
... 'IBM': 205.55,
... 'HPQ': 37.20,
... 'FB': 10.75
... }
>>> {key: value for key, value in prices.items() if value > 200}
{'AAPL': 612.78, 'IBM': 205.55}
>>> tech_names = {'AAPL', 'IBM', 'HPQ', 'MSFT'}
>>> {key: value for key, value in prices.items() if key in tech_names}
{'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.2}
>>>
字典推导能做到的，通过创建一个元组序列然后把它传给 dict()也能实现,字典推导方式表意更清晰，并且实际上也会运行的更快些
dict((key, value) for key, value in prices.items() if value > 200)
将名称映射到序列的元素中
「你有一段通过下标访问列表或者元组中元素的代码，但是这样有时候会使得你的代码难以阅读，于是你想通过名称来访问元素。」
collections.namedtuple() 函数通过使用一个普通的元组对象来帮你解决这个问题。
代码语言：javascript复制>>> from collections import namedtuple
>>> Subscriber = namedtuple('Subscriber', ['addr', 'joined'])
>>> sub = Subscriber('jonesy@example.com', '2012-10-19')
>>> sub
Subscriber(addr='jonesy@example.com', joined='2012-10-19')
namedtuple() 返回 Python 中标准元组类型子类的一个工厂方法,传递一个类型名和你需要的字段给它，然后它就会返回一个类,虽然看起来像一个类实例，但是是可交换的。
>>> sub.addr
'jonesy@example.com'
>>> sub[1]
'2012-10-19'
>>> addr, joined = sub
>>> addr
'jonesy@example.com'
>>>
命名元组的一个主要用途是将你的代码从下标操作中解脱出来,数据查询中返回很大一个元组，通过下标去操作其中的元素有很多可变性，如果使用元组命名则不用考虑
代码语言：javascript复制def compute_cost(records):
total = 0.0
for rec in records:
total = rec[1] * rec[2]
return total
from collections import namedtuple
Stock = namedtuple('Stock', ['name', 'shares', 'price'])
def compute_cost(records):
total = 0.0
for rec in records:
s = Stock(*rec)
total = s.shares * s.price
return total
命名元组另一个用途就是作为字典的替代，字典存储需要更多的内存空间
需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效
是需要注意一个命名元组是不可更改的.如果你真的需要改变后的属性，那么可以使用命名元组实例的replace()方法
>>> sub
Subscriber(addr='jonesy@example.com', joined='2012-10-19')
>>> sub.addr
'jonesy@example.com'
>>> sub.addr = '1@qq.com'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: can't set attribute
>>> sub = sub._replace(addr='1@qq.com')
>>> sub
Subscriber(addr='1@qq.com', joined='2012-10-19')
>>>
它会创建一个全新的命名元组并将对应的字段用新的值取代
_replace() 方法还有一个很有用的特性就是当你的命名元组拥有可选或者缺失字段时候，它是一个非常方便的填充数据的方法。你可以先创建一个包含缺省值的原型元组，然后使用 _replace() 方法创建新的值被更新过的实例,类似于类实例的初始化调用构造函数
>>> from collections import namedtuple
>>> Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time'])
>>> stock_prototype = Stock('', 0, 0.0, None, None)
>>> def dict_to_stock(s):
... return stock_prototype._replace(**s)
...
>>> a = {'name': 'ACME', 'shares': 100, 'price': 123.45}
>>> dict_to_stock(a)
Stock(name='ACME', shares=100, price=123.45, date=None, time=None)
>>> b = {'name': 'ACME', 'shares': 100, 'price': 123.45, 'date': '12/17/2012'}
>>> dict_to_stock(b)
Stock(name='ACME', shares=100, price=123.45, date='12/17/2012', time=None)
>>>
如果你的目标是定义一个需要更新很多实例属性的高效数据结构，那么命名元组并不是你的最佳选择。这时候你应该考虑定义一个包含 slots 方法的类
同时对数据做转换和换算
「我们需要调用一个换算(reduction)函数(例如sumO、min)、max))，但首先得对数据做转换或筛选。」
代码语言：javascript复制>>> num = [1,2,3,4,5]
>>> sum(x * x for x in num)
55
>>>
将多个映射合并为单个映射
「我们有多个字典或映射，想在逻辑上将它们合并为一个单独的映射结构，以此执行某些特定的操作，比如查找值或检查键是否存在。」
一种简单的万法是利用collections模块中的ChainMap类来解决
>>> a={'x':1,'z':3}
>>> b={'y':2,'z':4}
>>> from collections import ChainMap
>>> ChainMap(a,b)
ChainMap({'x': 1, 'z': 3}, {'y': 2, 'z': 4})
>>>
ChainMap可接受多个映射然后在逻辑上使它们表现为一个单独的映射结构。但是，这些映射在字面上并不会合并在一起。相反，ChainMap只是简单地维护一个记录底层映射关系的列表，然后重定义常见的字典操作来扫描这个列表。大部分的操作都能正常工作。
>>> len(ChainMap(a,b))
3
>>> list(ChainMap(a,b).keys())
['y', 'z', 'x']
>>> list(ChainMap(a,b).values())
[2, 3, 1]
>>>
如果有重复的键，那么这里会采用第一个映射中所对应的值。修改映射的操作总是会作用在列出的第一个映射结构上。
ChainMap与带有作用域的值，比如编程语言中的变量(即全局变量、局部变量等)一起工作时特别有用。
>>> v = ChainMap()
>>> v['x'] = 1
>>> v = v.new_child()
>>> v['x'] = 2
>>> v = v.new_child()
>>> v['x'] = 3
>>> v
ChainMap({'x': 3}, {'x': 2}, {'x': 1})
>>> v['x']
3
>>> v = v.parents
>>> v['x']...............
2
>>> v = v.parents
>>> v['x']
1
>>> v
ChainMap({'x': 1})
>>>
作为ChainMap的替代方案，我们可能会考虑利用字典的update()方法将多个字典合并在一起。但是破坏了原始的数据结构，而ChainMap使用的就是原始的字典，因此它不会产生这种令人不悦的行为。
>>> a
{'x': 1, 'z': 3}
>>> b
{'y': 2, 'z': 4}
>>>
>>> c= dict(b)
>>> c.update(a)
>>> c
{'y': 2, 'z': 3, 'x': 1}
