Python学习之路21-序列构成的数组

摘要：第行把具名元组以的形式返回。对序列使用和通常号两侧的序列由相同类型的数据所构成当然不同类型的也可以相加，返回一个新序列。从上面的结果可以看出，它虽抛出了异常，但仍完成了操作查看字节码并不难，而且它对我们了解代码背后的运行机制很有帮助。

《流畅的Python》笔记。
接下来的三篇都是关于Python的数据结构，本篇主要是Python中的各序列类型

Python标准库用C实现了丰富的序列类型，可分为两大类：

容器序列：list，tuple和collections.deque等这些序列能存放不同类型的数据。

扁平序列：str，bytes，bytearray，memoryview和array.array等，这些序列只能容纳一种类型。

容器序列存放的是它们所包含的任意类型的对象的引用，而扁平序列存放的是值而不是引用。即，扁平序列其实是一段连续的内存空间，更加紧凑。

序列类型还可以按能否被修改来分来：

可变序列（MutableSequence）：list，bytearray，array.array，collections.deque和memoryview；

不可变序列（Sequence）：tuple，str和byte。

以下是这两大类的继承关系：

虽然Python中内置的序列类型并不是直接从Sequence和MutableSequence这两个抽象基类继承而来，但了解这些基类可以总结出那些完整的序列类型包含了哪些功能，以及将上述两种分类方式融会贯通。

下面我们从最常用的列表（list）开始。

列表推导（list comprehension，简称listcomps）是构建列表的快捷方式，而生成器表达式（generator expression, 简称genexps）则可以用来创建其它任何类型的序列。

有时候，比起用for循环，列表推导可能会更简单可读。通常的原则是，只用列表推导来创建新的列表，并且尽量保持简短。如果列表推导的代码超过了两行，应该考虑是不是得用for循环重写，不过这个度得自己把握。（句法提示：Python会忽略[],{},()中的换行，所以可以省略不太好看的换行符)

注意：在Python3中，列表推导、生成器表达式，以及和它们很相似的集合（set）推导和字典（dict）推导都有了自己的局部作用域，不会影响外部的同名变量（Python2中则可能会影响），如下：

>>> x = "a"
>>> test = [x for x in "ABC"]
>>> x
"a"   # 在Python2中，该结果则可能是 "C"

列表推导可以过滤或加工一个序列或其他可迭代类型中的元素，然后生成一个新列表。而Python内置的filter和map函数组合起来也能达到这一效果（一般需要借助lambda表达式），但可读性却比不上列表推导，比如下面的代码：

>>> symbols = "ABCDEFG"
>>> ascii = [ord(s) for s in symbols if ord(s) > 66]
>>> ascii
[67, 68, 69, 70, 71]
>>> ascii = list(filter(lambda c: c > 66, map(ord, symbols)))
>>> ascii
[67, 68, 69, 70, 71]

原本以为map/filter组合起来会比列表推导快一些，但有测试证明该结论不一定成立。对于map, filter的详细介绍将放在后面的文章中。

简单说就是简化嵌套for循环，例子如下：

colors = ["black", "white"]
sizes = ["S", "M", "L"]
tshirts = [(color, size) for color in colors for size in sizes]

tshirts_for = [] # 最后它的内容等价于上面的tshirts
for color in colors:
    for size in sizes:
        tshirts_for.append((color, size))

列表推导的作用只有一个：生成列表。如果想生成其他类型的序列，则需要使用生成器表达式。

虽然也可以用列表推导式来初始化元组，数组或其他序列类型，但生成器表达式是更好的选择，因为生成器表达式背后遵循了迭代器协议，可以逐个生成元素（可节省内存），而不是一次性生成所有元素。

生成器表达式语法跟列表推导差不多，只是把方括号换成了圆括号而已，如下：

>>> symbols = "ABCDEFG"
>>> tuple(ord(symbol) for symbol in symbols)  # ①
(65, 66, 67, 68, 69, 70, 71)
>>> import array
>>> array.array("I", (ord(symbol) for symbol in symbols))  # ②
array("I", [65, 66, 67, 68, 69, 70, 71])

①如果生成器表达式是一个函数调用过程中的唯一参数，则可不加括号将其围起来；

②array的构造方法需要两个参数，因此括号是必需的。

下面用生成器表达式改写上面的笛卡尔积代码：

colors = ["black", "white"]
sizes = ["S", "M", "L"]
for tshirt in ("%s %s" % (c, s) for c in colors for s in sizes):
    print(tshirts)

# 结果：
black S
black M
black L
white S
white M
white L

生成器表达式逐个生成元素，不会一次性生成一个含有6个元素的列表。关于生成器表达式的工作原理将在后面的文章中介绍。

元组除了用作不可变的列表，它还可以用于没有字段名的记录，比如坐标，身份信息等，这里不再举例。

此概念之前涉及过，这里将其总结一下：

# 平行赋值
a, b = ("test1", "test2")
# 不用中间变量交换两个变量的值
b, a = a, b
# *号运算将可迭代对象拆开作为函数参数
t = (20, 8)
divmod(*t)  # 该函数的意思是： 20 ÷ 8 = 2 …… 4， 函数返回商和余数的元组
# 用*来处理剩下的元素，Python3支持
a, b, *rest = range(5)  # rest的值为[2, 3, 4]
a, b, *rest = range(3)  # rest的值为[2]
a, b, *rest = range(2)  # rest的值为[]
# 在平行赋值中，*前缀只能用在一个变量前，但该变量可在任意位置
>>> a, *body, c, d = range(5) # 值依次为 0, [1, 2], 3, 4
>>> *head, b, c, d = range(5) # 值依次为 [0, 1], 2, 3, 4

接受表达式的元组可以是嵌套式的，例如(a, b, (c, d))，只要这个接受元组的嵌套结构符合表达式本身的嵌套结构，以下用嵌套元组来获取经纬度：

metro_areas = [
    ("Tokyo", "JP", 36.933, (35.689722, 139.691667)),
    ("Delhi NCR", "IN", 21.935, (28.613889, 77.208889)),
    ("Mexico City", "MX", 20.142, (19.433333, -99.133333)),
    ("New York-Newark", "US", 20.104, (40.808611, -74.020386)),
    ("Sao Paulo", "BR", 19.649, (-23.547778, -46.635833)),
]

print("{:15} | {:^9} | {:^9}".format(" ", "lat.", "long."))
fmt = "{:15} | {:9.4f} | {:9.4f}"
# 把输入元组的最后一个元素拆包到由变量构成的元组中
for name, cc, pop, (latitude, longitude) in metro_areas:
    if longitude <= 0:
        print(fmt.format(name, latitude, longitude))
        
# 结果：
                |   lat.    |   long.  
Mexico City     |   19.4333 |  -99.1333
New York-Newark |   40.8086 |  -74.0204
Sao Paulo       |  -23.5478 |  -46.6358

上篇中有所涉及。collections.namedtuple是一个工厂函数，它可以创建一个带字段名的元组和一个有名字的类——这个带名字的类对调试程序有很大帮助。

namedtuple构造的类的实例所消耗的内存跟元组是一样的，因为字段名都存在对于的类中。这个实例跟普通对象实例比起来要小一些，因为Python不会用__dict__来存放这些实例的属性。

from collections import namedtuple

City = namedtuple("City", "name country population coordinates")
tokyo = City("Tokyo", "JP", 36.933, (35.689722, 139.691667))
print(tokyo)
print(tokyo.population)
print(tokyo[1])

print(City._fields)
LatLong = namedtuple("LatLong", "lat long")
delhi_data = ("Delhi NCR", "IN", 21.935, LatLong(28.613889, 77.208889))
delhi = City._make(delhi_data)
print(delhi._asdict())
for key, value in delhi._asdict().items():
    print(key + ":", value)

# 结果：
City(name="Tokyo", country="JP", population=36.933, coordinates=(35.689722, 139.691667))
36.933
JP
("name", "country", "population", "coordinates")
OrderedDict([("name", "Delhi NCR"), ("country", "IN"), ("population", 21.935),
             ("coordinates", LatLong(lat=28.613889, long=77.208889))])
name: Delhi NCR
country: IN
population: 21.935
coordinates: LatLong(lat=28.613889, long=77.208889)

第3行：创建一个具名元组需要两个参数，一个是类名，一个是类的各字段名。后者可以是由数个字符串组成的可迭代对象，或者是由空格分隔的字符串；

第6,7行：可通过字段名或位置来获取一个字段的信息；

第9行：_fields属性是一个包含这个类所有字段名的元组；

第12行：_make()通过接受一个可迭代对象来生成这个类的一个实例，它的作用跟City(*delhi_data)是一样的。

第13行：_asdict()把具名元组以collections.OrderedDict的形式返回。

注意第10，27行！

除了跟增减元素相关的方法外，元组支持列表的其他所有方法。还有一个例外就是元组没有__reversed__方法，但这方法只是个优化，reversed(my_tuple)这个方法在没有__reversed__的情况下也是合法的。

切片在Python基础中介绍了一些遍历的基本操作，这里补充一些高级的用法。

>>> test = list(range(6))
>>> test
[0, 1, 2, 3, 4, 5]
# 指定步长赋值
>>> test[3::2] = [11, 22]
>>> test
[0, 1, 2, 11, 4, 22]
# 将列表变长（也可以变短）
>>> test[1:3] = [7, 8, 9]
>>> test
[0, 7, 8, 9, 11, 4, 22]
>>> test[1:3] = 100
Traceback (most recent call last):
  File "", line 1, in 
TypeError: can only assign an iterable
>>> test[1:3] = [100]
[0, 100, 9, 11, 4, 22]

Python中有一个切片类（slice），可以用它创建切片对象：

temp = "adfadfadfadfafasdf"
TEST = slice(2, 8)  # 一般大写
print(temp[TEST])

# 结果：
fadfad

[ ]运算符中还可以使用以逗号分开的多个索引或者切片，比如第三方库Numpy中就用到了这个特性，二维的numpy.ndarray就可以用a[i, j]来获取值（这里的语法和C#一样，相当于C/C++中的a[i][j]），或者a[m:n, k:l]来获得二维切片。要正确处理这种语法，对象的特殊方法__getitem__和__setitem__需要以元组的形式来接收a[i, j]中的索引，即，如果要得到a[i, j]，Python会调用a.__getitem__((i, j))。关于多维切片的例子在本文后面演示。

省略（ellipsis）的写法是三个英语句点（...)，而不是Unicode码位U+2026表示的半个省略号（和前面三个句点几乎一模一样）。省略在Python解释器眼里是一个符号，而实际上它是Elllipsis对象的别名，而Ellipsis对象又是ellipsis类的单一实例（ellipsis是类名，全小写，而它的内置实例写作Ellipsis。这跟bool是小写，而它的两个实例True和False是大写一个道理）。它可以当做切片规范的一部分，也可用在函数的参数列表中，如f(a,...,z)，或a[i: ...]。在Numpy中，...用作多维数组切片的快捷方式，即x[i, ...]就是x[i, :, :, :]的缩写。

笔者暂时还没发现Python标准库中有任何Ellipsis或者多维索引的用法。这些句法上的特性主要是为了支持用户自定义类或者扩展，Numpy就是一个例子。

通常+号两侧的序列由相同类型的数据所构成（当然不同类型的也可以相加），返回一个新序列。如果想把一个序列复制几份再拼接，更快捷的做法是乘一个整数：

>>> [1, 2] + [3]
[1, 2, 3]
>>> [1, 2] * 2
[1, 2, 1, 2]
>>> 5 * "abc"
"abcabcabcabcabc"

注意：这里有深浅复制的问题，如果在A * n这个语句中，序列A中的元素b是对其他可变对象的引用的话，则新序列中A2中的n个元素b1……bn都指向同一个位置，即对b1到bn中任意一个赋值，都会影响其他元素。下面以一个创建多维数组的例子来说明这个情况（字符串是不可变对象，而列表是可变对象！）：

正确的写法：

board = [["_"] * 3 for i in range(3)]
print(board)
board[1][2] = "X"
print(board)
# 等价于：
board = []
for i in range(3):
    row = ["_"] * 3
    board.append(row)

# 结果：
[["_", "_", "_"], ["_", "_", "_"], ["_", "_", "_"]]
[["_", "_", "_"], ["_", "_", "X"], ["_", "_", "_"]]

错误的写法：

weird_board = [["_"] * 3] * 3
print(weird_board)
weird_board[1][2] = "X"
print(weird_board)
# 等价于：
weird_board = []
row = ["_"] * 3
for i in range(3):
    weird_board.append(row)

# 结果：
[["_", "_", "_"], ["_", "_", "_"], ["_", "_", "_"]]
[["_", "_", "X"], ["_", "_", "X"], ["_", "_", "X"]]

增量赋值运算符+=和*=的表现取决于它们的第一个操作对象，以+=为例。+=背后的特殊方法是__iadd__(用于“就地加法”)，如果一个类没有实现该方法，则会调用__add__。例如 a += b，如果a实现了__iadd__，则直接调用该方法，修改的是a，不会产生新对象，而如果没有实现该方法，则会调用__add__，执行的运算实际是 a = a + b，该运算会生成一个新变量，存储a + b的结果，然后再把该新变量赋值给a。

总体来说，可变序列一般都实现了__iadd__，而不可变序列根本就不支持这个操作。对不可变序列执行重复拼接操作的话，效率很低，因为每次都会生成新对象，而解释器需要把原来对象中的元素先复制到新对象中，然后再追加新元素。但str是个例外，因为对字符串做+=操作是在太普遍了，于是CPython对它做了优化：str初始化时，程序会为它预留额外的可扩展空间，因此做增量操作时不会涉及复制原有字符串到新位置的操作。

对于以下操作，大家猜想会得到什么样的结果：

>>> t = (1, 2, [3, 4])
>>> t[2] += [5, 6]

它的结果是报错，但t依然被改变了：

# 紧接上述代码
Traceback (most recent call last):
  File "", line 1, in 
TypeError: "tuple" object does not support item assignment
>>> t
(1, 2, [3, 4, 5, 6])
# 如果是t[2].extend([5, 6])则不会报错

如果我们看Python表达式 s[a] += b的字节码，便不难理解上述结果：

>>> import dis
>>> dis.dis("s[a] += b")
  1           0 LOAD_NAME                0 (s)
              2 LOAD_NAME                1 (a)
              4 DUP_TOP_TWO
              6 BINARY_SUBSCR
              8 LOAD_NAME                2 (b)
             10 INPLACE_ADD
             12 ROT_THREE
             14 STORE_SUBSCR
             16 LOAD_CONST               0 (None)
             18 RETURN_VALUE

从上述结果可以看出：

第6行：将s[a]的值存入TOS(Top Of Stack，栈顶)；

第8行：计算TOS += b， 这一步能够完成，因为TOS指向一个可变对象；

第14行：s[a] = TOS，报错，因为s是个元组，不可变。

从上述操作可以得到3个教训：

不要把可变对象放在元组中；

增量赋值不是一个原子操作。从上面的结果可以看出，它虽抛出了异常，但仍完成了操作；

查看Python字节码并不难，而且它对我们了解代码背后的运行机制很有帮助。

bisect模块包含两个主要函数，bisect和insort，这两个函数都利用二分查找算法在有序列表中查找或插入元素。

bisect用于查找元素的位置：biisect(haystack, needle)。它返回needle在haystack中的位置index，如果要插入元素，可以在找到位置后，再调用haystack.insert(index, new_ele)，但也可以用bisect模块中的insert直接插入，并且该方法速度更快。

Python的高产贡献者Raymond Hettinger写了一个排序集合模块sortedcollection，该模块集成了bisect功能，且比独立的bisect更易用。

bisect需要注意两点：

两个可选参数lo和hi：lo默认值是0，hi默认值是序列的长度，即len()作用域该序列的返回值。

bisect函数其实是bisect_right函数的别名，它返回的位置是与needle相等的元素的后一个位置，而它的兄弟函数bisect_left则返回的是与needle相等的元素的位置。

>>> import bisect
>>> test = [1, 2, 3, 4, 5, 6, 7]
>>> bisect.bisect(test,1)
1
>>> bisect.bisect_left(test,1)
0

相应的，模块中insort也有两个版本，insort是insort_right的别名，它也有两个可选参数lo和hi，insort_left的背后调用的就是bisect_left。

>>> bisect.insort(test, 1.0)
>>> test
[1, 1.0, 2, 3, 4, 5, 6, 7]
>>> bisect.insort_left(test, 1.0)
>>> test
[1.0, 1, 1.0, 2, 3, 4, 5, 6, 7]

当我们有特定的数据集时，list并不一定是首选，比如存放1000万个浮点数，数组（array）的效率就要高很多，因为数组的背后并不是float对象，而是数字的机器翻译，也就是字节表述。这点和C语言中的数组一样。再比如，如果要频繁对序列做先进先出的操作，deque（双端队列）的速度应该会更快。

如果需要一个只含数字的列表，array.array会比list更高效，它支持所有跟可变列表有关的操作，包括.pop，.insert，.extend等。另外数组还支持从文件读取和存入文件的更快的方法，比如.frombytes和.tofile。

数组跟C语言数组一样精简，创建一个数组需要指定一个类型码，这个类型码用来表示在底层的C语言应该存放怎样的数据类型，以下是array.array的操作例子：

from array import array
from random import random

print("

")
floats = array("d", (random() for i in range(10 ** 7)))
print(floats[-1])
with open("floats.bin", "wb") as fp:
    floats.tofile(fp)

floats2 = array("d")
with open("floats.bin", "rb") as fp:
    floats2.fromfile(fp, 10 ** 7)
print(floats2[-1])
print(floats2 == floats)

# 结果：
0.8220703930498271
0.8220703930498271
True

有人做过实验，用array.fromfile从一个二进制文件读出1000万个双精度浮点数只需要0.1秒（笔者电脑有点年代了，达不到这个速度），速度是从文本文件里读取的60倍，因为后者会使用内置的float方法把每一行文字转换成浮点数。另外，array.tofile写入二进制文件也比写入文本文件快7倍。另外，这1000万个数的bin文件只占8千万字节，如果是文本文件的话，需要181515739字节。

另一个快速序列化数字类型的方法是使用pickle模块，pickle.dump处理浮点数组的速度几乎和array.tofile一样快，而且pickle可以处理几乎所有的内置数字类型

memoryview是个内置类，它让用户在不复制内存的情况下操作同一个数组的不同切片。memoryview的概念受到了Numpy的启发。

内存视图其实是泛化和去数学化的Numpy数组。它让你在不需要复制内容的前提下，在数据结构之间共享内存。其中数据结构可以是任何形式，比如PIL图片、SQLite数据库和Numpy数组等待。这个功能在处理大型数据集合的时候非常重要。

memoryview.cast的概念跟数组模型类似，能用不同的方式读取同一块内存数据，而且内存字节不会随意移动。这有点类似于C语言的类型转换。memoryview.cast会把同一块内存里的内容打包成一个全新的memoryview对象返回。

下面这个例子精确地修改一个数组的某个字节：

import array
# 16位二进制整数
numbers = array.array("h", [-2, -1, 0, 1, 2])
memv = memoryview(numbers)
print(len(memv))
print(memv[0])
# 转换成8位的无符号整数
memv_oct = memv.cast("B")
print(memv_oct.tolist())
# 这个坐标刚好是第3个16位二进制数的高位字节
memv_oct[5] = 4
print(numbers)

# 结果：
5
-2
[254, 255, 255, 255, 0, 0, 1, 0, 2, 0]
array("h", [-2, -1, 1024, 1, 2])

拼接这NumPy和SciPy提供的高阶数组和矩阵操作，Python称为科学计算应用的主流语言。NumPy实现了多维同质数组（homogeneous array）和矩阵，这些数据结构不但能处理数字，还能存放其他由用户定义的记录。SciPy是基于NumPy的另一个库，他提供了很多跟科学计算有关的算法，专为线性代数、数值积分和统计学而设计。SciPy的高校和可靠性归功于背后的C和Fortran代码，而这些跟计算有关的部分都源自于Netlib。SciPy把基于C和Fortran的工业级数学计算功能用交互式且高度抽象的Python包装起来。

以下是一些NumPy二维数组的基本操作：

>>> import numpy
>>> a = numpy.arange(12)
>>> a
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11])

>>> type(a)

# 数组a的维度
>>> a.shape
(12,)
# 手动设置数组维度，3行4列
>>> a.shape = 3, 4
>>> a
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11]])
# 第2行
>>> a[2]
array([ 8,  9, 10, 11])
# 第2行第1列元素
>>> a[2, 1]
9
# 第1列元素
>>> a[:, 1]
array([1, 5, 9])
# 转置
>>> a.transpose()
array([[ 0,  4,  8],
       [ 1,  5,  9],
       [ 2,  6, 10],
       [ 3,  7, 11]])
# 全部数据乘2
>>> a *= 2
>>> a
array([[ 0,  2,  4,  6],
       [ 8, 10, 12, 14],
       [16, 18, 20, 22]])

NumPy也可读取、写入文件：

# 从文本文件中读取数据
floats = numpy.loadtxt("filename.txt")
# 把数组存入后缀为.npy的二进制文件，会自动加后缀名
numpy.save("filesave", floats)
# 从.npy文件中读取数据，这次load方法利用了一种叫做内存映射的机制，它让
# 我们在内存不足的时候仍可以对数组切片
floats2 = numpy.load("filesave.npy", "r+")

这两个库都异常强大，它们也是一些其他库的基础，比如Pandas和Blaze数据分析库。

利用.append和.pop方法，可以将列表（list）变成栈和队列。但删除列表的第一个元素或在第一个元素前插入元素之类的操作会很耗时，因为会移动数据。如果经常要在列表两端操作数据，推荐使用collections.deque类（双向队列）。它是一个线程安全、可快速从两端添加删除元素的数据类型。下面是它的操作示范：

# maxlen是个可选参数，表示队列最大长度，该属性一旦设定变不能修改
>>> dq = deque(range(10), maxlen=10)
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
# 队列旋转操作，接收参数n，当n＞0时，队列最右边n个元素移动到最左边
# 当n＜0时，队列最左边n个元素移动到最右边
>>> dq.rotate(3)
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)

>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
# 队列左边添加一个元素-1，由于队列长10，所以元素0被删除
>>> dq.appendleft(-1)
>>> dq
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
# 队列右边添加三个元素，挤掉了最前面的三个元素
>>> dq.extend([11, 22, 33])
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)
# 注意添加的顺序
>>> dq.extendleft([10, 20, 30, 40])
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

该数据结构还有许多其他操作，append和popleft是原子操作，可在多线程中安全地使用，不用担心资源锁的问题。

queue：提供了同步（线程安全）类Queue，LifoQueue和PriorityQueue，不同的线程可以利用这些数据类型来交换信息。这三个类在队列满的时候不会丢掉旧元素，而是被锁住，直到某线程移除了某个元素。这一特性让这些类很适合用来控制活跃线程的数量。

multiprocessing：实现了自己的Queue，和queue.Queue类似，设计给进程间通信用的。同时还有一个专门的multiprocessing.JoinableQueue类，该类让任务管理变得方便。

asyncio：从Python3.4新增的包，包含Queue，LifoQueue，PriorityQueue和JoinableQueue，这些类受queue和multiprocessing模块的影响，但是为异步编程里的任务管理提供了专门的便利。

heapq：和上述三个模块不同，它没有队列类，而是提供了heappush和heappop方法，让用户可以把可变序列当作堆队列或者优先队列来使用。

Python入门教材往往会强调列表可以容纳不同类型的元素，但实际上这样做并没有什么特别的好处。之所以用列表来存放东西，是期待在稍后使用它的时候，其中的元素能有一些共有的特性。Python3中，如果列表里的元素不能比较大小，则是不能对列表进行排序的。元组则恰恰相反，它经常用来存放不同类型的元素，这也符合它的本质，元组就是用作存放彼此之间没有关系的数据的记录。

list.sort，sorted，max和min函数的key参数是个很棒的设计，相比于其他语言中双参数比较函数，这里的参数key只需提供一个单参数函数来提取或计算一个值作为比较大小的标准。说它更高效，是因为在每个元素上，key函数只被调用一次。诚然，在排序的时候，Python总会比较两个键（key），但那一阶段的计算发生在C语言那一层，这样会比调用用户自定义的Python比较函数更快。key参数也能让你对一个混有数字字符和数值的列表进行排序，只需决定到底是将字符看做数值（数值排序），还是将数值看成字符（ASCII排序），即key到底是等于int还是等于str。

sorted和list.sort背后的排序算法是Timsort，它是一种自适应算法，会根据原始数据的顺序特点交替使用插入排序（数列基本有序时）和归并排序（没什么规律时），以达到最佳效率。这样的算法被证明是有效的，因为来自真实世界的数据通常是有一定的顺序特点的。Timsort在2002年的时候首次用在CPython中，自2009年起，Java和Android也开始使用这个算法。后来该算法被广为人知，是因为在Google对Sun的侵权案中，Oracle把Timsort中的一些相关代码作为了呈堂证供。Timsort的创始人是Tim Peters，一位高产的Python核心开发者，他也是“Python之禅”的作者之一。

迎大家关注我的微信公众号"代码港" & 个人网站 www.vpointer.net ~