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

Question

问题大家好。我想请教一下关于Python性能方面的建议。以下是我问题的一些背景信息：

给定：

一个 (x,y) 的节点网格，每个节点的值在 (0...255) 之间，初始值为0
一组 N 个输入坐标，每个坐标在范围 (0...x, 0...y) 内
一个值 Z，定义了“邻域”的节点数量

在输入坐标的节点及其邻居节点上增加值。超出网格边界的邻居会被忽略。（不进行循环处理）

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

处理时间应该是 O(x*y*Z*N)。我希望 x、y 和 Z 的值大致保持在基本情况的范围内，但输入坐标 N 的数量可能会增加到10万。我的目标 是尽量缩短处理时间。

当前结果 从我开始到下面的评论中，我们有几个实现方案。

在我的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 循环。
f2 用列表推导式替换了内层的 for 循环。
f3 是基于Andrei在评论中的建议，用 map() 替换了外层的 for 循环。
f 是Chris在下面回答中的建议。
f3b 是kriss对 f3 的改进。
f4 是Alex的贡献。

代码在下面供你参考。

问题我该如何进一步减少处理时间？我希望测试参数的处理时间能低于1.0秒。

请保持建议使用原生Python。我知道可以使用第三方库，比如 numpy，但我想尽量避免使用任何第三方库。此外，我生成了随机的输入坐标，并简化了节点值更新的定义，以保持讨论的简单性。具体细节需要稍微调整，超出了我的问题范围。

非常感谢！

**`f1` 是最初的简单实现：三个嵌套的 `for` 循环。**

def f1(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)):
            for j in xrange(max(0, topleft[1]), min(topleft[1]+(z*2), y)):
                if rows[i][j] <= 255: rows[i][j] += 1

f2 用列表推导式替换了内层 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 在评论中的建议，用 map() 替换了外层 for 循环。我的第一次尝试需要进行几次超出局部范围的查找，这在Guido的建议中是被反对的：局部变量查找比全局或内置变量查找快得多。我将除了对主数据结构的引用以外的所有内容都硬编码，以减少这种开销。

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]]

更新3： 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]]

更新4： kriss 对 f3 进行了几处改进，用新的三元运算符语法替换了最小值/最大值。

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]]

更新5： 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.

性能优化列表推导式嵌套循环处理时间节点网格输入坐标邻域算法原生实现

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

5 个回答

撰写回答