5. deque
基本用法 deque 双端队列,基于list优化了列表两端的增删数据操作。基本用法:
- from collections import deque
-
- In [3]: d = deque([3,2,4,0])
-
- In [4]: d.popleft() # 左侧移除元素,O(1)时间复杂度
- Out[4]: 3
-
- In [5]: d.appendleft(3) # 左侧添加元素,O(1)时间复杂度
-
- In [6]: d
- Out[6]: deque([3, 2, 4, 0])
使用场景:list左侧添加删除元素的时间复杂度都为O(n),所以在Python模拟队列时切忌使用list,相反使用deque双端队列非常适合频繁在列表两端操作的场景。但是,加强版的deque牺牲了空间复杂度,所以嵌套deque就要仔细trade-off:
- In [9]: sys.getsizeof(deque())
- Out[9]: 640
-
- In [10]: sys.getsizeof(list())
- Out[10]: 72
实现原理:cpython实现deque使用默认长度64的数组,每次从左侧移除1个元素,leftindex加1,如果超过64释放原来的内存块,再重新申请64长度的数组,并使用双端链表block管理内存块。
6. Counter
基本用法:Counter一种继承于dict用于统计元素个数的数据结构,也称为bag 或 multiset. 基本用法:
- from collections import Counter
- In [14]: c = Counter([1,3,2,3,4,2,2]) # 统计每个元素的出现次数
- In [17]: c
- Out[17]: Counter({1: 1, 3: 2, 2: 3, 4: 1})
-
- # 除此之外,还可以统计最常见的项
- # 如统计第1最常见的项,返回元素及其次数的元组
- In [16]: c.most_common(1)
- Out[16]: [(2, 3)]
使用场景:基本的dict能解决的问题就不要用Counter,但如遇到统计元素出现频次的场景,就不要自己去用dict实现了,果断选用Counter.
需要注意,Counter统计的元素要求可哈希(hashable),换句话说如果统计list的出现次数就不可行,不过list转化为tuple不就可哈希了吗.
实现原理:Counter实现基于dict,它将元素存储于keys上,出现次数为values.
7. OrderedDict
基本用法 继承于dict,能确保keys值按照顺序取出来的数据结构,基本用法:
- In [25]: from collections import OrderedDict
-
- In [26]: od = OrderedDict({'c':3,'a':1,'b':2})
-
- In [27]: for k,v in od.items():
- ...: print(k,v)
- ...:
- c 3
- a 1
- b 2
使用场景:基本的dict无法保证顺序,keys映射为哈希值,而此值不是按照顺序存储在散列表中的。所以遇到要确保字典keys有序场景,就要使用OrderedDict.
实现原理 :你一定会好奇OrderedDict如何确保keys顺序的,翻看cpython看到它里面维护着一个双向链表self.__root,它维护着keys的顺序。既然使用双向链表,细心的读者可能会有疑问:删除键值对如何保证O(1)时间完成?
cpython使用空间换取时间的做法,内部维护一个self.__map字典,键为key,值为指向双向链表节点的link. 这样在删除某个键值对时,通过__map在O(1)内找到link,然后O(1)内从双向链表__root中摘除。
8. heapq
基本用法 基于list优化的一个数据结构:堆队列,也称为优先队列。堆队列特点在于最小的元素总是在根结点:heap[0] 基本用法:
- import heapq
- In [41]: a = [3,1,4,5,2,1]
-
- In [42]: heapq.heapify(a) # 对a建堆,建堆后完成对a的就地排序
- In [43]: a[0] # a[0]一定是最小元素
- In [44]: a
- Out[44]: [1, 1, 3, 5, 2, 4]
-
- In [46]: heapq.nlargest(3,a) # a的前3个最大元素
- Out[46]: [5, 4, 3]
-
- In [47]: heapq.nsmallest(3,a) # a的前3个最小元素
- Out[47]: [1, 1, 2]
使用场景:如果想要统计list中前几个最小(大)元素,那么使用heapq很方便,同时它还提供合并多个有序小list为大list的功能。
基本原理:堆是一个二叉树,它的每个父节点的值都只会小于或大于所有孩子节点(的值),原理与堆排序极为相似。
9. defaultdict
基本用法 defaultdict是一种带有默认工厂的dict,如果对设计模式不很了解的读者可能会很疑惑工厂这个词,准确来说工厂全称为对象工厂。下面体会它的基本用法。
基本dict键的值没有一个默认数据类型,如果值为list,必须要手动创建:
- words=['book','nice','great','book']
- d = {}
- for i,word in enumerate(words):
- if word in d:
- d[word].append(i)
- else:
- d[word]=[i] # 显示的创建一个list
但是使用defaultdict:
- from collections import defaultdict
- d = defaultdict(list) # 创建字典值默认为list的字典
- for i,word in enumerate(words):
- d[word] = i
省去一层if逻辑判断,代码更加清晰。上面defaultdict(list)这行代码默认创建值为list的字典,还可以构造defaultdict(set), defaultdict(dict)等等,这种模式就是对象工厂,工厂里能制造各种对象:list,set,dict...
使用场景:上面已经说的很清楚,适用于键的值必须指定一个默认值的场景,如键的值为list,set,dict等。
实现原理:基本原理就是调用工厂函数去提供缺失的键的值。后面设计模式专题再详细探讨。
10. ChainMap
基本用法 如果有多个dict想要合并为一个大dict,那么ChainMap将是你的选择,它的方便性体现在同步更改。具体来看例子:
- In [55]: from collections import ChainMap
-
- In [56]: d1 = {'a':1,'c':3,'b':2}
-
- In [57]: d2 = {'d':1,'e':5}
-
- In [58]: dm = ChainMap(d1,d2)
-
- In [59]: dm
- Out[59]: ChainMap({'a': 1, 'c': 3, 'b': 2}, {'d': 1, 'e': 5})
ChainMap后返回一个大dict视图,如果修改其对应键值对,原小dict也会改变:
- In [86]: dm.maps # 返回一个字典list
- Out[86]: [{'a': 2, 'c': 3, 'b': 2, 'd': 10}, {'d': 1, 'e': 5}]
-
- In [87]: dm.maps[0]['d']=20 # 修改第一个dict的键等于'd'的值为20
-
- In [88]: dm
- Out[88]: ChainMap({'a': 2, 'c': 3, 'b': 2, 'd': 20}, {'d': 1, 'e': 5})
-
- In [89]: d1 # 原小dict的键值变为20
- Out[89]: {'a': 2, 'c': 3, 'b': 2, 'd': 20}
使用场景 :具体使用场景是我们有多个字典或者映射,想把它们合并成为一个单独的映射,有读者可能说可以用update进行合并,这样做的问题就是新建了一个内存结构,除了浪费空间外,还有一个缺点就是我们对新字典的更改不会同步到原字典上。
实现原理:通过maps便能观察出ChainMap联合多个小dict装入list中,实际确实也是这样实现的,内部维护一个lis实例,其元素为小dict.
总结
以上就是Python常用的10种数据结构,4种常用的基本结构,6种基于它们优化的适应于特定场景的结构,对它们的学习我将它们总结为三步。