能否写出高效的代码，要看你对所使用的数据结构的了解程度。实际上，当你用一段程序解决一个问题时，这段程序是否高效的因素之一就是是否选对了数据结构来解决问题。这次我们就聊聊 list 和 tuple，看看怎样使用它们才能更高效。
list 和 tuple 是一类数据结构，也就是我们常见的数组。一个数组就是一系列数据并隐含有次序的意味在里面。在使用数组时，我们有时候光注重了里面存放的元素，其实次序和元素本身一样重要。另外，还有一个重要的知识点就是，从数组这样的数据结构中获取任意位置的元素的时间复杂度都是 O(1)。
实现数组这种结构有多种多样的方式，每种方式有每种方式的特点，这也是为什么 Python 中有两种数组的实现方式：list 和 tuple。list 是个动态数组，它可以让我们修改其中的值，动态改变 list 的大小；而 tuple 是个静态数组，它的内容是不可改变的。
数组在内存中是一段连续的内存地址，所以只要我们知道了数组的首元素地址，我们就可以知道任意元素的地址了。这也是为什么获取数组任意元素的时间复杂度都是 O(1)了。
如果我们有一个无序的数组，查找其中某个元素的话，最基本的办法就是暴力搜索，其实叫线性搜索。也就是一个元素一个元素的去查找，直到找到为止。线性搜索的时间复杂度最坏情况下是待查元素不在数组中，即 O(n)。别怪我没告诉你，list.index() 使用的就是线性搜索算法。
如果你经常在无序的数据中查找某值，哈希表是更好的选择。当然，假如你在有序的数组中查找某值，那又另当别论，我们有更好的算法来把时间复杂度降低到 O(log n) 级别。悄悄地告诉你，二分搜索算法。
既然现在我们得知在有序数组中查找元素的效率更高，那我们就可以把问题转化为了无序数组变成有序数组，这个问题进一步退化为数组中元素如何比较的问题。我们知道用户自定义对象的比较是通过 eq 和 lt 魔法函数来进行的。
小提示：如果自定义对象没有实现上面两个函数，那么将只能比较同类型对象，并且比较的方式是实例的内存占用地址。如果实现了上面两个函数，我们可以使用 Python 标准库中提供的 functools.total_ordering 装饰器来装饰该对象，它会帮你实现其他的比较魔法函数，比如 gt 等等。
list 内建的排序算法是 Timsort。Timsort最好情况下的时间复杂度是 O(n)，最差是 O(n log n)。它会利用多类型排序算法和启发式算法来判断哪种算法更合适——插入排序算法或者归并排序算法。
在数组有序的情况下，二分搜索比把数据转换为字典再搜索要更有效率的多（虽然字典搜索的时间复杂度是 O(1)，但转换数据的时间要花费 O(n)的时间）。
Python 标准库提供了一个模块 bisect。它为我们提供了简单的办法来保证在 list 添加元素后是有序的。用法如下：
import bisect
import random
nums = []
for i in range(10):
new_num = random.randint(0, 1000)
bisect.insort(nums, new_num)
print(nums) # 有序数组
练习题：请写一函数，接收两个参数，第一个参数是个数字数组，第二个参数是个数字，函数的返回值为数字数组中与第二个参数最接近的数字的索引值。如有疑问请关注“读一读我”公众号。
tuple 和 list 都可以存储不同类型的值，这会导致性能损耗和一些优化的缺失，因此，为了更好的性能，我们尽量存储同类型数据。另外这一点也暗示了泛型编程要比具体类型编程要慢。
list 是动态数组，添加元素时会进行动态扩容，动态扩容意味着新建一个 size 为 J 的数组，假设原数组的 size 为 K，那么 J > K。这个 J 的取值在 Python 3.7 中是这样得来的：
J = (K >> 3) + (3 if K < 9 else 6)
套用这个公式，我们得知原数组 size 越大，额外扩容的空间就会越大，比如 size 为 1 的数组，添加新元素时扩容到 size 为 4，而 size 为 8000 的数组，就要扩容到 8600，这是相当昂贵的操作。
下图对比了使用 append 和列表解析创建 list 内存与时间上的差异：
tuple 是静态数组，不支持修改操作，不支持扩容操作，但我们可以合并两个 tuple，合并类似于扩容，但不需要额外的空间。合并操作总是重新生成一个新的 tuple，也就是重新申请内存地址存放合并后的内容。
list 在不进行 append 操作的情况下，内存也比 tuple 占用的多，因为 list 要用额外一个空间存放数组的大小作为将来扩容的依据。
tuple 是会被 Python 运行时缓存的。我们知道 Python 是自动垃圾回收的，意思是当一个变量不再被使用时，Python 运行时会释放该变量内存还给操作系统。对一个 size 大小为 1-20 的 tuple 来说，当不再使用时，Python 并不会立即释放它占用的内存，这样的 tuple 大概会被缓存至多 20000 个。也就是说，当我们日后再次使用 tuple 时，就不需要去和操作系统打交道申请内存空间了（和操作系统的通信，操作系统寻找可使用的内存空间，这都是很昂贵的操作），直接使用被缓存的空间即可。当然，这也恰恰说明了 Python 运行时会占用更大的内存。
下图为创建 list 和 tuple时间上的对比：
今天就到这里了，有任何问题请添加公众号“读一读我”。
网友评论