Python性能：嵌套列表上的迭代和操作

Question

问题大家好。我在寻找一些关于python性能的建议。关于我的问题的一些背景：

给出：

1. 一个(x,y)网格，每个节点的值(0...255)从0开始
2. 在一个指定的cd3{cd3}坐标范围内
3. 一个值Z，定义节点计数中的“邻居”

在输入坐标处增加节点的值和节点的邻居。忽略网格边以外的邻居。（无包装）

基本情况：一个大小为1024x1024节点的网格，具有400个输入坐标和75节点的范围Z。在

处理应该是O(x*y*Z*N)。我希望x、y和Z大致保持在基本情况下的值左右，但是输入坐标N的数量可能会增加到100000。我的目标是最小化处理时间。在

当前结果根据我的开始和下面的注释，我们有几个实现。在

在我的2.26 GHz Intel Core 2 Duo与Python 2.6.1上的运行速度：

  f1: 2.819s
  f2: 1.567s
  f3: 1.593s
   f: 1.579s
 f3b: 1.526s
  f4: 0.978s

f1是最初的朴素实现：三个嵌套的for循环。 f2is用一个列表理解替换了内部for循环。 f3基于Andrei在评论中的建议，并将外部for替换为map()f以下是克里斯的建议 f3b是克里斯斯扮演的f3f4是Alex的贡献。在

代码包含在下面供您阅读。在

问题如何进一步缩短处理时间？我更喜欢使用低于1.0s的测试参数。在

请，将建议保留为原生Python。我知道我可以使用第三方软件包，比如numpy，但我尽量避免任何第三方软件包。另外，我生成了随机输入坐标，并简化了节点值更新的定义，以使我们的讨论保持简单。具体细节要稍微改变一下，不在我的问题范围之内。在

多谢了！在

---

f1是最初的朴素实现：三个嵌套的for循环。 ^{pr2}$

f2is用列表理解替换了内部for循环。

def f2(x,y,n,z):
    rows = [[0]*x for i in xrange(y)]

    for i in range(n):
        inputX, inputY = (int(x*random.random()), int(y*random.random()))
        topleft = (inputX - z, inputY - z)
        for i in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
            l = max(0, topleft[1])
            r = min(topleft[1]+(z*2), y)
            rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]

更新：f3基于评论中Andrei的建议，并将外部for替换为map()。我在这方面的第一次尝试需要几个本地范围外的查找，特别是Guido的recommended against：局部变量查找比全局或内置的变量查找快得多除了对主数据结构本身的引用之外，我硬编码了所有这些查找，以将开销降到最低。在

rows = [[0]*x for i in xrange(y)]

def f3(x,y,n,z):
    inputs = [(int(x*random.random()), int(y*random.random())) for i in range(n)]
    rows = map(g, inputs)

def g(input):
    inputX, inputY = input
    topleft = (inputX - 75, inputY - 75)
    for i in xrange(max(0, topleft[0]), min(topleft[0]+(75*2), 1024)):
        l = max(0, topleft[1])
        r = min(topleft[1]+(75*2), 1024)
        rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]

UPDATE3:ChristopeD也指出了一些改进。在

def f(x,y,n,z):
    rows = [[0] * y for i in xrange(x)]
    rn = random.random
    for i in xrange(n):
        topleft = (int(x*rn()) - z, int(y*rn()) - z)
        l = max(0, topleft[1])
        r = min(topleft[1]+(z*2), y)
        for u in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
            rows[u][l:r] = [j+(j<255) for j in rows[u][l:r]]

UPDATE4:kriss对f3进行了一些改进，用新的三元运算符语法替换了min/max。在

def f3b(x,y,n,z):
    rn = random.random    
    rows = [g1(x, y, z) for x, y in [(int(x*rn()), int(y*rn())) for i in xrange(n)]]

def g1(x, y, z):
    l = y - z if y - z > 0 else 0
    r = y + z if y + z < 1024 else 1024
    for i in xrange(x - z if x - z > 0 else 0, x + z if x + z < 1024 else 1024 ):
        rows[i][l:r] = [j+(j<255) for j in rows[i][l:r]]

UPDATE5:Alex加入了他的实质性修订，添加了一个单独的map()操作，将值限制在255，并删除所有非本地范围查找。性能差异是非常重要的。在

def f4(x,y,n,z):
    rows = [[0]*y for i in range(x)]
    rr = random.randrange
    inc = (1).__add__
    sat = (0xff).__and__

    for i in range(n):
        inputX, inputY = rr(x), rr(y)
        b = max(0, inputX - z)
        t = min(inputX + z, x)
        l = max(0, inputY - z)
        r = min(inputY + z, y)
        for i in range(b, t):
            rows[i][l:r] = map(inc, rows[i][l:r])
    for i in range(x):
      rows[i] = map(sat, rows[i])

另外，由于我们似乎都在不断变化，下面是我用来比较速度的测试工具：（由ChristopheD改进）

def timing(f,x,y,z,n):
    fn = "%s(%d,%d,%d,%d)" % (f.__name__, x, y, z, n)
    ctx = "from __main__ import %s" % f.__name__ 
    results = timeit.Timer(fn, ctx).timeit(10)
    return "%4.4s: %.3f" % (f.__name__, results / 10.0)

if __name__ == "__main__":
    print timing(f, 1024, 1024, 400, 75)
    #add more here.

Answer 1

在我（slow ish；-）第一天Macbook Air，1.6GHz Core 2 Duo，MacOSX 10.5上的系统Python2.5上，在op.py中保存代码后，我看到了以下计时：

$ python -mtimeit -s'import op' 'op.f1()'
10 loops, best of 3: 5.58 sec per loop
$ python -mtimeit -s'import op' 'op.f2()'
10 loops, best of 3: 3.15 sec per loop

所以，我的机器比你的慢一点，比你的慢一点。在

我对这个任务最快的代码是：

^{pr2}$

乘以：

$ python -mtimeit -s'import op' 'op.f3()'
10 loops, best of 3: 3 sec per loop

所以，一个非常适度的加速，在你的机器上投射超过1.5秒-远高于你的目标1.0用于：-(. 在

使用简单的C代码扩展，exte.c…：

#include "Python.h"

static PyObject*
dopoint(PyObject* self, PyObject* args)
{
    int x, y, z, px, py;
    int b, t, l, r;
    int i, j;
    PyObject* rows;

    if(!PyArg_ParseTuple(args, "iiiiiO",
                         &x, &y, &z, &px, &py, &rows
        ))
        return 0;

    b = px - z;
    if (b < 0) b = 0;
    t = px + z;
    if (t > x) t = x;
    l = py - z;
    if (l < 0) l = 0;
    r = py + z;
    if (r > y) r = y;

    for(i = b; i < t; ++i) {
        PyObject* row = PyList_GetItem(rows, i);
        for(j = l; j < r; ++j) {
            PyObject* pyitem = PyList_GetItem(row, j);
            long item = PyInt_AsLong(pyitem);
            if (item < 255) {
                PyObject* newitem = PyInt_FromLong(item + 1);
                PyList_SetItem(row, j, newitem);
            }
        }
    }

    Py_RETURN_NONE;
}

static PyMethodDef exteMethods[] = {
    {"dopoint", dopoint, METH_VARARGS, "process a point"},
    {0}
};

void
initexte()
{
    Py_InitModule("exte", exteMethods);
}

（注意：我没有仔细检查它——我认为由于引用窃取和借用的正确交互作用，它不会泄漏内存，但是在投入生产之前应该非常仔细地检查代码；—），我们可以这样做

import exte
def f4(x=x,y=y,n=n,z=z):
    rows = [[0]*y for i in range(x)]
    rr = random.randrange

    for i in range(n):
        inputX, inputY = rr(x), rr(y)
        exte.dopoint(x, y, z, inputX, inputY, rows)

时间呢

$ python -mtimeit -s'import op' 'op.f4()'
10 loops, best of 3: 345 msec per loop

显示了8-9倍的加速度，这应该能让你达到你想要的水平。我看到一条评论说你不想要任何第三方扩展，但是，好吧，这个很小的扩展你可以完全自己做；-）。（（不确定什么授权条件适用于堆栈溢出时的代码，但如果需要，我很乐意在Apache2许可证或类似许可证下重新发布；-）。在

Answer 2

1。一个（较小的）加速肯定是你的rows的初始化。。。在

更换

rows = []
for i in range(x):
    rows.append([0 for i in xrange(y)])

与

^{pr2}$

2。您还可以通过将random.random移出循环来避免一些查找（节省一点）。在

3.编辑：更正后，您可以得出如下结论：

def f(x,y,n,z):
    rows = [[0] * y for i in xrange(x)]
    rn = random.random
    for i in xrange(n):
        topleft = (int(x*rn()) - z, int(y*rn()) - z)
        l = max(0, topleft[1])
        r = min(topleft[1]+(z*2), y)
        for u in xrange(max(0, topleft[0]), min(topleft[0]+(z*2), x)):
            rows[u][l:r] = [j+(j<255) for j in rows[u][l:r]]

编辑：timeit的一些新计时（10次跑步）--这似乎只提供了一些小的加速：

import timeit
print timeit.Timer("f1(1024,1024,400,75)", "from __main__ import f1").timeit(10)
print timeit.Timer("f2(1024,1024,400,75)", "from __main__ import f2").timeit(10)
print timeit.Timer("f(1024,1024,400,75)", "from __main__ import f3").timeit(10)

f1 21.1669280529
f2 12.9376120567
f  11.1249599457

Answer 3

在f3重写中，g可以简化。（也适用于f4）

在for循环中有以下代码。在

l = max(0, topleft[1])
r = min(topleft[1]+(75*2), 1024)

但是，在for循环中，这些值似乎永远不会更改。所以计算一次，在循环之外。在