Python 2D列表性能优化，不使用numpy

Question

我正在尝试在Python中创建一个二维列表。我找到了两种可能性。

def cArray(size):
    c = [[0. for i in range(size)] for j in range(size)]
    return c

def npArray(size):
    np = numpy.zeros((size,size))
    return np

现在这两个功能都可以给出正确的答案。问题在于性能方面。我使用timeit运行了这两个函数，以下是我的结果:

list size is 5000
number of times run is 5

cArray average time: 3.73241295815
npArray average time: 0.210782241821

显然，我希望避免第一种解决方案，特别是因为它将在大小高达100k时运行。但是，我也不想使用太多依赖项。有没有一种方法可以有效地创建一个二维数组，而不使用numpy？只要速度不慢到17倍以下，它并不需要完全跟得上。

- Phil

---

如果这让你感到震惊，那么尝试一下测量内存消耗吧。虽然可能不会比原来大17倍，但肯定也很糟糕。 - user395760

ctypes可以帮助，但肯定没有numpy那么强大。请参见https://dev59.com/EW855IYBdhLWcg3wynmC这个问题。 - unddoch

大小达到100k吗？那么我希望你的数组要么（1）不是正方形，尽管你的示例是正方形，要么（2）非常稀疏，否则跟踪那么多单元格会很麻烦。 - DSM

我真的认为，如果不知道对数据进行了什么处理，就无法真正回答这个问题。同时，还有一个只限于1D的import array，但是可以使用数组列表。将其放入[[0]*size for _ in xrange(size)]或array('d', [0])而不是[0]（它是类型感知的，因此占用更少的空间），可以消除一个循环。 - seberg

@DSM：不幸的是，DNA链远非稀疏。 - Phil

Answer 1

很明显，我希望避免第一种解决方案，特别是这将运行大小高达100k。然而，我也不想使用太多的依赖项。你必须选择其中更重要的内容。Numpy具有更好的性能，因为它不使用内置的Python类型，而是使用其自己的针对数值计算进行优化的类型。如果您的数据将是数字，并且您将拥有100k行/列，则使用numpy将看到巨大的性能提升。如果您想避免numpy的依赖关系，则必须接受性能降低。（显然，您始终可以编写自己的Python库或C扩展程序来优化您的特定用例，但这些将成为像其他任何依赖项一样的依赖项。）就个人而言，我建议您只需使用numpy。它使用如此广泛，以至于任何考虑使用处理100k多维数组的库的人可能已经安装了numpy。

- BrenBarn

Answer 2

我尝试了几个替代方法;

编辑: 原始的eArray存在问题，它创建了对同一列表的引用...

编辑2: 根据Sebastian的建议添加了array.array。

import time
import numpy as np
import array

t1 = 0

def starttimer():
    global t1
    t1 = time.clock()

def stoptimer(s):
    t2 = time.clock()
    print 'elapsed time for "{}": {:.3f} seconds'.format(s, t2-t1)

def cArray(size):
    c = [[0. for i in range(size)] for j in range(size)]
    return c

def dArray(size):
    d = [[0. for i in xrange(size)] for j in xrange(size)]
    return d

def eArray2(size):
    return [[0.]*size for j in xrange(size)]

def fArray(size):
    return np.zeros((size,size))

def gArray(size):
    return [array.array('d', [0])*size for j in xrange(size)]

sz = 5000

starttimer()
cArray(sz)
stoptimer('cArray')

starttimer()
dArray(sz)
stoptimer('dArray')

starttimer()
fArray(sz)
stoptimer('fArray')

starttimer()
gArray(sz)
stoptimer('gArray')

以下是结果（如果有人关心的话，运行在FreeBSD amd64上的cpython 2.7.3）：

> python tmp/test.py
elapsed time for "cArray": 2.312 seconds
elapsed time for "dArray": 1.945 seconds
elapsed time for "eArray2": 0.680 seconds
elapsed time for "fArray": 0.180 seconds
elapsed time for "gArray": 0.695 seconds
> python tmp/test.py
elapsed time for "cArray": 2.312 seconds
elapsed time for "dArray": 1.914 seconds
elapsed time for "eArray2": 0.680 seconds
elapsed time for "fArray": 0.180 seconds
elapsed time for "gArray": 0.695 seconds
> python tmp/test.py
elapsed time for "cArray": 2.328 seconds
elapsed time for "dArray": 1.906 seconds
elapsed time for "eArray2": 0.680 seconds
elapsed time for "fArray": 0.180 seconds
elapsed time for "gArray": 0.703 seconds

- Roland Smith

---

这个计时代码不起作用：t1 = time.clock()设置了一个局部变量。这就是为什么当e应该更快时，d和e具有相同的时间。如果你修复这个问题（例如在starttimer中使用global t1），你会得到更合理的结果。通常使用timeit模块更容易。另外，eArray并不是一个公平的比较，因为它实际上并没有创建5000^2个单元格。 - DSM

请记住它们不做同样的事情。例如，尝试更改您的eArray元素并查看结果。 - Joe Kington

@JoeKington 我已经修改了 eArray。我想我意识到了哪里出错了。 :-/ - Roland Smith

既然你在这里，也许可以添加import array，array.array('d'，[0])*size而不是[0]*size用于eArray。 - seberg

Answer 3

如果您想要进入底层编程，可以使用ctypes：

a = (ctypes.c_int * 5000 * 5000)()

但是NumPy可以在Python运行的大多数平台上使用。

- ecatmur

Answer 4

我的使用情况是，在某些在线评测平台上，库依赖性受到限制，但在进行动态规划时需要二维数组（也很难矢量化）。我的Python代码经常会超时。

以下是需要注意的事项：

1. 尽管Python列表是指针数组，但简单对象非常快。
2. 使用像numpy这样的紧凑结构可能在创建对象时更快，但访问元素将产生额外的开销，不像简单的Python对象。
3. 除非使用一些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进行二维动态规划！）

- ZornLemma