Question

读完本章之后你将能够回答下列问题

列表和元组各自适用于什么情况？

查询列表/元组的复杂度是什么？

该复杂度是如何计算出来的？

列表和元组的区别是什么？

向列表添加新项目是如何实现的？

我应该在什么情况下使用列表和元组？

写高性能程序最重要的事情是了解你的数据结构所能够提供的性能保证。事实上，高性能编程的很大一部分是了解你查询数据的方式，并选择一个能够迅速响应这个查询的数据结构。本章我们将谈论那些列表和元组能迅速响应的查询，以及它们是如何响应的。

列表和元组之类的数据结构被称为数组。一个数组是数据在某种内在次序下的扁平列表。这一先验次序十分重要：知道了数据在数组中的确定位置，我们就能以O(1)的复杂度得到它！另外，数组可以有多种实现方式。下面是列表和元组的另一个区别：列表是动态的数组，而元组则是静态的数组。

让我们回顾一下之前的定义。一台计算机的系统内存可以被看作是一系列编了号的桶，每个桶可以存放一个数字。这些数字可以被用来代表任何我们关心的变量（整数、浮点数、字符串，或其他数据结构），因为它们只是引用了数据被保存在内存中的位置^[1]。

当我们想要创建一个数组（也就是一个列表或元组）时，我们首先必须分配一块系统内存（其每一段都将被当成是一个整型大小的指向实际数据的指针）。这需要进入内核，操作系统的子进程，去申请使用N个连续的桶。图3-1的例子显示了一个大小为6的列表的系统内存布局。注意在Python中列表还记录了它们的大小，所以在分配的6个块中，仅可使用5个——第一个元素是列表的长度。

图3-1　一个长度为6的数组的系统内存布局示例

为了能在我们的列表中查询任意指定元素，我们只需要知道我们想要的是哪个元素以及放数据的起始桶是哪个即可。因为所有的数据都占据同样大小的空间（一个“桶”，或者更确切地说，一个整型大小的指向实际数据的指针），我们不需要知道任何关于被存储数据的类型的信息就能够进行计算。

　问题

如果你知道你的N元素列表从哪里开始，那么你如何查找列表中任意的元素？

假设我们需要获取数组的第一个元素，只需要去第一个桶，M+1，并读出其中的值。（译注：原文这里是M，但是根据上下文应为M+1。）另一方面，如果我们需要数组的第五个元素，可以去位于M+5的桶并读取其内容。总而言之，如果我们想要获取数组的第i个元素，就去桶M+i。也就是说，只要我们的数据保存在连续的桶里且知道数据的顺序，就能一步（O(1)）定位到数据所在的桶，无论我们的数组有多大（见例3-1）。

例3-1　对不同大小的列表进行查询的时间

>>> %%timeit l = range(10)
    ...: l[5]
    ...:
10000000 loops, best of 3: 75.5 ns per loop
>>>
>>> %%timeit l = range(10000000)
    ...: l[100000]
    ...:
10000000 loops, best of 3: 76.3 ns per loop

如果我们拿到的是一个未知次序的数组，又该如何获取某个元素？如果是次序已知的数组，我们可以直接查询指定的值。而在次序未知的情况下，我们必须进行搜索操作。解决这个问题最基本的方法叫“线性搜索”，我们遍历数组中的每一个元素并检查其值是否为我们想要的，见例3-2。

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

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

这个算法的最差情况性能是O(n)。最差情况发生在当我们搜索的东西不存在于数组中时。为了知道我们搜索的元素不存在于数组中，我们必须对所有的元素进行检查。最终我们走到了最后的return -1语句。事实上，这个算法正是list.index()使用的算法。

唯一提升速度的方法是了解数据如何存放在内存中，或者说了解存放我们数据的桶的组织方式。比如，散列表，一个用于实现字典和集合的基本数据结构，通过丢弃数据的原始次序并指定另外一种次序，或者更确切地说，另外一种数据组织方式，能够以O(1)的复杂度解决这个问题。又比如说，如果你的数据是排过序的，每一个元素都大于（或小于）位于其左边（或右边）的相邻元素，那么一个特化的搜索算法可以将你的搜索时间降至O(log n)。我们之前的常数时间的查找不需要排序这一步骤，然而在某些时候，先排序后搜索是最佳的选择（特别是因为这可以让搜索算法更为灵活且允许你创出新的搜索方式）。

　问题　

给定下列数据，写一个算法找到值61的索引：

[9, 18, 18, 19, 29, 42, 56, 61, 88, 95]

已知数据经过排序，你如何可以做得更快？

{提示：} 如果你将数组对半分，你知道左半边所有的值都小于右半边最小的元素。你可以利用这点！