Python 这3种超方便的容器你都用过吗

2020-12-26 08:08 Python实用宝典

图片


导读初学python时,遇到各类数据结构都会习惯性的想到列表。由于python的变量不声明类型,一个list几乎可以满足所有操作。如果列表推导式用的再熟练一些,那个感觉简直是会上瘾的。


直到我认识了collections之后,这种深深陶醉的感觉被彻底击碎。原来,python还有这么多强大的内置容器!


01 初识collections

Collections模块是python的内置模块之一,提供了很多容器类型。按照官方文档介绍,它被用作是对python通用内置类型(list、dict、set、tuple)的一个替代。


最初collections模块的类型众多,在python3.3版本中将一部分抽象数据类型写进了collections.abc(abc,abstract base classes)中,后续将在python3.9版本全部整合至collections.abc模块。


图片

collections模块提供了9种容器类型
(适用于python3.8及更早版本)


collections模块当前包括9类容器接口,本文主要介绍其中比较常用的3种数据类型:deque,defaultdict,Counter。

02 双端队列:deque

deque(double-ended queue)是一个与列表类似的容器类型,其最大的优势在于支持高效的双端添加(append)和弹出(pop)操作,两个方向的开销都是 O(1) 复杂度。


其常用函数包括:

append(x)#添加 x 到右端。
appendleft(x)#添加 x 到左端。
extend(iterable)#扩展deque的右侧,通过添加iterable参数中的元素。
extendleft(iterable)#扩展deque的左侧,通过添加iterable参数中的元素。注意,iterable参数中的顺序将被反过来添加。
insert(i, x)#在位置 i 插入 x 。如果插入会导致一个限长 deque 超出长度 maxlen 的话,就引发一个IndexError
pop()#移去并且返回一个元素,deque 最右侧的那一个。 如果没有元素的话,就引发一个 IndexError。
popleft()#移去并且返回一个元素,deque 最左侧的那一个。 如果没有元素的话,就引发 IndexError。
remove(value)#移除找到的第一个 value。 如果没有的话就引发 ValueError。
index(x[, start[, stop]])#返回 x 在 deque 中的位置(在索引 start 之后,索引 stop 之前)。 返回第一个匹配项,如果未找到则引发 ValueError。
count(x)#计算 deque 中元素等于 x 的个数。
reverse()#将deque逆序排列。返回 None 。
rotate(n=1)#向右循环移动 n 步。 如果 n 是负数,就向左循环。
#如果deque不是空的,向右循环移动一步就等价于 d.appendleft(d.pop()) , 向左循环一步就等价于 d.append(d.popleft()) 。
clear()#移除所有元素,使其长度为0.
copy()#创建一份浅拷贝。


需注意的几个要点:


1. deque在初始化时,可以接受一个任意可迭代类型或者为空,同时可接受一个缺省参数maxlen,如果不提供maxlen值,则默认不限长度。

2. 初始化如果提供maxlen参数,在append、appendleft、extend和extendleft 4类操作中,若增加元素后超过最大长度,操作不会报错,而是在操作的另一端自动丢弃多余元素(模拟处理"过期"元素);但在insert操作中,由于目标是在deque之间插入,deque无法"决策"该丢弃哪一端的多余元素,从而引发IndexError

from collections import deque
dq = deque('abcde'6)
dq.extend('fg')
print(dq)#deque(['b', 'c', 'd', 'e', 'f', 'g'], maxlen=6)
dq.appendleft('h')
print(dq)#deque(['h', 'b', 'c', 'd', 'e', 'f'], maxlen=6)
dq.insert(3,'i')
print(dq)#IndexError: deque already at its maximum size


1. extendleft()是在左端扩展,而且是将可迭代元素以相反的顺序扩展到左端。

2. extendleft()和popleft()是O(1)复杂度,但remove()和insert()仍然是O(n)复杂度。

3. pop()和popleft()不支持任意索引的弹出,即仅能弹出左端或右端的元素,两个函数不允许接受任意参数。

4. rotate()操作可以很容易的实现经典的旋转字符串问题


from collections import deque
dq = deque('abcdefg')
dq.rotate(3)#右旋3位
print(dq)#deque(['e', 'f', 'g', 'a', 'b', 'c', 'd'])


deque支持迭代、len()、in等基本操作,但不支持切片操作,这也是deque相比列表的一个缺点。

from collections import deque
dq = deque([1234])
dq[0:2]#TypeError: sequence index must be integer, not 'slice'
03 默认字典:defaultdict

defaultdict是python内置类型dict的子类,支持dict的所有操作,重点是在初始化时可以接收一个default_factory作为字典默认生成类型。


def __init__(self, default_factory=None, **kwargs): # known case of _collections.defaultdict.__init__
    """
    defaultdict(default_factory[, ...]) --> dict with default factory

    The default factory is called without arguments to produce
    a new value when a key is not present, in __getitem__ only.
    A defaultdict compares equal to a dict with the same items.
    All remaining arguments are treated the same as if they were
    passed to the dict constructor, including keyword arguments.

    # (copied from class doc)
    """


使用defaultdict的最大便利是指定默认类型后,后续操作元素时可以直接操作,无需判断是否存在及初始化。例如,想用字典统计一个列表中各元素的个数,可以这样操作:

from collections import defaultdict
colors = ['yellow''blue''yellow''blue''red']
colorDict = defaultdict(int)
for color in colors:
    colorDict[color] += 1
print(colorDict)#defaultdict(<class 'int'>, {'yellow': 2, 'blue': 2, 'red': 1})


或者列表中元素是一个元组类型,我们需要记录所有相同key的对应value值:

from collections import defaultdict
persons = [('name''A'), ('name''B'), ('age'18), ('age'20), ('name''C')]
perDict = defaultdict(list)
for k, v in persons:
    perDict[k].append(v)
print(perDict)#defaultdict(<class 'list'>, {'name': ['A', 'B', 'C'], 'age': [18, 20]})


除了int和list外,还支持set类型默认字典。注意:defaultdict只是在操作某一个此前不存在的key时自动用default_factory初始化一个value,但在in操作时,若此前不存在则仍然判断为False。

from collections import defaultdict
persons = [('name''A'), ('name''B'), ('age'18), ('age'20), ('name''C')]
perDict = defaultdict(list)
for k, v in persons:
    perDict[k].append(v)
'height' in perDict #False
04 计数器:Counter

在上个例子中,我们利用defaultdict简化了统计列表中元素个数的操作,但实际上collections中针对计数操作还有一个更加专业的容器类型:Counter。


Counter类型也是一个继承自dict类型的容器,同时也是一个集合,元素及其计数值存储为key:value值。这里,计数可以是任何整数值,包括0和负数。


初始化一个Counter类型主要有2种方式:

1. 用一个可迭代对象或者一个字典:

2. 在用可迭代对象初始化时,counter会自动统计所有元素及其出现的次数,且统计元素保留迭代对象中元素出现的先后顺序(这点比较关键,后面有例为证);

而在用一个字典初始化时,value值可以不是整数,甚至可以不是数值(不过个人认为这已经违背了计数器的初衷)

from collections import Counter
colors = ['blue''red''green''blue''red''yellow']
colorC = Counter(colors)
print(colorC)#Counter({'blue': 2, 'red': 2, 'green': 1, 'yellow': 1})
persons = {'name':'AA''age':20}
personC = Counter(persons)
print(personC)#Counter({'name': 'AA', 'age': 20})


Counter作为一个计数器容器类型,有几个常用的统计类接口:

elements()#返回一个迭代器,其中每个元素重复其计数值次。 元素会按首次出现的顺序返回。 如果一个元素的计数值小于一,elements() 将会忽略它。
most_common([n])#返回一个列表,其中包含 n 个最常见的元素及出现次数,按常见程度由高到低排序。 如果 n 被省略或为 None,most_common() 将返回计数器中的 所有 元素。 计数值相等的元素按首次出现的顺序排序:
subtract([iterable-or-mapping])#从 迭代对象 或 映射对象 减去元素。像 dict.update() 但是是减去,而不是替换。输入和输出都可以是0或者负数。
A+B #计数器相加
A-B #计数器相减
A&B #计数器交集
A|B #计数器并集


利用这些接口,可以方便的实现特定的一些计数统计,包括出现最多的元素及其个数、加减法等。重点说明下Counter中的两个"减法"操作,一个是subtract,另一个是“-”,即重载的__sub__操作,二者主要区别如下:

1. subtract是实例方法,__sub__是重写的类方法。


2. subtract对实例进行inplace操作,无返回值,而__sub__返回相减后的结果。


3. subtract是简单的完成元素及其计数的减法,即:A、B都有的元素,结果是基数之差,0个也会包含在结果中;A有B无的,则直接返回A的计数值;A无B有的,则会按A中相应元素计数为0去操作减法,返回的是B中元素计数值的负数。


4. __sub__中以"-"操作符前面的对象为主(姑且叫做前向保留),即忽略前面没有而后面对象特有的元素,当共有元素计数相减为0时,结果不保留(类似SQL语言中的left join)。

from collections import Counter
A = Counter([1342234])
B = Counter([1245667])
print(A, B)  #Counter({3: 2, 4: 2, 2: 2, 1: 1}) Counter({6: 2, 1: 1, 2: 1, 4: 1, 5: 1, 7: 1})
print(A.most_common(3))  #[(3, 2), (4, 2), (2, 2)]
print(A-B) ##Counter({3: 2, 4: 1, 2: 1})
A.subtract(B) ## 对A进行inplace操作,操作后A:Counter({1: 0, 3: 2, 4: 1, 2: 1, 5: -1, 6: -2, 7: -1})


运用Counter类的操作,有时可以得到很好的效果。例如:

  • 利用减法“-”操作的前向保留特点:

给你两个长度相等的字符串 s 和 t。每一个步骤中,你可以选择将 t 中的 任一字符 替换为 另一个字符。返回使 t 成为 s 的字母异位词的最小步骤数。字母异位词 指字母相同,但排列不同的字符串。


示例 :

输出:s = "leetcode", t = "practice"

输出:5

提示:用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c',使 t 变成 s 的字母异位词。


来源:力扣(LeetCode)1347# 制造字母异位词的最小步骤数

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        return sum((collections.Counter(s) - collections.Counter(t)).values())




利用Counter初始化时保留迭代元素出场顺序的特点:

字符串S和 T 只包含小写字符。在S中,所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说,如果S中x在y之前出现,那么返回的字符串中x也应出现在y之前。返回任意一种符合条件的字符串T。


示例:

输入:

S = "cba"

T = "abcd"

输出: "cbad"

解释: 

S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a". 

由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。


来源:力扣(LeetCode)791#自定义字符串排序

class Solution:
    def customSortString(self, S: str, T: str) -> str:
        cs = collections.Counter(S)
        ct = collections.Counter(T)
        return ''.join(list(((cs+ct)-cs).elements()))




05 总结

1. collections模块提供了很好的容器型数据结构,对于python通用内置类型list、dict等是一个很好的扩展和补充


2. deque实现了一个双端队列,可以实现O(1)复杂度的双向添加和弹出元素以及扩展,但remove()和insert()仍然是O(n)操作。pop()和popleft()不接受任何参数,仅能弹出端头元素


3. defaultdict可以通过设置默认值实现直访问字典的key值,而无需判断是否存在


4. Counter继承字典,可以很好的实现计数器功能,并支持常用的+、-、交、并操作。


还有其他一些实用的功能,如namedtuple、ordereddict等读者可以自行查询使用。


我们的文章到此就结束啦,如果你喜欢今天的Python 实战教程,请持续关注Python实用宝典。

有任何问题,可以在公众号后台回复:加群,回答相应红字验证信息,进入互助群询问。

原创不易,希望你能在下面点个赞和在看支持我继续创作,谢谢!

点击下方阅读原文可获得更好的阅读体验

Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文章转载自公众号:pythondict

首页 - Python 相关的更多文章: