没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
Python 中常见的数据结构
图灵教育
题图来自 Unsplash。
有没有什么是每个 Python 开发者都应该进一步练习和学习的呢?
那就是数据结构。数据结构是构建程序的基础。各个数据结构在组织
方式上有自己的特点,以便在不同情况下高效访问数据。我相信无论
程序员的技术水平或经验如何,掌握一些基本功总是有好处的。
我并不主张只专注于掌握更多的数据结构知识,这是一种“失效模
式”(failure mode),只会让人陷入假想理论上的幻境,而不会带
来任何实际的结果。不过花一些时间来补习数据结构(和算法)的知
识总会有好处。
无论是花几天时间“突击”,还是利用零碎的时间持续学习,在数据
结构上下点功夫都是值得的。那么 Python 中有哪些数据结构呢?列
表、字典、集合,还有……栈?Python 有栈吗?
看到没?Python 在其标准库中提供了大量的数据结构,但问题在于
各自的命名有点词不达意。
举例来说,很多人甚至不清楚 Python 是否具体实现了像栈这样著名
的“抽象数据类型”。相比之下,Java 等其他语言则更“计算机科学
化”,其中的命名很明确。比如,Java 中的列表还细分成了
LinkedList 和 ArrayList。
这种细分的命名便于我们识别各个数据类型的预期行为和计算复杂
度。Python 也倾向于使用简单且“人性化”的命名方案。我喜欢
Python 的方案,因为人性化也是 Python 编程更有趣的原因之一。
这种方案的缺点在于,即使是经验丰富的 Python 开发人员,也不清
楚内置的列表类型是以链表还是动态数组实现的。如果需要用到这些
知识却没有掌握,则会让人感到沮丧,也可能导致面试被拒。
本文将介绍 Python 及其标准库内置的基本数据结构和抽象数据类型
的实现。
我们的目标是阐释常见的抽象数据类型在 Python 中对应的名称及实
现,并逐个进行简单的介绍。这些内容也会帮助你在 Python 面试中
大放异彩。
如果你正在寻找一本能够用来温习通用数据结构知识的好书,我强烈
推荐 Steven S. Skiena 的《算法设计手册》。
这本书介绍了各种数据结构及其各自在不同算法中的实际应用,并在
这两个方面之间取得了很好的平衡。它对编写本文提供了很大的帮
助。
一、字典、映射和散列表
在 Python 中,字典是核心数据结构。字典可以存储任意数量的对
象,每个对象都由唯一的字典键标识。
字典通常也被称为映射、散列表、查找表或关联数组。字典能够高效
查找、插入和删除任何与给定键关联的对象。
这在现实中意味着什么呢?字典对象相当于现实世界中的电话簿。
电话簿有助于快速检索与给定键(人名)相关联的信息(电话号
码)。因此不必为了查找某人的号码而浏览整本电话簿,根据人名基
本上就能直接跳到需要查找的相关信息。
若想研究以何种方式组织信息才有利于快速检索,上述类比就不那么
贴切了。但基本性能特征相同,即字典能够用来快速查找与给定键相
关的信息。
总之,字典是计算机科学中最常用且最重要的数据结构之一。
那么 Python 如何处理字典呢?
我们来看看 Python 及其标准库中可用的字典实现。
1.dict——首选字典实现
由于字典非常重要,因此 Python 直接在语言核心中实现了一个稳健
的字典:dict 数据类型。
Python 还提供了一些有用的“语法糖”来处理程序中的字典。例
如,用花括号字典表达式语法和字典解析式能够方便地创建新的字典
对象:
phonebook = {
'bob': 7387,
'alice': 3719,
'jack': 7052,
}
squares = {x: x * x for x in range(6)}
>>> phonebook['alice']
3719
>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
关于哪些对象可以作为字典键,有一些限制。
Python 的字典由可散列类型的键来索引。可散列对象具有在其生命
周期中永远不会改变的散列值(参见__hash__),并且可以与其他对
象进行比较(参见__eq__)。另外,相等的可散列对象,其散列值必
然相同。
像字符串和数这样的不可变类型是可散列的,它们可以很好地用作字
典键。元组对象也可以用作字典键,但这些元组本身必须只包含可散
列类型。
Python 的内置字典实现可以应对大多数情况。字典是高度优化的,
并且是 Python 语言的基石,例如栈帧中的类属性和变量都存储在字
典中。
Python 字典基于经过充分测试和精心调整过的散列表实现,提供了
符合期望的性能特征。一般情况下,用于查找、插入、更新和删除操
作的时间复杂度都为 O(1)。
大部分情况下,应该使用 Python 自带的标准字典实现。但是也存在
专门的第三方字典实现,例如跳跃表或基于 B 树的字典。
除了通用的 dict 对象外,Python 的标准库还包含许多特殊的字典实
现。它们都基于内置的字典类,基本性能特征相同,但添加了其他一
些便利特性。
下面来逐个了解一下。
2.collections.OrderedDict——能记住键的插入顺序
collections.OrderedDict 是特殊的 dict 子类,该类型会记录添加到
其中的键的插入顺序。
剩余51页未读,继续阅读
资源评论
xiaoshun007~
- 粉丝: 3868
- 资源: 3126
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功