collections模块-集合型数据结构

发表于   |   更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 2.1k | 阅读时长 ≈ 2 分钟

collections 是Python的一个集合模块, 它在内置数据结构 (dict, list, set, tuple) 的基础上, 提供了一些额外的集合型数据结构:

类型 说明 备注
deque 双端队列, 可以快速的从头/尾两端添加或删除元素 New in 2.4
defaultdict 带有默认值的字典 New in version 2.5
namedtuple 命名元组, 可以使用名字访问元素 New in version 2.6
Counter 计数器, 用于对某项数据进行计数 New in version 2.7
OrderedDict 有序字典, 按key对字典元素排序 New in version 2.7
ChainMap 合并多个map(dict), 但保持原数据结构 New in version 3.3
UserDict 将字典包装起来使得创建字典的子类更容易
UserList 列表对象的包装器
UserString 字符串对象的包装器

deque

deque 是double-ended queue 的缩写, 即双端队列. List存储数据的优势在于按索引查找元素很快, 但是插入和删除元素就很慢了, 因为List是基于数组实现的. deque 是为了高效插入和删除的双向列表, 适合用于跌列和栈, 而且线程安全, 其原型如下:

1
collections.deque([iterable[, maxlen]])

deque 除了list固有的方法外, 还新增了 appendleft / popleft 等方法允许高效的在队列的开头插入或删除元素, 其时间复杂度为 $O(1)$

defaultdict

namedtuple

namedtuple 是继承自 tuple 的子类, 它会创建一个和 tuple 类似的对象, 而且对象拥有可以访问的属性, 注意, 这些属性是只读的, 示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import namedtuple

# 定义一个 namedtuple 类型: User 类型, 该类型包含三个属性: name, sex 和 age.
User = namedtuple("User", ["name", "sex", "age"])

# 创建一个 User 类型的对象 u1
u1 = User(name="u1", sex="male", age=1)


# 通过 . 访问对象的属性
print(u1.name, u1.sex, u1.age) # "u1" "male" 1

# 属性一旦确定就是只读的, 不能直接修改
u1.age = 2 # 报错: AttributeError: can't set attribute

# 如果非要修改, 可以使用 _replace, 这种方法实际上是创建再替换, 而非修改, 不过效果上相同
u1 = u1._replace(age=2)

# 利用 _asdict() 方法可将 namedtuple 类型转换成 OrderedDict 类型.
u1_d = u1._asdict()

Counter

OrderedDict

OrderedDict 是 dict 的一个子类, 支持所有的 dict 方法, 它能够保持 dict 的有序性, 其原型如下:

1
collections.OrderedDict([items])
1
2
3
4
# last = True: LIFO 栈
# last = False: FIFO 队列
popitem(last=True)
move_to_end(key, last=True)

OrderedDict 的经典应用, LRU:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LRU(OrderedDict):
    'Limit size, evicting the least recently looked-up key when full'

    def __init__(self, maxsize=128, *args, **kwds):
        self.maxsize = maxsize
        super().__init__(*args, **kwds)

    def __getitem__(self, key):
        value = super().__getitem__(key)
        self.move_to_end(key)
        return value

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        if len(self) > self.maxsize:
            oldest = next(iter(self))
            del self[oldest]