《高性能 Python》第二版

第 3 章 列表和元组 列表和元组

本作品已使用人工智能进行翻译。欢迎您提供反馈和意见：[e-mail]

读完本章后您将能够回答的问题

• 列表和元组有什么用？

• 列表/元组中查找的复杂程度如何？

• 如何实现这种复杂性？

• 列表和元组有什么区别？

• 如何对列表进行追加？

• 何时使用列表和元组？

编写高效程序最重要的一点是了解所使用数据结构的保证。事实上，高效编程的很大一部分就是要知道你想对数据提出什么问题，并选择一种能快速回答这些问题的数据结构。 在本章中，我们将讨论列表和元组能快速回答哪些类型的问题，以及它们是如何做到这一点的。

列表和元组是一类数据结构，称为数组。数组是具有某种内在排序的平面数据列表。通常在这类数据结构中，元素的相对排序和元素本身一样重要！ 此外，这种关于排序的先验知识非常有价值：知道数组中的数据位于特定位置后，我们就可以在O(1) 中检索这些数据！¹ 实现数组的方法也有很多种，每种方案都有其有用的特性和保证。这就是为什么在 Python 中我们有两种数组：列表和元组。列表是动态数组，允许我们修改和调整存储数据的大小，而图元是静态数组，其内容是固定不变的。

让我们来解读一下前面的陈述。计算机上的系统内存可以看作是一系列有编号的桶，每个桶都可以存储一个数字。Python通过引用将数据存储在这些桶中，这意味着数字本身只是指向或引用我们实际关心的数据。因此，这些桶可以存储我们想要的任何类型的数据 (而numpy 数组则不同，它有一个静态类型，只能存储该类型的数据)。²

当我们要创建一个数组（也就是列表或元组）时，首先必须分配一个系统内存块（该内存块的每一部分都将用作实际数据的整数大小指针）。这需要向系统内核申请使用N 连续的内存桶。图 3-1显示了大小为 6 的数组（这里是列表）的系统内存布局示例。

备注

在 Python 中，列表也会存储它们的大小，因此在六个分配的块中，只有五个是可用的--第零个元素就是长度。

图 3-1. 大小为 6 的阵列的系统内存布局示例

要查找列表中的任何特定元素，我们只需知道我们想要的元素，并记住数据是从哪个数据桶开始的。由于所有数据将占用相同的空间（一个 "桶"，或者更具体地说，一个指向实际数据的整数大小的指针），因此我们不需要知道存储的数据类型来进行计算。

提示

如果你知道N 元素列表在内存中的起始位置，你将如何在列表中找到任意元素？

例如，如果我们需要检索数组中的第零个元素，我们只需转到序列中的第一个存储桶M ，然后读出其中的值。另一方面，如果我们需要数组中的第五个元素，我们将转到位置M + 5 的存储桶，然后读出其中的内容。一般来说，如果我们想从数组中检索元素i ，我们就会转到M + i 的存储桶。因此，通过将数据存储在连续的数据桶中，并了解数据的排序，无论数组有多大，我们都可以通过一步（或O(1) ）知道要查看哪个数据桶来定位数据（例 3-1）。

例 3-1. 不同大小列表中的查找计时

>>> %%timeit l = list(range(10))
        ...: l[5]
        ...:
30.1 ns ± 0.996 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops ...