Python高性能编程3版：列表与元组的高效探索

Python高性能编程3版：列表与元组的高效探究

3 列表与元组

主要内容

• 列表和元组的功用是什么？
• 在列表或元组中进行查找的复杂度情况怎样？
• 如何达成这种复杂度？
• 列表和元组有哪些差异？
• 怎样对列表进行追加操作？
• 何时该选用列表或元组？

高效编写程序的关键之一在于明晰所使用数据结构所具备的特性。高效编程很大程度上是要明确你对数据提出何种问题，并选取能快速回应这些问题的数据结构。在本章里，我们会探讨列表和元组能够快速回应哪些类型的问题，以及它们是怎样做到的。

列表和元组属于数组这类数据结构。数组是有着内在排序的扁平数据列表。通常在这类数据结构中，元素的相对顺序和元素自身同等重要！并且，这种对顺序的先验认知极为宝贵：凭借知晓数组中的数据处于特定位置，我们能够在O(1)的时间内获取这些数据！实现数组的方式有诸多，每种方案都有其有用的特性和保障。这就是为何在Python中有两种数组类型：列表和元组。列表是动态数组，允许我们修改并调整存储数据的大小，而元组是静态数组，其内容固定不变。

来解读一下上述表述。计算机的系统内存可看作是一系列编号的桶，每个桶能存储一个数字。Python通过引用来将数据存储在这些桶中，这意味着数字本身只是指向我们真正关心的数据的引用。所以，这些桶能够存储我们想要的任何类型的数据（而numpy数组不同，它有静态类型，只能存储该类型的数据）。

当我们要创建数组（以及列表或元组）时，首先得分配一块系统内存（这块内存的每一部分将用作实际数据的整数大小指针）。这需要调用系统内核，请求使用N个连续的内存桶。下图展示了大小为6的数组（本例中为列表）的系统内存布局示例。

注意：在Python中，列表也存储它们的大小，所以在分配的六个块中，只有五个是可用的——第三个元素是长度。

若要查找列表中的任意特定元素，我们只需知道想要的元素，并记住数据从哪个存储桶起始。由于所有数据占用相同空间（一个“桶”，更确切地说，是一个指向实际数据的整数大小指针），所以无需知晓存储数据的类型来进行计算。

若已知由N个元素组成的列表在内存中的起始位置，该如何在列表中查找任意元素呢？比如，若我们要获取数组中的第零个元素，只需转到序列中的第一个存储桶M，然后读出其中的值。反之，若要获取数组中的第五个元素，就转到位于M + 5位置的桶，再读取其中内容。所以，通过将数据存储在连续的桶中，并知晓数据的顺序，无论数组大小如何，我们都能通过一步（即O(1)）就确定要查看哪个桶来定位数据（例3-1）。

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

>>> %%timeit l = list(range(10))
...: l[5]
...:
14 ns ± 0.182 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

>>> %%timeit l = list(range(10_000_000))
...: l[100_000]
...:
13.9 ns ± 0.123 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

要是给我们一个顺序未知的数组，想要检索某个特定元素，该怎么办呢？若顺序已知，只需查找该特定值即可。但这种情况下，就得进行搜索操作。最基本的解决办法是线性搜索，我们遍历数组中的每个元素，检查是否是想要的值，如例3-2所示。

例3-2. 对列表进行线性搜索

import timeit


def linear_search(needle, array):
    for i, item in enumerate(array):
        if item == needle:
            return i
    return -1


if __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: <8} found in haystack of "
                f"size {len(haystack): <8} at index "
                f"{index: <8} in {t/iterations:.5e} seconds"
            )

执行结果：

# python linear_search.py
Value 1        found in haystack of size 10000    at index 1        in 1.32893e-07 seconds
Value 6000     found in haystack of size 10000    at index 6000     in 2.02747e-04 seconds
Value 9000     found in haystack of size 10000    at index 9000     in 3.04364e-04 seconds
Value 1000000  found in haystack of size 10000    at index -1       in 3.49609e-04 seconds
Value 1        found in haystack of size 100000   at index 1        in 1.31818e-07 seconds
Value 6000     found in haystack of size 100000   at index 6000     in 2.06552e-04 seconds
Value 9000     found in haystack of size 100000   at index 9000     in 3.20001e-04 seconds
Value 1000000  found in haystack of size 100000   at index -1       in 3.51215e-03 seconds
Value 1        found in haystack of size 1000000  at index 1        in 1.31243e-07 seconds
Value 6000     found in haystack of size 1000000  at index 6000     in 1.98086e-04 seconds
Value 9000     found in haystack of size 1000000  at index 9000     in 3.07604e-04 seconds
Value 1000000  found in haystack of size 1000000  at index -1       in 3.37868e-02 seconds

这种算法的最差性能是O(n)。当搜索不在数组中的元素时，就会出现这种情况。要知道要搜索的元素不在数组中，就得先将它与其他元素核对。最终会执行到最后的return -1语句。实际上，这种算法正是list.index()所采用的算法。

要提升速度，唯一的办法是了解数据在内存中的放置方式，或者我们所拥有的数据桶的排列方式。例如，哈希表（“字典和集合是如何工作的？”）是字典和集合的基础数据结构，它通过在插入/检索时增加额外开销并强制对项目进行严格且特殊的排序，以O(1)的速度解决了这个问题。另外，如果对数据进行排序，使每个条目都比左边（或右边）的相邻条目大（或小），那么就可以使用专门的搜索算法，将查找时间降低到O(log n)。不过，有时使用这些搜索算法是最佳解决方案（尤其是搜索算法非常灵活，允许以创造性的方式定义搜索）。

练习

给定如下数据，编写算法来查找值61的索引：[9, 18, 18, 19, 29, 42, 56, 61, 88, 95]
已知数据是有序的，怎样能更快完成呢？
提示：若将数组一分为二，就能知晓左边所有值都小于右边集合中最小的元素。可利用此方法！

3.1 更高效的搜索

如前所述，若先对数据进行排序，使某一项左边的所有元素都比该项小（或大），就能获得更好的搜索性能。比较是通过对象的eq和lt魔法函数完成的，若使用自定义对象，也可由用户自定义。

若没有eq和lt方法，自定义对象将仅与相同类型的对象比较，比较会使用实例在内存中的位置。定义了这两个魔法函数后，可使用标准库中的functools.total_ordering装饰器自动定义所有其他排序函数，尽管性能会有少许损失。

必要的两个要素是排序算法和搜索算法。Python列表有内置的使用Tim排序的排序算法。在最佳情况下，Tim排序能以O(n)的速度对列表排序（在最差情况下，排序速度为O(n log n)）。它通过结合多种类型的排序算法，并运用启发式方法猜测在给定数据下哪种算法性能最佳来实现这一性能（更确切地说，它混合了插入和合并排序算法）。

对列表排序后，可使用二进制搜索（例3-3）找到所需元素，其平均复杂度为O(log n)。它首先查看列表的中点，然后将该值与所需值比较。若这个中点的值小于我们期望的值，就考虑列表的右半部分，如此继续将列表减半，直到找到该值，或确定该值不在排序列表中。所以，无需像线性搜索那样读取列表中的所有值，只需读取其中一部分。

例3-3. 高效搜索排序列表--二进制搜索

import timeit


def binary_search(needle, haystack):
    # imin和imax存储当前考虑的haystack的边界。初始为haystack的边界，逐渐收敛到包围needle。
    imin, imax = 0, len(haystack)
    while True:
        if imin >= imax:
            return -1
        midpoint = (imin + imax) // 2
        if haystack[midpoint] > needle:
            imax = midpoint
        elif haystack[midpoint] < needle:
            imin = midpoint + 1
        else:
            return midpoint


if __name__ == "__main__":
    setup = "from __main__ import (binary_search, haystack, needle)"
    iterations = 10000

    for haystack_size in (10000, 100000, 1000000):
        haystack = range(haystack_size)
        for needle in (1, 6000, 9000, 1000000):
            index = binary_search(needle, haystack)
            t = timeit.timeit(
                stmt="binary_search(needle, haystack)", setup=setup, number=iterations
            )
            print(
                f"Value {needle: <8} found in haystack of "
                f"size {len(haystack): <8} at index "
                f"{index: <8} in {t/iterations:.5e} seconds"
            )

执行结果：

# python binary_search.py
Value 1        found in haystack of size 10000    at index 1        in 9.15618e-07 seconds
Value 6000     found in haystack of size 10000    at index 6000     in 1.24657e-06 seconds
Value 9000     found in haystack of size 10000    at index 9000     in 1.21479e-06 seconds
Value 1000000  found in haystack of size 10000    at index -1       in 1.66498e-06 seconds
Value 1        found in haystack of size 100000   at index 1        in 1.15999e-06 seconds
Value 6000     found in haystack of size 100000   at index 6000     in 1.76719e-06 seconds
Value 9000     found in haystack of size 100000   at index 9000     in 1.57295e-06 seconds
Value 1000000  found in haystack of size 100000   at index -1       in 2.03157e-06 seconds
Value 1        found in haystack of size 1000000  at index 1        in 1.36514e-06 seconds
Value 6000     found in haystack of size 1000000  at index 6000     in 1.74420e-06 seconds
Value 9000     found in haystack of size 1000000  at index 9000     in 1.96218e-06 seconds
Value 1000000  found in haystack of size 1000000  at index -1       in 2.39626e-06 seconds

通过这种方法，无需使用字典这种可能较重的解决方案就能查找列表中的元素。尤其是当操作的数据列表本质上是有序的时候。在列表中进行二进制搜索查找对象比先将数据转换为字典再进行单次查找更高效。虽然字典查找只需O(1)，但将数据转换为字典需要O(n)（而且字典不限制重复键可能不可取）。而二进制搜索需要O(log n)。

此外，Python标准库中的bisect模块简化了这一过程，除了使用高度优化的二进制搜索查找元素外，还提供了在保持列表有序的同时向列表中添加元素的简便方法。它通过提供替代函数，将元素添加到正确的有序位置。由于列表始终保持有序，很容易找到要找的元素（相关示例可在bisect模块的文档中找到）。此外，还可以使用bisect快速找到最接近的元素（例3-4）。这对比较两个相似但不完全相同的数据集很有用。

例3-4. 使用bisect模块查找列表中的近似值

import bisect
import random


def find_closest(haystack, needle):
    # bisect.bisect_left将返回haystack中第一个大于needle的值
    i = bisect.bisect_left(haystack, needle)
    if i == len(haystack):
        return i - 1
    elif haystack[i] == needle:
        return i
    elif i > 0:
        j = i - 1
        # 由于知道值大于needle（反之亦然对于j处的值），此处无需使用绝对值
        if haystack[i] - needle > needle - haystack[j]:
            return j
    return i


if __name__ == "__main__":
    important_numbers = []
    for i in range(10):
        new_number = random.randint(0, 1000)
        bisect.insort(important_numbers, new_number)

    # important_numbers由于使用bisect.insort插入新元素，已经有序
    print(important_numbers)
    # > [14, 265, 496, 661, 683, 734, 881, 892, 973, 992]

    closest_index = find_closest(important_numbers, -250)
    print(f"Closest value to -250: {important_numbers[closest_index]}")
    # > Closest value to -250: 14

    closest_index = find_closest(important_numbers, 500)
    print(f"Closest value to 500: {important_numbers[closest_index]}")
    # > Closest value to 500: 496

    closest_index = find_closest(important_numbers, 1100)
    print(f"Closest value to 1100: {important_numbers[closest_index]}")
    # > Closest value to 1100: 992

执行结果

[26, 69, 153, 159, 172, 221, 336, 426, 772, 859]
Closest value to -250: 26
Closest value to 500: 426
Closest value to 1100: 859

一般而言，这涉及编写高效代码的基本规则：选择正确的数据结构并坚持使用！虽然