跟着官网学Python(6)非常重要的数据结构

数据结构"/>

跟着官网学Python(6)非常重要的数据结构

“数据结构是一个语言的基础，非常重要。”

01 面临问题

继续跟着官网学Python，第5章数据结构。
前面学完流程控制基本能够实现某些功能脚本了，但是要想实现更多功能，必须要掌握数据结构，只有合理使用不能数据结构，才能高效解决问题。
有些时候某些问题的关键就是设计一个数据结构。
首先一起看看Python自带的数据结构。

02 怎么办

Python内置的常用数据结构有列表、元组、集合和字典，他们都是Python的序列，必须要区分的非常清楚，合理利用。

列表list更多特性

前面已经使用列表的一些方法，这里有必要把常用方法再列一下。

• list.append(x)在列表的末尾添加一个元素x
• list.extend(iterable)在列表的末尾添加可迭代对象iterable的所有元素
• list.insert(i,x)在列表的给定位置i插入一个元素x
• list.remove(x)移除列表中第一个值为x的元素，如果没有抛出ValueError异常
• list.pop([i])删除列表给定位置i的元素并返回该元素,[]表示参数可选，如果没有参数则删除并返回最后一个元素，等价于-1
• list.clear()移除列表中所有元素，等价于 del a[:]
• list.index(x,[start,[end,]]) 返回列表中第一个值为x的索引(从0开始编号)，如果没有抛出ValueError异常，其中可选参数start、end通过切片符合限制查找范围，返回索引还是整体的。
• list.count(x)返回元素x在列表中出现的次数
• list.sort(key=None,reverse=False)对元素列表进行排序，参数key可以自定义排序方式
• list.reverse()翻转列表中的元素
• list.copy()返回列表的一个浅拷贝

可以结合代码看看

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Find next banana starting a position 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

insert、remove、sort等方法修改列表，没有返回值，这是Python可变对象的设计原则。
其他语言还有类似栈、队列等数据结构，python中列表也可以类似。
列表作为栈使用
列表的append()和pop()方法配合可以快速实现栈的功能，最后一个插入，最先取出(后进先出)

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

千万不要自作聪明stack = stack.append(6)

列表也可以作为队列(先进先出)使用，但是在列表头部插入和取出操作非常浪费性能，因为后面每位都要移动，不建议。
如果想使用队列，建议使用专门的数据模型
from collections import deque
collections这个

列表推导式
如何快速生成一个新的列表，或者任意一个新的数据结构非常关键。
比如产生0到9的平方数列表，可以用前面学到的for循环实现.

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

更一般的，我喜欢Python中的列表推导式，不仅列表，每个python序列都有推导式。

squares = [x**2 for x in range(10)]

多么简洁，非常喜欢Python这个功能。
列表推导式由一个表达式加for子句，后面跟0个或多个for或if子句，外面是一对中括号，表示生产一个新列表。

#两个列表元素不对则配对
>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
#选择10以内偶数
>>> [x for x in range(10) if x %2 ==0]
[0,2,4,6,8]
#如果不是偶数 乘以2 那么注意if else 要在for之前
>>> [x if x %2 ==0 else 2*x for x in range(10)]
[0, 2, 2, 6, 4, 10, 6, 14, 8, 18]
#列表表达式可以嵌套列表表达式  如交互矩阵的行和列
>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]
>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

不过复杂场景我一般分开写，可读性更好。

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

元组tuple和序列

和列表类似，元组也是一种序列，逗号分隔，圆括号包围，偶尔可以省略括号(不建议)。

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
... t[0] = 88888
Traceback (most recent call last):File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

关于元组，以下关键点必须掌握：

• 元组是不可变类型，不可以对某个元素进行赋值
• 元组元素可以是可变类型，如一个列表
• 元组中元素类型可以不一样
• 元组也可以嵌套，有多层元组
• 元组打包和解包要掌握，解包时左侧变量数必须与元组元素个数相同。t = 12345, 54321, 'hello!'和x, y, z = t
• 0个或1个元组初始化要注意 ()表示空元组,(1,)表示一个元素的元组，注意逗号。

很多时候函数fun返回多个值时，如果不小心直接a = fun()，此时a是一个元组，然后如果不注意直接当成普通变量处理，肯定出错。
和列表一样，元组也支持推导式，把中括号换成圆括号就可以

集合set

前面列表或元组中的元素都可以重复，那么元素不能重复的序列就是集合。
集合可以帮我们消除重复元素，我经常set(list)实现去重。
两个集合可以可以求并集、交集、差集，比如在爆破Base64字符表时，可以将原先64个字符的集合减去已爆破的字符，直接得到未知的，无需像之前一样写循环。
还记得以前学过的集合的性质:确定性、互异性、无序性。
一个元素要么属于一个集合，要么不属于，in关键句非常快。
集合中元素不能重复，集合中元素顺序不重要。
两个集合A和B相等就是每个元素都一样。
初始化集合

a = set()
a = {1,'a'}
a = set([1,'a'])

注意初始空集合必须set(),因为{}是初始化空字典。
同时set()只能接受一个参数，一个可迭代参数，把每个元素去重转为集合，set(1,2)会报错。

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a      # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b     # 差集letters in a but not in b
{'r', 'd', 'b'}
>>> a | b     # 并集letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b     # 交集letters in both a and b
{'a', 'c'}
>>> a ^ b     # 对称差letters in a or b but not both
{'r', 'd', 'b', 'm', 'z', 'l'}

和列表一样，集合也支持推导式，把中括号换成大括号就可以
{x for x in 'abracadabra' if x not in 'abc'}

字典dict

其实不同数据结构和算法应用关系很大。
比如前面列表和元组本质上有点像数组，添加一个元素很快，但是查找某个元素是否存在就很忙。
于是基本所有的语言都提供类似字典的数据结构，key-value形式，查找非常快。

官网的一些示例，可以参考下基本操作。

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

关于字典，以下关键点必须掌握：

• key和value之间用:对应，不同键值对之间还是用，分隔。
• key是任意不可变类型,通常用字符串或数字。
• dict[key]可以取值，还有dict.get()方法，前者如果传入不存在的key会报错，否则返回None值。
• 对某个key赋值，如果存在则覆盖之前的，如果不存在新增键值对
• in关键字可以判断一个变量是否在字典键集合中，not in 反之
• dict()可以从键值对序列创建新字典

和列表一样，集合也支持推导式，把中括号换成大括号，同时有冒号
{x: x**2 for x in (2, 4, 6)

循环的技巧

Python中序列用的最多就是遍历它，也就是循环，不同类型的序列有不同的技巧。
items()、enumerate()、zip()、reversed()、sorted()你都用过哪些呢？

如何打印字典的键值对？
刚开始是我喜欢这样

for k in d:print(k,d[k])

但是如果我们要对值就行处理时，代码相对复杂了点。更好的办法是用items()方法将关键字和对应的值同时取出。

for k,v in d.items():print(k,v)

如果想对值v进行操作非常方便。
对于元组、列表和集合等序列，enumerate()函数可以将序列索引位置和对应值同时取出。

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

可以指定起始编号，你可以试试如果传入一个字典会有什么效果？
当存在两个或多个序列时，zip()可以将序列内元素一一匹配，比如试题和答案匹配。

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

你猜猜如果两个序列长度不一样，会不会报错？
如果传入字典呢？

当想要逆向一个序列时(不是排序，纯粹从后面开始数),reversed()函数可以帮我们。
当需要重新排序一个序列时，sorted()函数可以帮我们。
留一个疑问，序列不同类型元素如何排序呢？

深入条件控制

大家还记得while和if语句吗？
只要后面条件为True时，就会执行下面的代码块，为False 不执行。
任意一个能返回True或Flase的表达式都可以。

• ==、!=、<、<=、>、>=最基本的比较操作
• in和not in判断一个元素在不在序列中
• is和not is判断两个对象是否同一个对象
• 比较操作可以传递，a<b==c，会检验a是否小于b，且b是否等于c
• 比较操作可以通过布尔运算符and、or和not来组合,与或非运算
• 布尔运算符被称为短路运算符，从左到右解析，一旦可以确定解析结果就会停止，如果A 和 C 为真而 B 为假，那么 A and B and C 不会解析 C。
• 把比较操作或者逻辑表达式的结果赋值给一个变量,看看下面的赋值逻辑

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

官网还提到布尔操作符优先级比比较操作符低，但是not and or优先级依次降低，做个实验。

认真想了一下，由于布尔运算特殊性，and 和 or优先级意义大吗？由于and全真才为真，然后先算后算是不是效果一样？

比较序列和其他类型

相同类型的序列可以比较，使用字典顺序进行比较:

• 先比较第一个元素，如果不同，直接决定结果返回
• 第一个元素相同，再比较第二个元素
• 以此类推，直到一个序列为空

字典顺序对于字符串来说，就是单字符Unicode 码的顺序。下面是官网的一些示例

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

**对于不同类型的对象，只要待比较对象提供了合适的比较方法，就可以使用<和>进行比较，否则会抛出TypeError。

[]<()
Traceback (most recent call last):File "<ipython-input-68-6736af9fd6cf>", line 1, in <module>[]<()TypeError: '<' not supported between instances of 'list' and 'tuple'

关键总结，必看

好了，数据结构基础知识就这些，灵活运用最重要，需要后面长期思考，总结，简单总结下：

• 字符串、列表、元组、集合和字典都是Python的序列，很多序列属性和操作得掌握
• 列表、元组和集合非常像，中括号、小括号和大括号
• 注意分清可变和不可变
• list(),tuple(),set(),dict() 将可迭代对象强制转为列表、元组、集合和字典，很多时候为了安全需要显式的转换一下
• 解决实际问题时，一般需要多个数据结构配合使用
• 应该还有更多的操作方法，遇到再总结

很早之前分享过的图片有必要再拿出来。
 

python常用序列对比

希望Python高级数据结构让你编程更高效。

03 为什么

为什么要这么做？

首先任何东西的官方文档都是最全面最权威的教程。
以前只是受限于英语水平，
对官方网站敬而远之，
遇到问题都百度，
很多答案讲的都不到位，
没有说明为什么？
越到后面，收获越大。
比如学会了enumerate()、zip()、reversed()、sorted()使用技巧，
对序列比较有了更深理解。

04 更好的选择

有没有更好的选择

还是那句话，多敲代码，结合案例，偶然看看官方源代码，加深理解。
比如之前力扣(LeetCode)做过一道题(说起leetcode，注册起码5年只做了不到40题)

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

所谓双指针解法，设定两个索引cur和i，一次遍历就可以完成。
使用到可变列表，原地修改，没有额外的数组空间。

    def removeDuplicates(nums: List[int]) -> int:cur = 1for i in range(1,len(nums)):if nums[i]>nums[cur-1]:nums[cur] = nums[i]cur += 1return cur

晕，我不知道当初为啥这么写了，标准答案是!=判断,我这大于应该只能适用于升序数组。
还有一点这个原始nums长度不变，之前取前cur，也就是nums[:cur]才是我们想要的答案。
这就是函数传参，传的是引用，函数内部修改，外部被感知？

好了，睡觉，晚安。