【python笔记】deque()、list()、heapq主要区别

2024-09-02 09:28

本文主要是介绍【python笔记】deque()、list()、heapq主要区别,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

内部实现

1、deque()

deque是Python中的一个双端队列,位于collections模块中。

数据结构:

deque 是一个双端队列,其内部实现基于一个双向链表

这意味着元素不是连续存储在内存中的,而是分布在多个节点中,每个节点包含元素本身以及指向其前一个和后一个节点的链接。
动态扩容:

虽然 deque 不需要像 list 那样复制整个数组来扩容,但它仍然需要管理链表的节点,并在必要时添加新的节点。然而,这个过程的开销通常比 list 的扩容要小。
随机访问:

与 list 相比,deque 不支持快速的随机访问。访问 deque 中的元素通常需要从头或尾开始遍历链表,直到找到所需的元素,这可能需要O(n)时间复杂度。
插入和删除:

在 deque 的两端添加或删除元素是非常高效的(O(1)),因为只需要修改几个指针即可。

然而,在 deque 的中间插入或删除元素则可能较慢(O(n)),因为需要遍历链表来找到正确的位置,并可能需要移动多个节点。
 

2、list()

数据结构:

list 是一个动态数组,其内部实现基于一个连续的数组

数组的大小可以动态变化,以容纳更多的元素。
内存分配:

当列表需要更多空间时,Python会分配一个新的、更大的数组,并将旧数组的元素复制到这个新数组中。

这个过程称为“扩容”。
随机访问:

由于列表是基于数组的,因此它支持快速的随机访问,即可以在O(1)时间复杂度内通过索引访问列表中的任意元素。
插入和删除:

在列表的末尾添加或删除元素是高效的(O(1)),但在列表的开头或中间插入或删除元素则可能较慢(O(n)),因为需要移动其他元素

3、heapq

heapq是Python中的一个模块;实际上是基于Python的列表(list)实现了一个最小堆,用于维护一组元素的优先队列。

数据结构:heapq 模块提供了一个堆队列算法的实现,它通常使用列表(list)作为底层容器。但是,heapq 并不改变列表的底层数据结构;它只是通过一系列操作(如上浮和下沉)来维护堆的属性。
堆属性:

heapq 实现的是一个最小堆(尽管可以通过一些技巧来实现最大堆),其中父节点的值不大于其子节点的值。

这使得堆顶(列表的第一个元素)始终是最小的元素。
操作:

heapq 提供了如 heappush(向堆中添加元素)、heappop(从堆中移除最小元素)和 heapify(将列表转换成堆)等函数。

这些函数通过维护堆的属性来确保堆的有效性。
性能:

heapq 的性能特点主要体现在其插入和删除操作上。

向堆中添加元素(heappush)和从堆中移除最小元素(heappop)的时间复杂度都是O(log n),其中n是堆中的元素数量。

这是因为这些操作可能需要通过上浮或下沉来调整堆的结构。
 


使用场景

1、deque()

双端队列:

当需要在队列的两端进行频繁的插入和删除操作时,deque是理想的选择。
高效访问两端元素:

deque提供了从两端快速访问元素的能力,这使得它在某些特定场景下(如循环队列)非常有用。
队列和栈的实现:

deque可以作为队列和栈的底层实现,因为它支持从两端添加和删除元素。

2、list()

存储静态数据集:

适用于需要频繁访问元素、但不经常进行插入或删除操作的场景

3、heapq

优先队列:

当需要处理一系列元素,但每次只想处理优先级最高(或最低)的元素时,heapq非常有用。
堆排序:

heapq可以用于实现堆排序算法,这是一种基于比较的排序算法,适用于大数据集的排序。
资源分配:

在资源分配问题中,如内存管理、CPU时间片分配等,heapq可以根据优先级来分配资源。


常用方法

1、deque()与list()

共用方法
append(x)向右侧添加一个元素
pop()从右侧移除并返回一个元素
extend(iterable)从右侧扩展,添加指定迭代器的元素
insert(index,obj) 在指定位置插入一个元素
index(value, [start, [stop]])返回指定值在列表中第一次出现的索引
clear()移除列表中的所有元素,使其长度为0
remove(value)移除列表中第一个出现的指定值
count(value)返回列表中指定值的出现次数
reverse()原地翻转列表中元素
copy()返回一个浅拷贝
deque()专用方法
appendleft(x)向左侧添加一个元素
extendleft(iterable)从左侧扩展deque,通过添加指定迭代器的元素(元素顺序相反)
popleft()从左侧移除并返回一个元素
rotate(n=1)向右旋转deque n个步骤(如果n是负数,则向左旋转)
list()专用方法
sort(key=None, reverse=False)列表中的元素进行排序
注意:deque在两端添加或删除元素时性能更高,而list在列表中间或两端添加元素时性能相对较差,尤其是在列表很大时。

2、heapq

heappush(heap, item)将item项添加到heap中,保持堆属性
heappop(heap)弹出并返回heap中的最小元素(对于小顶堆)。如果堆为空,则会引发IndexError
heappushpop(heap, item)将item推入堆中,然后弹出并返回堆中的最小元素。这个操作比先调用heappush()再调用heappop()更高效
heapreplace(heap, item)弹出并返回堆中的最小元素,同时将item推入堆中。这个操作与先调用heappop()再调用heappush()效果相同,但更高效
heapify(list)将列表list转换成堆。这是通过就地修改列表来完成的,意味着不会创建新列表
nlargest(n, iterable, key=None)返回iterable中n个最大的元素。这通过保持一个大小为n的堆来实现,使得堆的根元素始终是最大的元素之一
nsmallest(n, iterable, key=None)返回iterable中n个最小的元素。与nlargest()类似,但这是为了找到最小的元素
merge(*iterables, key=None, reverse=False) 合并多个已排序的输入为一个已排序的迭代器;这类似于sorted(itertools.chain(*iterables)),但返回的是一个迭代器,并且不会一次性加载所有数据,因此更适合于大数据集

这篇关于【python笔记】deque()、list()、heapq主要区别的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1129591

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

便携式气象仪器的主要特点

TH-BQX9】便携式气象仪器,也称为便携式气象仪或便携式自动气象站,是一款高度集成、低功耗、可快速安装、便于野外监测使用的高精度自动气象观测设备。以下是关于便携式气象仪器的详细介绍:   主要特点   高精度与多功能:便携式气象仪器能够采集多种气象参数,包括但不限于风速、风向、温度、湿度、气压等,部分高级型号还能监测雨量和辐射等。数据采集与存储:配备微电脑气象数据采集仪,具有实时时钟、数据存

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

nudepy,一个有趣的 Python 库!

更多资料获取 📚 个人网站:ipengtao.com 大家好,今天为大家分享一个有趣的 Python 库 - nudepy。 Github地址:https://github.com/hhatto/nude.py 在图像处理和计算机视觉应用中,检测图像中的不适当内容(例如裸露图像)是一个重要的任务。nudepy 是一个基于 Python 的库,专门用于检测图像中的不适当内容。该

native和static native区别

本文基于Hello JNI  如有疑惑,请看之前几篇文章。 native 与 static native java中 public native String helloJni();public native static String helloJniStatic();1212 JNI中 JNIEXPORT jstring JNICALL Java_com_test_g