魔力Python——collections

collections是Python内建的一个集合模块,提供了许多有用的集合类。

namedtuple

tuple可表示不变集合,例如,一个点的二维坐标就可以表示成:

A = (2,3)

但是,看到(2,3)这样的tuple很难联想到一个点坐标,定义一个class,又很鸡肋,大材小用,此时,namedtuple就派上用场了。

1
2
3
4
5
from collections import namedtuple
Point = namedtuple('Point',('x','y'))
A = Point(2,3)
print(A.x,A.y)
>>> 2 3

deque

由于list是线性存储,按索引访问元素很快,但数据量大时,插入和删除效率较低。deque是为实现高效插入和删除的双向列表,适用于栈和队列。

deque除了list的append()pop(),还支持appenleft()popleft(),这就可以高效的往头部插入或删除元素。

1
2
3
4
5
6
7
8
9
10
#用deque查找图中start->goal两结点的路径
from collections import deque
def bfs_paths(graph, start, goal):
queue = deque([(start,[start])])
while queue:
vertex,path= queue.popleft()
if vertex==goal:
yield path
for next in graph[vertex]-set(path):
queue.extend([(next,path+[next])])

defaultdict

使用dict时,常常会遇到引用的key不存在,而报错,如果希望可以不存在时,返回一个默认值,可以用defaultdict
用法1:

1
2
3
4
5
6
7
from collections import defaultdict
d = defaultdict(lambda: 'Error')
d['1'] = 'a'
print(d['1'])
>>> a #key存在
print(d['2'])
>>> Error #key不存在

用法2:

1
2
3
4
5
6
7
import collections
s = 'mississippi'
d = defaultdict(int) #该语句创建一个defaultdict类型,value类型是指定的int类型
for k in s:
d[k] += 1
>>> list(d.items())
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

1
2
3
4
5
6
7
import collections
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = collections.defaultdict(list) #该语句创建一个defaultdict类型,value类型是指定的list类型
for k, v in s:
d[k].append(v)
>>>list(d.items())
[('red', [1]), ('blue', [2, 4]), ('yellow', [1, 3])]

Counter

Counter是一个简单的计数器,可统计字符出现的个数:

1
2
3
4
5
6
7
from collections import Counter
A = Counter()
str1='hello word'
for s in str1:
A[s]+=1
print(A)
>>> Counter({'l': 2, 'o': 2, ' ': 1, 'h': 1, 'r': 1, 'w': 1, 'd': 1, 'e': 1})

OrderedDict

使用dict时,key是无序的,若要使key保持有序,可使用OrderedDict,它可以实现一个先进先出(FIFO)的dict,当超出容量,删除最先进入的key。
实例:
LeetCode——LRU Cache
题目大意,就是实现一个近期最少使用(LRU)缓存的数据结构,支持put和get操作。
get(key)-取值(key恒为正),不存在返回-1;
put(key,value)-插入或替换(缓存容量达到上限,移除近期最少使用的元素)。

运用OrderedDict解题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import OrderedDict
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity=capacity
self.cache = OrderedDict()
def get(self, key):
"""
:type key: int
:rtype: int
"""
if not key in self.cache.keys():
return -1
else:
#一定要弹出再重新插入,不然体现不了最近最少使用
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
#2种特殊情况,key在缓存中,弹出再插;容量达到上限,弹出最近最少使用的
if key in self.cache.keys():
self.cache.pop(key)
elif self.capacity==len(self.cache):
self.cache.popitem(last = False)
self.cache[key]=value

此题,虽然用OrderedDict可以很简洁的解决,但是不够高效,更快速的方法,可采用双链表实现,双链表实现细节参见我的Github(method2)。

Talk is cheap. Show me the code.
分享