你不知道的Python容器

你不知道的Python容器

昨天阅读了《Python Tricks: The Book》的第五章“Common Data Structures in Python”,该章节介绍了字典、数组、集合、栈、队列以及堆等数据结构的用法和注意事项,其中ChainMap、MappingProxyType等不常使用的容器类引起了我的注意。本文主要对几种不常使用的容器类进行介绍,通过示例说明这些容器的特点。

散列表

ChainMap

“collections.ChainMap”能有效整合多个字典的信息,提供一个可进行查询和更新的视图。它使用列表管理字典的引用,而非创建一个新的字典,因此时空开销比较小。当查询字典内容时,ChainMap按序遍历字典列表,直至找到给定的键;当更新(包括新增、删除)字典内容时,ChainMap只在字典列表的首项上进行操作。

由于ChainMap是从前到后依次查找字典列表,如果有多个字典包含了相同的键,那么靠近列表起始位置的字典就会被优先匹配,而靠近列表末端的字典会被忽略。ChainMap能够为键查找操作设置优先级的特性使得它能够用于管理应用程序的配置项。具体来说,当应用程序具有多种来源(命令行、配置文件、环境变量等)的配置时,可以把优先级高的配置当作ChainMap的第一个位置参数:

from collections import ChainMap

cli_config = {  # 命令行参数
    batch_size: 128,  # 批次大小为128
    learning_rate: 1e-3,
    dropout: 0.2,
}
default_config = {  # 默认配置
    batch_size: 64,  # 这里也配置了批次大小
    num_layers: 2,
}

lookup = ChainMap(cli_config, default_config)
lookup[batch_size]  # 128,命令行参数优于匹配
lookup[num_layers]  # 2,默认配置也能查询

lookup.maps  # ChainMap({batch_size: 128, learning_rate: 0.001, dropout: 0.2}, {batch_size: 64, num_layers: 2})

lookup[beam_size] = 4  # 新增键值对
del lookup[batch_size]  # 删除键值对
cli_config  # {learning_rate: 0.001, dropout: 0.2, beam_size: 4},cli_config是字典列表的首项,更新操作会作用到它身上

MappingProxyType

“types.MappingProxyType”通过代理模式控制了对字典内容的访问,它接收一个字典作为参数,返回该字典的只读(Read Only)视图,任何尝试更新该视图的操作都会触发“TypeError”异常。

from types import MappingProxyType

meetings = {
    ACL: Annual Meeting of the Association for Computational Linguistics,
    CVPR: IEEE Conference on Computer Vision and Pattern Recognition,
}
mapping = MappingProxyType(meetings)
mapping[ACL]  # Annual Meeting of...
del mapping[ACL]  # TypeError: mappingproxy object does not support item deletion
mapping[ACL] =   # TypeError: mappingproxy object does not support item assignment

线性表

Python的内置类型“list”支持按位置插入、删除列表元素,基于它可以实现栈和队列等操作受限的线性表,但考虑到“list”本身是基于动态数组的,频繁增删列表元素会使得“list”需要时常调整占用的存储空间(扩容、缩容),最终导致程序性能的下降。

“collections.deque”是实现栈和队列的更好选择,它基于双向链表,支持快速地从序列两端添加或删除元素。

  1. 使用deque模拟栈“后进先出”的特性

    from collections import deque
    
    stack = deque()
    stack.append(F)
    stack.append(E)
    
    stack.pop()  # E,首先弹出E
    stack.pop()  # F,出栈顺序与入栈顺序相反
    stack.pop()  # IndexError: pop from an empty deque
    
  2. 使用deque模拟队列“先进先出”的特性

    from collections import deque
    
    queue = deque()
    queue.append(F)
    queue.append(E)
    
    queue.popleft()  # F,F首先出队
    queue.popleft()  # E,出队顺序与入队顺序相同
    queue.popleft()  # IndexError: pop from an empty deque
    

二叉堆是一棵完全二叉树,有最小堆和最大堆两种类型,其中最小堆的每个节点都小于等于它的子节点。Python的“heapq”模块提供了关于构造最小堆、插入删除元素并保持最小堆特性的接口。

import random
import heapq

digits = [random.randrange(100) for i in range(5)]  # [75, 28, 93, 79, 57]
heapq.nsmallest(2, digits)  # [28, 57],获取列表中最小的2个元素

heapq.heapify(digits)  # 堆化,[28, 57, 93, 79, 75]
heapq.heappush(digits, 10)  # 插入一个元素,[10, 57, 28, 79, 75, 93]
heapq.heappop(digits)  # 10,弹出最小的元素

“queue.Priority”给出了优先队列的一种实现,它基于最小堆:

from queue import PriorityQueue

q.put((3, Sing))
q.put((1, Jump))
q.put((2, Rap))

while not q.empty():
    next_item = q.get()
    print(next_item)

# (1, Jump), (2, Rap), (3, Sing)

参考资料

  1. Python Tricks: The Book
  2. Pythons ChainMap: Manage Multiple Contexts Effectively
  3. 《流畅的Python》,2.9.4节“双向队列和其他形式的队列”

文章标签:

原文连接:https://www.cnblogs.com/wan-deuk/p/16191782.html

相关推荐

坚持用C++刷牛客题(剑指offer专题)

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……

「Java数据结构」手撕数组队列及环形数组队列。

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

【数据结构】插入排序(直接插入排序 && 希尔排序)

【C语言进阶】自定义类型——结构体

洛谷每日三题之第六天

【27. 表达式求值(中缀表达式)】

数据结构之【堆】(Heap)

经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

2022-7-15 java 数据结构入门

树状数组

Java | 平铺列表(List)互转树形(Tree)结构

算法秒懂之背包问题(DP)-附牛客网真题实战

【二叉树】之力扣牛客必刷题

求数据流中的中位数问题

字典树及其实现

【数据结构】栈实现队列 & 队列实现栈

python查找与排序算法详解(示意图+代码、看完基础不成问题)