Python性能优化-优化每一个细节

摘要: 《Python性能分析与优化》笔记，关于 Python 性能优化的常见基本手法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

写在前面

这是 Python 性能分析与优化系列的第 7 篇文章，主要参考 Python性能分析与优化 这本书。

往期回顾

第一期: Python性能分析基础
第二期: Python性能分析器 — cProfile
第三期: 使用cProfile进行性能分析与优化实践
第四期: Python性能分析器 — line_profiler
第五期: line_profiler性能分析实践 — 优化倒排索引
第六期: Python性能分析-可视化

运行性能分析程序只能发现问题,不能解决问题。在在前几期中中, 我们看过了一些示例,也做过了一些优化,但是都没有进行详细的解释。

本文将详细介绍优化的过程。从基础知识和Python语言自身的特点去分析，没有辅助工具,只有Python语言和正确使用Python的方法。

主要内容如下:

• 函数返回值缓存/函数查询表
• 默认参数的用法
• 列表综合表达式
• 生成器
• ctypes
• 字符串连接
• 其他Python优化技巧

---

1. 函数返回值缓存和函数查询表

函数返回值缓存

优化一段代码最常用的办法是函数返回值缓存(memoization)/函数查询表(lookup table)，先把函数、输入参数和返回值全部都保存起来,在函数下次被调用时直接使用存储的结果。

这种优化方法的典型使用情形是在处理【固定参数的函数被重复调用】时。这样做可以确保每次函数被调用时,直接返回缓存结果。如果函数被调用很多次,但是参数是随机变化的,那么我们存储函数就没什么效果了。

函数返回值缓存例子

下面的代码对比固定参数不加缓存、固定参数加缓存，随机参数不加缓存，随机参数加缓存四中情况下的耗时。

代码本身没有意义，就是重复跑一个数学公式记录时间。

由于第一个参数是列表，不能作为 Memoized 类 results 字典的键，因此要用下面的代码处理。

key = ''.join(map(str, args[0]))

import math
import time
import random

class Memoized:
    def __init__(self, fn):
        self.fn = fn
        self.results = {}


    def __call__(self, *args):
        key = ''.join(map(str, args[0]))
        try:
            return self.results[key]
        except KeyError:
            self.results[key] = self.fn(*args)
        return self.results[key]


@Memoized
def twoParamsMemoized(values, period):
    totalSum = 0
    for x in range(0, 100):
        for v in values:
        totalSum = math.pow((math.sqrt(v) * period), 4) + totalSum
    return totalSum



def twoParams(values, period):
    totalSum = 0
    for x in range(0, 100):
        for v in values:
            totalSum = math.pow((math.sqrt(v) * period), 4) + totalSum
    return totalSum



def performTest():
    valuesList = []
    for i in range(0, 10):
        valuesList.append(random.sample(range(1, 101), 10))

    start_time = time.clock()
    for x in range(0, 10):
        for values in valuesList:
            twoParamsMemoized(values, random.random())
    end_time = time.clock() - start_time
    print("Fixed params, memoized: {}".format(end_time))

    start_time = time.clock()
    for x in range(0, 10):
        for values in valuesList:
            twoParams(values, random.random())
    end_time = time.clock() - start_time
    print("Fixed params, without memoizing: {}".format(end_time))


    start_time = time.clock()
    for x in range(0, 10):
        for values in valuesList:
            twoParamsMemoized(random.sample(range(1,2000), 10), random.random())
    end_time = time.clock() - start_time
    print("Random params, memoized: {}".format(end_time))

    start_time = time.clock()
    for x in range(0, 10):
        for values in valuesList:
            twoParams(random.sample(range(1,2000), 10), random.random())
    end_time = time.clock() - start_time
    print("Random params, without memoizing: {}".format((end_time)))


if __name__ == "__main__":
    performTest()

Fixed params, memoized: 0.0023110000000000006
Fixed params, without memoizing: 0.022036
Random params, memoized: 0.022730999999999994
Random params, without memoizing: 0.023069000000000006

函数查询表

返回值缓存另一种版本是在初始化将阶段直接计算所有的值，然后调用时直接查表。这样做有几个条件

• 输入值必须是有限的,否则无法预先算出所有值;
• 查询表带了所有值,必须满足内存限制;
• 和前面提到的一样,输入值至少要使用一次,这样优化才有意义,也值得我们多付出一些努力

构建查询表可以用不同的数据结构，需要看问题的类型。

1. 列表/链表
2. 字典
3. 平衡树

最常用的是字典，注意是只要每次都能够生成不重复的键,这个算法就是有效的。但是,随着字典规模增大,哈希碰撞频繁,性能会下降。

函数查询表的例子 — 三角函数

按照计算时间来看,三角函数这类函数运行得非常慢。在重复使用时,这些函数会对程序性能造成沉重负担。

由于输入参数有无穷可能,无法全都预先计算。这样就不得不牺牲计算精度,例如仅仅预先计算离散的整数值输入。

但这种方法在某些既要求高性能又需要精度的环境中可能不太适用。对此还有折中的做法：在预先计算的结果之间进行插值计算。这样做的话性能无法同直接用查询表时相比,但是比每次直接调用三角函数计算结果的性能要好很多。

初始代码

import math
import time
from collections import defaultdict

trig_lookup_table = defaultdict(lambda: 0)

def complexTrigFunction(x):
    return math.sin(x) * math.cos(x) ** 2

for x in range(-1000, 1000):
    trig_lookup_table[x] = complexTrigFunction(x)

def lookUpTrig(x):
    return trig_lookup_table[int(x)]

trig_results = []
lookup_results = []
xs = [x / 1000 for x in range(-10000, 10000, 1)]

init_time = time.clock()
for x in xs:
    trig_results.append(complexTrigFunction(x))
print("Trig results: {}".format((time.clock() - init_time)))

init_time = time.clock()
for x in xs:
    lookup_results.append(lookUpTrig(x))
print("Lookup results: {}".format((time.clock() - init_time)))

import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.plot(xs, trig_results)
ax.plot(xs, lookup_results)

plt.savefig("fig.png")

从图上可以看到，简单查询表及其不精确，时间上稍有补偿，用三角函数计算是 0.0063，而查表是 0.0044。

增加插值计算

我们加一个插值计算(范围限制在-PI到PI之间)。

import math
import time
from collections import defaultdict

trig_lookup_table = defaultdict(lambda: 0)

def complexTrigFunction(x):
    return math.sin(x) * math.cos(x) ** 2

T = math.pi * 2
for x in range(0, 2000):
    trig_lookup_table[x] = complexTrigFunction(math.pi * x / 1000)

def lookUpTrig(x):
    return trig_lookup_table[int(x)]

trig_results = []
lookup_results = []
xs = [x / 1000 for x in range(-10000, 10000, 1)]

init_time = time.clock()
for x in xs:
    trig_results.append(complexTrigFunction(x))
print("Trig results: {}".format((time.clock() - init_time)))

factor = 1000 / math.pi
init_time = time.clock()
for x in xs:
    x = (x % T) * factor # 插值的过程
    lookup_results.append(lookUpTrig(x))
print("Lookup results: {}".format((time.clock() - init_time)))

import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.plot(xs, trig_results)
ax.plot(xs, lookup_results)

plt.savefig("fig.png")

实测插值+查表仅仅与三角函数计算基本一样，都是 0.006 左右。说明插值部分写的不太好。

---

2. 使用默认参数

默认参数(default argument)可以在函数创建时就确定输入值,而不用在运行阶段才确定输入。

这种方法只能用于在运行过程中参数不发生变化的函数和对象。

import time
import math
from functools import reduce

def degree_sin(deg):
    return math.sin(deg * math.pi / 180.0) * math.cos(deg * math.pi / 180.0)

def degree_sin_opt(deg, factor=math.pi/180.0, sin=math.sin, cos = math.cos):
    return sin(deg * factor) * cos(deg * factor)

normal_times = []
optimized_times = []

for y in range(100):
    init = time.clock()
    for x in range(1000):
        degree_sin(x)
    normal_times.append(time.clock() - init)

    init = time.clock()
    for x in range(1000):
        degree_sin_opt(x)
    optimized_times.append(time.clock() - init)

print("Normal function: {}".format((reduce(lambda x, y: x + y, normal_times, 0) / 100)))
print("Optimized function: {}".format((reduce(lambda x, y: x + y, optimized_times, 0 ) / 100)))

耗时对比

Normal function: 0.034630160000000416
Optimized function: 0.023715989999999985

显然这不是一个十分出色的优化手段。但是,它为我们节省了几毫秒的运行时间,因此值得我们关注。

但是用这个办法的化必须写好文档，因为如果文档没写清楚,这种优化方法是有问题的。因为在运行过程中,函数预先计算的项目是不能改变的,所以函数的接口容易造成混乱。

---

3. 列表推导表达式与生成器

列表推导表达式

为了搞明白为什么列表推导表达式比for循环的性能更好,我们需要做一些代码分解工作,还得看一点儿字节码。

代码之所以可以分解,是因为Python虽然是一个解释型语言,但是代码最终还是会编译成字节码。

字节码需要经过处理才能被理解。因此,我们用dis模块把字节码转换成人能读懂的形式,然后分析它们执行的细节。

import dis
import timeit

programs = dict(
    loop="""
multiples_of_two = []
for x in range(100):
    if x % 2 == 0:
        multiples_of_two.append(x)
""",
    comprehension='multiples_of_two = [x for x in range(100) if x % 2 == 0]',
)

for name, text in programs.items():
    print("{}, {}".format(name, timeit.Timer(stmt=text).timeit()))
    code = compile(text, '<string>', 'exec')
    dis.disassemble(code)

代码输出结果包括两部分:

• 每段代码的运行时间
• 通过dis模块分解出的解释器指令集

输出结果如下

loop, 5.503727740004251
  2           0 BUILD_LIST               0
              2 STORE_NAME               0 (multiples_of_two)

  3           4 SETUP_LOOP              38 (to 44)
              6 LOAD_NAME                1 (range)
              8 LOAD_CONST               0 (100)
             10 CALL_FUNCTION            1
             12 GET_ITER
        >>   14 FOR_ITER                26 (to 42)
             16 STORE_NAME               2 (x)

  4          18 LOAD_NAME                2 (x)
             20 LOAD_CONST               1 (2)
             22 BINARY_MODULO
             24 LOAD_CONST               2 (0)
             26 COMPARE_OP               2 (==)
             28 POP_JUMP_IF_FALSE       14

  5          30 LOAD_NAME                0 (multiples_of_two)
             32 LOAD_ATTR                3 (append)
             34 LOAD_NAME                2 (x)
             36 CALL_FUNCTION            1
             38 POP_TOP
             40 JUMP_ABSOLUTE           14
        >>   42 POP_BLOCK
        >>   44 LOAD_CONST               3 (None)
             46 RETURN_VALUE
comprehension, 4.012385269001243
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x7fa81e72b780, file "<string>", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (range)
              8 LOAD_CONST               2 (100)
             10 CALL_FUNCTION            1
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 STORE_NAME               1 (multiples_of_two)
             18 LOAD_CONST               3 (None)
             20 RETURN_VALUE

首先,上图中的结果说明列表推导版的代码确实比for循环要快。现在,让我们仔细地逐条对比两种方式的指令集列表,以便更好地理解两者的差异。

主要的差异是数值被增加到列表中的方式不同：

• 在for循环里,数值是一个一个增加的,用到三个指令(LOAD_ATTR、LOAD_NAME和CALL_FUNCTION)。
• 列表推导只用了一个简单且已经经过优化的指令(LIST_APPEND)。

但是不能肆意将所有的for循环都改成列表推导。这是因为有时候未经优化的列表推导,可能比for循环消耗的时间更长。

生成器表达式

在处理大列表(例如10万以上)的时候,列表综合表达式可能就不好使了。这是因为列表综合需要直接产生每一个值。

可以用生成器表达式(generator expression),不需要直接返回列表,而是返回一个生成器对象,它的API与列表类似。每当请求列表元素时,生成器表达式就会动态地生成列表元素。

生成器对象与列表对象有两个重要的差异

• 生成器对象不支持随机接入(random access)
• 生成器对象只能遍历一次,而列表对象可以遍历任意次

下面统计列表综合表达式和生成器表达式创建不同长度列表的时间

---

4. ctypes

ctypes 库可以让直接进入 Python 的底层,借助 C 语言的力量进行开发。这个库只有 CPython 解释器里面才有,因为这个版本是C语言写的。其他版本,如PyPy和Jython,都不能接入这个库。

这个连接C语言的接口可以直接加载预编译代码, 并用C语言执行。可以接入 Windows 系统上的 kernel32.dll 和 msvcrt.dll 动态链接库,以及 Linux 系统上的 libc.so.6 库。

加载自定义ctypes

我们可以把关键代码写成C语言,编译成一个库,然后导入Python当作模块使用。

例子1: 从1千万(1e7)个整数的列表中找出所有素数

朴素算法: 枚举 1 ~ 1e7 的每个数字，判断其是否为素数。判断过程就是简单的枚举 1~sqrt(x)，判断是否为 x 的因数即可。

朴素算法的时间复杂度 $O(N\sqrt{N})$，对于 1e7 的数据量级，可以在分钟级时间跑完。

import math
import time

N = int(1e7)

def check_prime(x):
    for i in range(2, math.floor(math.sqrt(x) + 1)):
        if x % i == 0:
            return 0
    return 1

def get_prime(N):
    return [x for x in range(2, int(N)) if check_prime(x) == 1]

init = time.clock()
numbers_py = get_prime(N)
print("{}".format((time.clock() - init)))

print("N: {}, len(numbers_py): {}".format(N, len(numbers_py)))

运行时间:
N = 1e6: 2.879s
N = 1e7: 75.541s

加 ctypes，用 c 实现返回整数的函数

写一个C语言版的check_prime函数,然后把它当作共享库(.so)导入Python代码中。

check_prime.c 的实现如下:

int check_prime(int x)
{
    for(int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return 0;
    }
    return 1;
}

产生库文件

gcc -shared -o check_prime.so -fPIC check_prime.c

调用方代码

import time
import ctypes
import math

N = int(1e7)

check_prime_types = ctypes.CDLL('./check_prime.so').check_prime

def get_prime_types(N):
    return [x for x in range(2, int(N)) if check_prime_types(x) == 1]

init = time.clock()
numbers_c = get_prime_types(N)
print("C version: {} seconds".format((time.clock() - init)))

print("N: {}, len(numbers_c): {}".format(N, len(numbers_c)))

运行时间:
N = 1e6: 0.367 seconds
N = 1e7: 6.129 seconds

加 ctypes，用 c++ 实现返回整数的函数

调用 C++ 代码时，需要在源文件中增加一个 extern “C” 的代码块，如下

#include <cmath>

int check_prime_(int a)
{
    for(int c = 2; c <= sqrt(a) ; c++)
    {
        if (a % c == 0)
            return 0;
    }
    return 1;
}

extern "C"
{
    int check_prime(int a)
    {
        return check_prime_(a);
    }
}

g++ -shared -o check_prime.so -fPIC check_prime.cpp

在extern “C”里的代码是暴露给的python的接口，可以使用CDLL进行调用，后面的过程与用 C 实现函数的做法一样，最终运行时间也与用 C 实现基本一样。

例子2: 从1亿(1e8)个整数的列表中找出所有素数

对于 1e8 的量级，再用 $O(N\sqrt{N})$ 的朴素算法就无法在分钟级的时间跑出来了。因此我们的需要用素数筛算法。

import math
import time

N = int(1e7)

def preprocess_prime(N):
    vec = [True] * N
    vec[0] = False
    vec[1] = False
    for x in range(2, int(N)):
        if not vec[x]:
            continue
        for i in range(x + x, N, x):
            vec[i] = False
    return vec

def get_prime(N):
    vec = preprocess_prime(N)
    return [x for x in range(2, int(N)) if vec[x]]

init = time.clock()
numbers_py = get_prime(N)
print("{}".format((time.clock() - init)))

print("N: {}, len(numbers_py): {}".format(N, len(numbers_py)))

运行时间:
N = 1e6: 0.189s
N = 1e7: 2.296s
N = 1e8: 26.186s

将返回数组的 preprocess_prime 用 C 实现

可以将数组指针传递给 dll/so，但无法返回数组指针，python 中没有对应的数组指针类型。

如果需要返回数组，需借助结构体。

#include <math.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct
{
    int x;
}Int;

Int* preprocess_prime(int N)
{
    Int *vec = (Int*)malloc(N * sizeof(Int));
    vec[0].x = 0;
    vec[1].x = 0;
    for(int i = 2; i < N; ++i)
        vec[i].x = 1;
    for(int i = 2; i < N; ++i)
    {
        if(!vec[i].x)
            continue;
        for(int j = i + i; j < N; j += i)
            vec[j].x = 0;
    }
    return vec;
}

结构体在ctypes中通过类进行定义。用于定义结构体的类需要继承自ctypes的Structure基类，而后通过定义类的_fields_属性来定义结构体的构成。

import math
import time
import ctypes

N = int(1e7)

preprocess_prime_types = ctypes.CDLL('./preprocess_prime.so').preprocess_prime

class StructPointer(ctypes.Structure):
    _fields_ = [("x", ctypes.c_int)]

preprocess_prime_types.restype = ctypes.POINTER(StructPointer)

def get_prime(N):
    vec = preprocess_prime_types(N)
    return [i for i in range(int(N)) if vec[i].x == 1]

init = time.clock()
numbers_c = get_prime(N)
print("{}".format((time.clock() - init)))

print("N: {}, len(numbers_c): {}".format(N, len(numbers_c)))

运行时间:
N = 1e6: 0.105s
N = 1e7: 1.182s
N = 1e8: 12.231s

性能对比

	1e6	1e7	1e8
朴素算法 + Python	2.879	75.541	-
朴素算法 + Python + C/C++	0.367	6.129	128.46
素数筛 + Python	0.189	2.296	26.186
素数筛 + Python + C/C++	0.105	1.182	12.231

加载一个系统库

如果需要的功能系统的库文件已经准备好了。则需要做的就是导入库文件,调用函数。

例子: 生成1000万个随机数

import time
import random

N = int(1e7)

init = time.clock()
randoms = [random.randrange(1, 100) for x in range(N)]
print("Pure python: {} seconds".format(time.clock() - init))

运行时间: 6.635s

import time
from ctypes import cdll

libc = cdll.LoadLibrary('libc.so.6') # linux systems
# libc = cdll.msvcrt # windows systems

N = int(1e7)

init = time.clock()
randoms = [(libc.rand() % 100) for x in range(N)]
print("C version: {} seconds".format(time.clock() - init))

运行时间: 2.008s

---

5. 字符串连接

Python的字符串和其他语言中的字符串不太一样。在Python里,字符串是不可变的(immutable。

这种设计带来的影响一定要知道，因为我们经常要在字符串变量中进行连接(concatenation)或替换等操作。

由于字符串是不可变的,每当我们要做任何改变字符串内容的操作时,其实都是创建了一个带有新内容的新字符串,我们的变量会指向新创建的字符串。

不可变的测试

下面的代码创建了两个内容相同的字符串变量。然后用id函数(在CPython里返回的是储存变量值的内存地址——指针)就可以比较两个变量。

a = "This is a string"
b = "This is a string"
print id(a) == id(b) # 打印 True
print id(a) == id("This is a string") # 打印 True
print id(b) == id("This is another String") # 打印 False

以上实验的结果显示了我们每次写相同的字符串(例如This is a string)时,Python底层是如何重用字符串的。

对一个变量赋值两次字符串的几种常见情况图示如下

不可变对象如果使用恰当，对性能有好处。例如：

• 可以作为字典的键
• 可以在不同的变量绑定之间进行共享(引用同一个字符串其实都在用同一块内存)

下面看一下基于字符串不可变的特性的性能优化的例子。

例子1: 用列表中的词串成新字符串

将列表中的字符串元素串成新字符串，join 的方式比 for 循环的方式内存和时间消耗都更小。

import time
import sys

option = sys.argv[1]

N = int(1e6)

words =  [str(x) for x in range(N)]

if option == '1':
    full_doc = ""
    init = time.clock()
    for w in words:
        full_doc += w
    print("Time using for-loop: {}".format(time.clock() - init))
else:
    init = time.clock()
    full_doc = "".join(words)
    print("Time using join: {}".format(time.clock() - init))

time -f "Memory: %M bytes" python string_concat.py 0
time -f "Memory: %M bytes" python string_concat.py 1

输出结果如下：join 版本消耗时间更短且占用内存更少。

Time using for-loop: 0.14099799999999998
Memory: 78484 bytes
Time using join: 0.015214000000000005
Memory: 78428 bytes

例子2: 连接不同类型的字符串

实现几个字符串的连接，常规写法如下，最终要创建几个字符串。

document = title + introduction + main_piece + conclusion

优化1： 用 format()

document = "{}{}{}{}".format(title, introduction, main_piece, conclusion)

优化2: C 语言的变量内插

document = "%s%s%s%s" % (title, introduction, main_piece, conclusion)

优化3: 用 locals 函数创建子字符串

document = "%(title)s%(introduction)s%(main_piece)s%(conclusion)s" % locals()

---

6. 其它优化技巧

还有一些专门针对Python的小tricks。可能不会显著提升性能，但可以揭示Python内部的运作方式。

命名元组 namedtuple

用常规 class 创建存储数据的简单对象时，实例中会有一个字典存储属性。

如果要创建大量简单对象，会浪费大量内存，此时可以用命名元组，这是 tuple 的子类。

import time
import collections

N = int(1e6)

class Obj(object):
    def __init__(self, i):
        self.i = i
        self.l = []

all = {}

init = time.clock()
for i in range(N):
    all[i] = Obj(i)
print("Regular Objects: {}".format((time.clock() - init)))

Obj = collections.namedtuple('Obj', 'i l')

all = {}
init = time.clock()
for i in range(N):
    all[i] = Obj(i, [])
print("Namedtuple Objects: {}".format((time.clock() - init)))

Regular Objects: 1.908448
Namedtuple Objects: 1.2511809999999999

内联函数

在时间密集的循环体中内联函数代码,不调用外部函数,可以更加高效。

但有一个很大的代价: 可能会损害代码的可读性和维护便利性。

import time

N = int(1e7)

def fn(x):
    return (x * x) / (x + 1)

init = time.clock()
x = 0.0
for i in range(N):
    x = fn(i)
print("Total time: {}".format(time.clock() - init))

init = time.clock()
x = 0.0
for i in range(N):
    x = (i * i) / (i + 1)
print("Total time (inline): {}".format(time.clock() - init))

Total time: 1.924492
Total time (inline): 1.3223509999999998

while 1 与 while True

1比True好:Python 中的while 1得到了优化,跳转一次就能完成,而while True并没有,因此需要跳转好几次才能完成

但是与内联函数的情况差不多，while 1 的写法会有理解成本和沟通成本。

多元赋值

a, b = "hellothere", 123 通常比单独赋值慢。但是变量交换的时候多元赋值更快，因为少了临时变量和赋值的过程。

---