使用 PyPy 代替 CPython

Python 的默认解释器是 CPython，它是用 C 语言实现的。由于 CPython 的执行效率比较低，因此在一些算法竞赛中，会使用 PyPy 代替 CPython。PyPy 是用 Python 语言实现的，它的执行效率比 CPython 平均高出 5 倍。由于某些 Python 早期发展历史原因，许多常用的第三方库都是针对 CPython 解释器进行设计和优化的，使用 PyPy 时可能会使程序变得更慢甚至无法运行，这也是 Python 仍把 CPython 作为默认解释器的原因。

但在日常的算法练习或是正规的算法竞赛中，往往都不会用到这样的第三方库，而 PyPy 的执行效率却比 CPython 高出很多，因此在这些场景中，使用 PyPy 代替 CPython 可以获得很大的加速效果。

使用 sys.stdin.readline 代替 input

Python 自带的输入函数 input 可以读取一行输入，并把它以字符串类型返回。但是 input 的执行效率比较低，因此在一些算法竞赛中，会使用 sys.stdin.readline 代替 input。sys.stdin.readline 也可以读取一行输入，并把它以字符串类型返回，与 input 的区别在于，sys.stdin.readline 会把末尾的换行符 \n 读取进来作为字符串的最后一个字符，而 input 则不会。

下图是使用相同的程序和解释器提交 Codeforce 1798 C. Candy Store，分别使用 input 和 sys.stdin.readline 读取输入的执行时间对比。

可以看出，当输入数据规模较大时，使用 sys.stdin.readline 代替 input 可以获得十分可观的性能提升。

使用局部变量代替全局变量

在 Python 中，全局变量与局部变量的实现方法不同，访问局部变量往往比访问全局变量要快。因此在一些算法竞赛中，会使用局部变量代替全局变量。

下面是许多 Python 初学者的简单写法，将整个程序在全局范围内运行：

1
2
3
4
5
6
7
8
9
10
11

import time
start = time.time()

n = 10000
for i in range(n):
    for j in range(n):
        temp = i**2 + j**2

end = time.time()
print(end - start)
# 44.94498109817505

下面是将程序放到 main 函数中运行的写法，这样可以减少使用全局变量：

1
2
3
4
5
6
7
8
9
10
11
12
13

import time
start = time.time()

def main():
    n = 10000
    for i in range(n):
        for j in range(n):
            temp = i**2 + j**2
main()

end = time.time()
print(end - start)
# 40.268553256988525

可以看到，当 n 为 10000 时，使用局部变量代替全局变量可以获得约 10% 的性能提升。

使用 from … import … 代替 import

Python 中的 import 语句会把模块中的所有内容都导入到当前作用域中，而 from ... import ... 语句只会导入指定的内容。除此之外，对模块的 . 操作也会消耗额外的时间，所以使用 from ... import ... 语句代替 import 语句可以获得一定的性能提升。

直接 import 模块：

1
2
3
4
5
6
7
8
9
10
11
12

import time
start = time.time()

import math
n = 10000
for i in range(n):
    for j in range(n):
        temp = math.sqrt(i) + math.sqrt(j)

end = time.time()
print(end - start)
# 20.36855411529541

使用 from ... import ... 语句代替 import 语句：

1
2
3
4
5
6
7
8
9
10
11
12

import time
start = time.time()

from math import sqrt
n = 10000
for i in range(n):
    for j in range(n):
        temp = sqrt(i) + sqrt(j)

end = time.time()
print(end - start)
# 17.78050708770752

使用 join 代替 + 拼接字符串

在 Python 中，+ 操作符可以用来拼接字符串，但是使用 + 来连接字符串时，会产生多个临时中间字符串，这会消耗额外的时间和空间。而 join 方法则是计算结果字符串所需的空间，然后一次性分配空间并进行连接。

使用 + 拼接字符串：

1
2
3
4
5
6
7
8
9
10
11
12

import time
start = time.time()

n = 10**7
c = ['0'] * n
s = ''
for i in c:
    s += i

end = time.time()
print(end - start)
# 2.7627029418945312

使用 join 拼接字符串：

1
2
3
4
5
6
7
8
9
10

import time
start = time.time()

n = 10**7
c = ['0'] * n
s = ''.join(c)

end = time.time()
print(end - start)
# 0.0600128173828125

可以看到，当需要拼接的字符串数量较多时，使用 join 拼接字符串可以获得很大的性能提升。