Python高性能编程第3版3列表和元组

3 列表和元组

主要内容：

• 列表和元组有什么用？
  
• 在列表/元组中查找的复杂性是什么？
  
• 如何实现这种复杂性？
  
• 列表和元组有哪些区别？
  
• 如何对列表进行追加？
  
• 什么时候应该使用列表和元组？
  

编写高效程序最重要的一点是了解所使用数据结构的保证。事实上，高效编程的很大一部分就是要知道你想对数据提出什么问题，并选择一种能快速回答这些问题的数据结构。在本章中，我们将讨论列表和元组可以快速回答哪些类型的问题，以及它们是如何做到这一点的。
列表和元组是一类名为数组的数据结构。数组是具有某种内在排序的扁平数据列表。通常在这类数据结构中，元素的相对排序和元素本身一样重要！此外，这种对排序的先验知识非常有价值：通过知道数组中的数据位于特定位置，我们可以在 O(1) 的时间内检索到这些数据！实现数组的方法也有很多种，每种方案都有其有用的特性和保证。这就是为什么在 Python 中我们有两种数组类型：列表和元组。列表是动态数组，允许我们修改和调整存储数据的大小，而元组是静态数组，其内容是固定不变的。
让我们来解读一下前面的表述。计算机上的系统内存可以看作是一系列编号的桶，每个桶都可以存储一个数字。Python 通过引用将数据存储在这些桶中，这意味着数字本身只是指向或引用我们实际关心的数据。因此，这些桶可以存储我们想要的任何类型的数据（而 numpy 数组则不同，它有一个静态类型，只能存储该类型的数据）。
当我们要创建数组（以及列表或元组）时，首先必须分配一个系统内存块（该内存块的每一部分都将用作实际数据的整数大小指针）。这需要进入系统内核，请求使用 N 个连续的内存桶。下图显示了大小为 6 的数组（本例中为列表）的系统内存布局示例。

注意：在 Python 中，列表也存储它们的大小，因此在分配的六个块中，只有五个是可用的--第三个元素是长度。
为了查找列表中的任何特定元素，我们只需知道我们想要的元素，并记住我们的数据是从哪个存储桶开始的。由于所有数据将占用相同的空间（一个 “桶”，或者更具体地说，一个指向实际数据的整数大小的指针），因此我们不需要知道存储的数据类型来进行计算。
如果你知道由 N 个元素组成的列表在内存中的起始位置，你将如何在列表中查找任意元素？
例如，如果我们需要检索数组中的第零个元素，我们只需转到序列中的第一个存储桶 M，然后读出其中的值。另一方面，如果我们需要数组中的第五个元素，我们就会转到位于 M + 5 位置的桶，然后读取其中的内容。因此，通过将数据存储在连续的存储桶中，并了解数据的排序，无论数组有多大，我们都可以通过一步（或 O(1)）就知道要查看哪个存储桶来定位数据（例 3-1）。
例 3-1. 不同大小列表中的查找计时

1. >>> %%timeit l = list(range(10))
2.         ...: l[5]
3.         ...:
4. 14 ns ± 0.182 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
6. >>> %%timeit l = list(range(10_000_000))
7.         ...: l[100_000]
8.         ...:
9. 13.9 ns ± 0.123 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

复制代码

如果给我们一个顺序未知的数组，并希望检索某个特定元素，该怎么办？如果排序已知，我们只需查找该特定值即可。但在这种情况下，我们必须进行搜索操作。解决这个问题的最基本方法是线性搜索，我们遍历数组中的每个元素，检查它是否是我们想要的值，如例 3-2 所示。
例 3-2. 对列表进行线性搜索
[code]import timeitdef linear_search(needle, array):    for i, item in enumerate(array):        if item == needle:            return i    return -1if __name__ == "__main__":    setup = "from __main__ import (linear_search, haystack, needle)"    iterations = 1000    for haystack_size in (10000, 100000, 1000000):        haystack = range(haystack_size)        for needle in (1, 6000, 9000, 1000000):            index = linear_search(needle, haystack)            t = timeit.timeit(                stmt="linear_search(needle, haystack)", setup=setup, number=iterations            )            print(                f"Value {needle: