Python专题之性能与优化
[TOC]
前言
Python慢是大家都知道的，他释放的人的生产力问题。
但是通过正确的使用Python，也是可以提高效率的。
数据结构
如果使用正确的数据结构，大多数计算机问题都能以一种优雅而简单的方式解决，而Python就恰恰提供了很多可供选择的数据结构。
通常，有一种诱惑是实现自定义的数据结构，但这必然是徒劳无功、注定失败的想法。因为Python总是能够提供更好的数据结构和代码，要学会使用它们。
例如，每个人都会用字典，但你看到过多少次这样的代码：
def get_fruits(basket,fruit):
try:
return basket[fruit]
except KeyError:
return set()
最好是使用dict结构已经提供的get方法。
def get_fruits(basket,fruit):
return basket.get(fruit,set())
使用基本的Python数据结构但不熟悉它提供的所有方法并不罕见。这也同样适用于集合的使用。例如：
def has_invalid_fields(fields):
for field in fields:
if field not in ['foo','bar']:
return True
return False
这可以不用循环实现：
def has_invalid_fields(fields):
return bool(set(fields) - set(['foo','bar']))
还有许多高级的数据结构可以极大地减少代码维护负担。看下面的代码：
def add_animal_in_family(species, animal, family):
if family not in species:
species[family] = set()
species[family].add(animal)
species = {}
add_animal_in_family(species,'cat','felidea')
事实上Python提供的collections.defaultdict结构中以更优雅地解决这个问题。
import collections
def add_animal_in_family(species, animal, family):
species[family].add(animal)
species = collections.defaultdict(set)
add_animal_in_family(species,'cat','felidea')
每次试图从字典中访问一个不存在的元素，defaultdict都会使用作为参数传入的这个函数去构造一个新值而不是抛出KeyError。在这个鸽子，set函数被用来在每次需要时构造一个新的集合。
此外,collections模块提供了一些新的数据结构用来解决一些特定问题，如OrderedDict或者Counter。
在Python中找到正确的数据结构是非常重要的，因为正确的选择会节省你的时间并减少代码维护量。
性能分析
Python提供了一些工具对程序进行性能分析。标准的工具之一就是cProfile,而且它很容易使用。如下所示。
$python -m cProfile manage.py
ncalls tottime percall cumtime percall filename:lineno(function)
455 0.002 0.000 0.002 0.000 <frozen importlib._bootstrap>:119(release)
408 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:159(__init__)
408 0.001 0.000 0.007 0.000 <frozen importlib._bootstrap>:163(__enter__)
408 0.001 0.000 0.003 0.000 <frozen importlib._bootstrap>:170(__exit__)
455 0.003 0.000 0.004 0.000 <frozen importlib._bootstrap>:176(_get_module_lock)
416 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:190(cb)
47 0.000 0.000 0.001 0.000 <frozen importlib._bootstrap>:195(_lock_unlock_module)
477/25 0.001 0.000 0.455 0.018 <frozen importlib._bootstrap>:214(_call_with_frames_removed)
...
运行结果的列表显示了每个函数的调用次数，以及执行所花费的时间。可以使用-s选项按其他字段进行排序，例如，-s time可以按内部时间进行排序。
cProfile生成的性能分析数据很容易转换成一个可以被KCacheGrind读取的调用树。cProfile模块有一个-o选项允许保存性能分析数据，并且pyprof2calltree可以进行格式转换。
使用示例：
$ python -m cProfile -o myscript.cprof myscript.py
$ pyprof2calltree -k -i myscript.cprof
dis模块
用dis模块可以看到一些隐藏的东西。dis模块是Python字节码的反编译器，用起来也很简单。
>>> def x():
... return 42
...
>>> import dis
>>> dis.dis(x)
2 0 LOAD_CONST 1 (42)
3 RETURN_VALUE
>>>
dis.dis函数会反编译作为参数传入的函数，并打印出这个函数运行的字节码指令的清单。为了能适当地优化代码，这对于理解程序的每行代码非常有用。
下面的代码定义了两个函数，功能相同，都是拼接三个字母。
>>> abc = ('a', 'b', 'c')
>>> def concat_a_1():
... for letter in abc:
... abc[0] + letter
...
>>> def concat_a_2():
... a = abc[0]
... for letter in abc:
... a + letter
...
>>>
两者看上去作用一样，但如果反汇编它们的话，可以看到生成的字节码有点儿不同。
>>> dis.dis(concat_a_1)
2 0 SETUP_LOOP 26 (to 29)
3 LOAD_GLOBAL 0 (abc)
6 GET_ITER
>> 7 FOR_ITER 18 (to 28)
10 STORE_FAST 0 (letter)
3 13 LOAD_GLOBAL 0 (abc)
16 LOAD_CONST 1 (0)
19 BINARY_SUBSCR
20 LOAD_FAST 0 (letter)
23 BINARY_ADD
24 POP_TOP
25 JUMP_ABSOLUTE 7
>> 28 POP_BLOCK
>> 29 LOAD_CONST 0 (None)
32 RETURN_VALUE
>>> dis.dis(concat_a_2)
2 0 LOAD_GLOBAL 0 (abc)
3 LOAD_CONST 1 (0)
6 BINARY_SUBSCR
7 STORE_FAST 0 (a)
3 10 SETUP_LOOP 22 (to 35)
13 LOAD_GLOBAL 0 (abc)
16 GET_ITER
>> 17 FOR_ITER 14 (to 34)
20 STORE_FAST 1 (letter)
4 23 LOAD_FAST 0 (a)
26 LOAD_FAST 1 (letter)
29 BINARY_ADD
30 POP_TOP
31 JUMP_ABSOLUTE 17
>> 34 POP_BLOCK
>> 35 LOAD_CONST 0 (None)
38 RETURN_VALUE
>>>
如你所见，在函数的第二个版本中运行循环之前我们将abc[0]保存在了一个临时变量中。这使得循环内部执行的字节码稍微短一点，因为不需要每次迭代都去查找abc[0]。通过timeit测量,第二个版本的函数比第一个要快10%，少花了不到一微妙。
另一个我在评审代码时遇到的错误习惯是无理由地定义嵌套函数。这实际是有开销的，因为函数会无理由地被重复定义。
>>> import dis
>>> def x():
... return 42
...
>>> dis.dis(x)
2 0 LOAD_CONST 1 (42)
3 RETURN_VALUE
>>> def x():
... def y():
... return 42
... return y()
...
>>> dis.dis(x)
2 0 LOAD_CONST 1 (<code object y at 0x10dff9b70, file "<stdin>", line 2>)
3 LOAD_CONST 2 ('x.<locals>.y')
6 MAKE_FUNCTION 0
9 STORE_FAST 0 (y)
4 12 LOAD_FAST 0 (y)
15 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
18 RETURN_VALUE
>>>
可以看到函数被不必要地复杂化了，调用MAKE_FUNCTION、STORE_FAST、LOAD_FAST和CALL_FUNCTION,而不是直接调用LOAD_CONST,这无端造成了更多的操作码，而函数调用在Python中本身就是低效的。
唯一需要在函数内定义函数的场景是在构建函数闭包的时候，它可以完美地匹配Python的操作码中的一个用例。反汇编一个闭包的示例如下：
>>> def x():
... a = 42
... def y():
... return a
... return y()
...
>>> dis.dis(x)
2 0 LOAD_CONST 1 (42)
3 STORE_DEREF 0 (a)
3 6 LOAD_CLOSURE 0 (a)
9 BUILD_TUPLE 1
12 LOAD_CONST 2 (<code object y at 0x10e09ef60, file "<stdin>", line 3>)
15 LOAD_CONST 3 ('x.<locals>.y')
18 MAKE_CLOSURE 0
21 STORE_FAST 0 (y)
5 24 LOAD_FAST 0 (y)
27 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
30 RETURN_VALUE
>>>
有序列表和二分查找
当处理大的列表时，有序列表比非有序列表有一定的优势。例如，有序列表的元素获取时间为O(log n)。
首先,Python提供了一个bisect模块，其包含了二分查找算法。非常容易使用，如下所示：
>>> farm = sorted(['haystack', 'needle', 'cow', 'pig'])
>>> import bisect
>>> bisect.bisect(farm, 'needle')
3
>>> bisect.bisect_left(farm, 'needle')
2
>>> bisect.bisect(farm,'chicken')
0
>>> bisect.bisect_left(farm,'chicken')
0
>>> bisect.bisect(farm,'eggs')
1
>>> bisect.bisect_left(farm,'eggs')
1
bisect函数能够在保证列表有序的情况下给出要插入的新元素的索引位置。
如果要立即插入， 可以使用bisect模块提供的insort_left和insort_right函数。如下所示：
>>> farm
['cow', 'haystack', 'needle', 'pig']
>>> bisect.insort(farm,'eggs')
>>> farm
['cow', 'eggs', 'haystack', 'needle', 'pig']
>>> bisect.insort(farm,'turkey')
>>> farm
['cow', 'eggs', 'haystack', 'needle', 'pig', 'turkey']
>>>
可以使用这些函数创建一个一直有序的列表，如下所示：
import bisect
class SortedList(list):
def __init__(self, iterable):
super(SortedList, self).__init__(sorted(iterable))
def insort(self, iterm):
bisect.insort(self, iterm)
def index(self, value, start=None, stop=None):
place = bisect.bisect_left(self[start:stop], value)
if start:
place += start
end = stop or len(self)
if place < end and self[place] == value:
return place
raise ValueError("%s is not in list" % value)
此外还有许多Python库实现了上面代码的各种不同版本，以及更多的数据类型，如二叉树和红黑树。Python包blist和bintree就包含了用于这些目的的代码，不要开发和调试自己的版本。
namedtuple和slots
有时创建只拥有一些固定属性的简单对象是非常有用的。一个简单的实现可能需要下面这几行代码：
class Point(object):
def __init__(self, x, y):
self.x = x
self.y = y
这肯定可以满足需求。但是，这种方法的缺点就是它创建了一个继承自object的类。在使用这个Point类时，需要实例化对象。
Python中这类对象的特性之一就是会存储所有的属性在一个字典内，这个字典本身被存在__dict__属性中：
>>> p = Point(1, 2)
>>> p.__dict__
{'x': 1, 'y': 2}
>>> p.z = 42
>>> p.z
42
>>> p.__dict__
{'x': 1, 'z': 42, 'y': 2}
>>>
好处是可以给一个对象添加任意多的属性。缺点就是通过字典来存储这些属性内存方面的开销很大，要存储对象、键、值索引等。创建慢，操作也慢，并且伴随着高内存开销。
看看下面这个简单的类。
class Foobar(object):
def __init__(self, x):
self.x = x
我们可以通过Python包memory_profiler来检测一下内存使用情况：
我在mac上用py2.7和py3.5测试都失败。在centos上py3.5测试也失败。
如下
python -m memory_profiler object.py
/home/work/pythonlearn/venv/lib/python3.5/site-packages/memory_profiler.py:1035: UserWarning: psutil can not be used, posix used instead
new_backend, _backend))
Python中的类可以定义一个__slots__属性,用来指定该类的实例可用的属性。其作用在于可以将对象属性存储在一个list对象中，从而避免分配整个字典对象。如果浏览一下CPython的源代码并且看看objects/typeobject.c文件，就很容易理解这里Python做了什么。下面给出了相关处理函数的部分代码：
static PyObject *
type_new(PyTypeObject *metatype, PyObject *args, PyObject *kwds)
{
[...]
/* Check for a __slots__ sequence variable in dict, and count it */
slots = _PyDict_GetItemId(dict, &PyId___slots__);
nslots = 0;
if (slots == NULL) {
if (may_add_dict)
add_dict++;
if (may_add_weak)
add_weak++;
}
else {
/* Have slots */
/* Make it into a tuple */
if (PyUnicode_Check(slots))
slots = PyTuple_Pack(1, slots);
else
slots = PySequence_Tuple(slots);
/* Are slots allowed? */
nslots = PyTuple_GET_SIZE(slots);
if (nslots > 0 && base->tp_itemsize != 0) {
PyErr_Format(PyExc_TypeError,
"nonempty __slots__"
"not supported for subtype of '%s'",
base->tp_name);
goto error;
}
/* Copy slots into a list, mangle names and sort them.
Sorted names are nedded for __class__ assignment.
Conert them back to tuple at the end.a
*/
newslots = PyList_New(nslots - add_dict - add_weak);
if (newslots == NULL)
goto error;
if (PyList_Sort(newslots) == -1) {
Py_DECREF(newslots);
goto error;
}
slots = PyList_AsTuple(newslots);
Py_DECREF(newslots);
if (slots == NULL)
goto error;
}
/* Allocate the type object */
type = (PyTypeObject *)metatype->tp_alloc(metatype, nslots);
[...]
/* Keep name and slots alive in the extended type object */
et = (PyHeapTypeObject *)type;
Py_INCREF(name);
et->ht_name = name;
et->ht_slots = slots;
slots = NULL;
[...]
return (PyObject *)type;
}
正如你所看到的，Python将__slots__的内容转化为一个元组，构造一个list并排序，然后再转换回元组并存储在类中。这样Python就可以快速地抽取值，而无需分配和使用整个字典。
声明这样一个类并不难。
class Foobar(object):
__slots__ ='x'
def __init__(self, x):
self.x = x
再看看内存情况：
看似通过使用Python类的__slots__属性可以将内存使用率提升一倍，这意味着在创建大量简单对象时使用__slots__属性是有效且高效的选择。但这项技术不应该被滥用于静态类型或其他类似场合，那不是Python程序的精神所在。
由于属性列表的固定性，因此不难想像类中列出的属性总是有一个值，且类中的字段总是按某种方式排过序的。
这也正是collection模块中namedtuple类的本质。它允许动态创建一个继承自tuple的类，因而有着共有的特征，如不可改变，条目数固定。namedtuple所提供的能力在于可以通过命名属性获取元组的元素而不是通过索引。如下所示：
>>> import collections
>>> Foobar = collections.namedtuple('Foobar',['x'])
>>> Foobar = collections.namedtuple('Foobar',['x','y'])
>>> Foobar(42,43)
Foobar(x=42, y=43)
>>> Foobar(42,43).x
42
>>> Foobar(42,43).x = 44
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: can't set attribute
>>> Foobar(42,43).z = 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'Foobar' object has no attribute 'z'
>>> list(Foobar(42,43))
[42, 43]
>>>
因为这样的类是继承自tuple的，因此可以很容易将其转换为list。但不能添加或修改这个类的对象的任何属性，因为它继承自tuple同时也因为__slots__的值被设置成了一个空元组以避免创建__dict__。
namedtuple还提供了一些额外的方法，尽管以下划线作为前缀，但实际上是可以公开访问的。_asdict可以将namedtuple转换为字典实例,_make可以转换已有的iterable对象为namedtuple,_replace替换某些字段后返回一个该对象的新实例。
memoization
memoization是指通过缓存函数返回结果来加速函数调用的一种技术。仅当函数是纯函数时结果才可以被缓存，也就是说函数不能有任何副作用或输出，也不能依赖任何全局状态。
正弦函数sin就是一个可以用来memoize化的函数
>>> import math
>>> _SIN_MEMOIZED_VALUES = {}
>>> def memoized_sin(x):
... if x not in _SIN_MEMOIZED_VALUES:
... _SIN_MEMOIZED_VALUES[x] = math.sin(x)
... return _SIN_MEMOIZED_VALUES[x]
...
>>> memoized_sin(1)
0.8414709848078965
>>> _SIN_MEMOIZED_VALUES
{1: 0.8414709848078965}
>>> memoized_sin(2)
0.9092974268256817
>>> memoized_sin(2)
0.9092974268256817
>>> _SIN_MEMOIZED_VALUES
{1: 0.8414709848078965, 2: 0.9092974268256817}
>>>
这就是一个简单的内存缓存。自己实现也简单，不过PyPI已经包含了一些通过装饰器实现的memoization,从简单场景到最复杂且最完备的情况都有覆盖。
从Python3.3开始,functools模块提供了一个LRU(Least-Recently-Used)缓存装饰器。它提供了同此处描述的memoization完全一样的功能，其优势在于限定了缓存的条目数，当缓存的条目数达到最大时会移除最近最少使用的条目。
该模块还提供了对缓存命中、缺失等的统计。在我看来，对于缓存来说它们都是必备的实现。如果不能对缓存的使用和效用进行衡量，那么使用memoization是毫无意义的。
上述例子改用functools.lru_cache改写的示例如下：
>>> import functools
>>> import math
>>> @functools.lru_cache(maxsize=2)
... def memoized_sin(x):
... return math.sin(x)
...
>>> memoized_sin(2)
0.9092974268256817
>>> memoized_sin.cache_info()
CacheInfo(hits=0, misses=1, maxsize=2, currsize=1)
>>> memoized_sin(2)
0.9092974268256817
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=1, maxsize=2, currsize=1)
>>> memoized_sin(3)
0.1411200080598672
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=2, maxsize=2, currsize=2)
>>> memoized_sin(4)
-0.7568024953079282
>>> memoized_sin.cache_info()
CacheInfo(hits=1, misses=3, maxsize=2, currsize=2)
>>> memoized_sin.cache_clear()
>>> memoized_sin.cache_info()
CacheInfo(hits=0, misses=0, maxsize=2, currsize=0)
>>>
PyPy
PyPy是符合标准的Python语言的一个高效实现。
除了技术上的挑战，PyPy吸引人的地方在于目前它是CPython的更快的替代品。PyPy包含内置的JIT(Just-In-Time)编译器。简单来说，就是通过利用解释的灵活性对编译后的代码的速度进行整合从而运行得更快。
到底有多快呢？看情况，但对于纯算法代码会更快一点。对于普通的代码，大多数情况下PyPy声称可以达到3倍的速度。尽管如此，也不要期望太高，PyPy同样有一些CPython的局限性，如可恶的GIL(Global Interpreter Lock, 全局解释器锁)。
#通过缓冲区协议实现零复制
通常程序都需要处理大量的大型字节格式的数组格式的数据。一旦进行复制、分片和修改等操作，以字符串的方式处理如此大量的数据是非常低效的。
分片操作符会复制全部的内容，从而占用过多的内存。
在Python中可以使用实现了缓冲区协议的对象。PEP 3118定义了缓冲区协议，其中解释了用于为不同数据类型(如字符串类型)提供该协议的C API。
对于实现了该协议的对象，可以使用其memoryview类的构建函数去构造一个新的memoryview对象，它会引用原始的对象内存。
如下：
>>> s = b"abcdefgh"
>>> view = memoryview(s)
>>> view[1]
98
>>> limited = view[1:3]
>>> bytes(view[1:3])
b'bc'
>>>
在这个例子中，会利用memoryview对象的切片运算符本身返回一个memoryview对象的事实。这意味着它不会复制任何数据，而只是引用了原始数据的一个特定分片，如图所示：
当处理socket时这类技巧尤其有用。如你所知，当数据通过socket发送时，它不会在一次调用中发送所有数据。下面是一个简单的实现：
import socket发送时
s = socket.socket(...)
s.connect(...)
data = b"a" * (1024 * 100000)
while data:
sent = s.send(data)
data = data[sent:]
显然通过这种机制，需要不断地复制数据，直到socket将所有数据发送完毕。而使用memoryview可以实现同样的功能而无需复制数据，也就是零复制。
import socket发送时
s = socket.socket(...)
s.connect(...)
data = b"a" * (1024 * 100000)
mv = memoryview(data)
while mv:
sent = s.send(data)
mv = mv[sent:]
这段程序不会复制任何内容，不会使用额外的内存，也就是说只是像开始时那样要给变量分配100MB内存。
前面已经看到了将memoryview对象用于高效地写数据的场景，同样的方法也可以用在读数据时。