python性能:嵌套列表上的迭代和操作

问题嘿,乡亲们。我正在寻找一些关于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的数量可能会增加到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 循环。 f2 是代替内在的 对于 循环使用列表理解。 f3 根据安德烈在评论中的建议,替换了外部 对于 具有 map() f 克里斯的建议是否在下面的答案中? f3b 克丽丝是不是喜欢上了? F3 f4 是亚历克斯的贡献。

下面的代码供您阅读。

问题如何进一步缩短处理时间?测试参数我更喜欢Sub-1.0s。

拜托, 保留对本机python的建议。我知道我可以转到第三方软件包,比如 numpy 但是我想避免任何第三方软件包。此外,我还生成了随机输入坐标,并简化了节点值更新的定义,使我们的讨论变得简单。具体情况必须稍微改变,超出我的问题范围。

多谢!

F1 是初始的简单实现:三个嵌套 对于 循环。

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 是代替内在的 对于 循环使用列表理解。

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() . 我在这方面的第一次黑客攻击需要几个本地范围外的查找,特别是 recommended against 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 ,将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]]

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