我的使用情况是,在某些在线评测平台上,库依赖性受到限制,但在进行动态规划时需要二维数组(也很难矢量化)。我的Python代码经常会超时。
以下是需要注意的事项:
- 尽管Python列表是指针数组,但简单对象非常快。
- 使用像numpy这样的紧凑结构可能在创建对象时更快,但访问元素将产生额外的开销,不像简单的Python对象。
- 除非使用一些JIT工具,如Numba。
使用玩具DP示例进行测试代码:
import timeit
size = 1000
range_init_0 = "size={}".format(size)
range_init_1 = "a = [[0 for i in range(size)] for j in range(size)]"
multi_init_0 = "size={}".format(size)
multi_init_1 = "a = [[0]*size for _ in range(size)]"
numpy_init_0 = "from numpy import zeros; size={}".format(size)
numpy_init_1 = "a = zeros((size, size), dtype=int)"
array_init_0 = "from array import array; size={}".format(size)
array_init_1 = "a = [array('d', [0])*size for j in range(size)]"
ctyps_init_0 = "from ctypes import c_int; size={}".format(size)
ctypes_init_1 = "a = (c_int * size * size)()"
dp = '''
MOD = int(1e9+7)
for i in range(size):
a[i][0] = 1
for j in range(size):
a[0][i] = 1
for i in range(1, size):
for j in range(1, size):
a[i][j] = (a[i][j] + a[i-1][j] + a[i][j-1]) % MOD
'''
def test(name, init_0, init_1, dp, n=10):
t = timeit.timeit(init_1, setup=init_0, number=n)
print("{} initial time:\t{:.8f}".format(name, t))
t = timeit.timeit(dp, setup=init_0 + '\n' + init_1, number=n)
print("{} calculate time:\t{:.8f}".format(name, t))
test("range", range_init_0, range_init_1, dp)
test("multi", multi_init_0, multi_init_1, dp)
test("numpy", numpy_init_0, numpy_init_1, dp)
test("array", array_init_0, array_init_1, dp)
test("ctypes", ctyps_init_0, ctypes_init_1, dp)
print('------')
numba_init_0 = '''
import numpy as np
size = {}
a = np.zeros((size, size), dtype=np.int32)
'''.format(size)
numba_init_1 = '''
import numba
def dp1(a):
size = len(a)
MOD = int(1e9+7)
for i in range(size):
a[i][0] = 1
for j in range(size):
a[0][i] = 1
for i in range(1, size):
for j in range(1, size):
a[i][j] = (a[i][j] + a[i-1][j] + a[i][j-1]) % MOD
dp_jit = numba.jit('void(i4[:,:])')(dp1)
'''
dp = "dp_jit(a)"
test("numba", numba_init_0, numba_init_1, dp)
结果:
range initial time: 0.56781153
range calculate time: 5.08359793
multi initial time: 0.03682878
multi calculate time: 5.14657282
numpy initial time: 0.00883761
numpy calculate time: 12.15619322
array initial time: 0.02656035
array calculate time: 5.27542352
ctypes initial time: 0.00523795
ctypes calculate time: 7.88469346
------
numba initial time: 2.98394509
numba calculate time: 0.05321887
(这里的Numba初始化时间不包括numpy初始化)
可以看到,在计算时,无论是numpy还是ctypes都比本地列表慢。
Numba JIT需要一些时间,但计算时间显着缩短。
(在在线评测平台上不要使用Python进行二维动态规划!)