如何在Python中干净地同时迭代多个二维列表?

23

例如,如果我正在制作一个基于网格的简单游戏,我可能会有几个二维列表。其中一个可能用于地形,另一个可能用于对象等。但不幸的是,当我需要遍历这些列表并且一个列表中方块的内容会影响到另一个列表的某一部分时,我必须像下面这样做。

for i in range(len(alist)):
    for j in range(len(alist[i])):
        if alist[i][j].isWhatever:
            blist[i][j].doSomething()

有没有更好的方法来做类似这样的事情?

11个回答

33

如果有人对上述解决方案的性能感兴趣,则以下是4000x4000网格的排序,从最快到最慢:

编辑:添加了带有izip修改的Brian的得分,它赢得了大量优势!

John的解决方案也非常快,但它使用了索引(我真的很惊讶!)。 Robert和使用zip的Brian的速度比问题创作者最初的解决方案慢。

因此,让我们介绍Brian的获胜函数,因为在这个主题中没有以正确的形式显示:

from itertools import izip
for a_row,b_row in izip(alist, blist):
    for a_item, b_item in izip(a_row,b_row):
        if a_item.isWhatever:
            b_item.doSomething()

你尝试过原封不动地使用Brian的解决方案或者使用itertools.izip吗?另外,你愿意对我的建议进行基准测试吗? - tzot
添加后,结果再次令人惊讶。在您的情况下,似乎向对象添加一个意外的(不在__slots__中的)变量非常缓慢! - Dzinx
哦,初始化可以与现有的矩阵初始化合并。我不知道你为什么提到“not in __slots__”部分;我们不知道单元格对象是如何实现的。顺便说一下,你忘记调用a_item.isWhatever(即没有括号)。 - tzot
有趣的是,我曾认为在isWhatever很少见的情况下,原始方法会表现得更好,因为它根本不需要访问blist,但看起来索引查找更重要。即使在0.5%的isWhatever为真的情况下,izip方法也表现更好。 - Brian
我现在也为3D列表方法添加了一些时间记录,实际上它似乎更快了。 - Brian
显示剩余2条评论

15

我会从编写一个生成器方法开始:

def grid_objects(alist, blist):
    for i in range(len(alist)):
        for j in range(len(alist[i])):
            yield(alist[i][j], blist[i][j])

然后,每当你需要遍历列表时,你的代码看起来像这样:

for (a, b) in grid_objects(alist, blist):
    if a.is_whatever():
        b.do_something()

这不是同一件事,在第二个for循环中,范围取了alist[i]的长度,为什么你去掉了那个索引? - Andrea Ambu
我肯定最喜欢这个。它可能不是最好的答案,但我很可能会使用它。 - Eugene M
这只是对Eugene所写内容的语法糖。恐怕如果网格足够大,这个生成器可能会非常慢。毕竟,每个yield仍然需要四个索引查找。 - Dzinx
此外,将range()调用更改为xrange()可能是明智的选择。 - tzot

10
你可以将它们压缩成zip文件。例如:
for a_row,b_row in zip(alist, blist):
    for a_item, b_item in zip(a_row,b_row):
        if a_item.isWhatever:
            b_item.doSomething()

然而,如果你很少使用b_item(即a_item.isWhatever通常为False),那么压缩和迭代项目的开销可能比你原来的方法更高。你可以使用itertools.izip而不是zip来减少这种影响的内存占用,但除非你总是需要b_item,否则它仍然可能稍微慢一些。

或者,考虑使用一个三维列表,这样单元格i,j的地形就在l[i] [j] [0],物品在l[i][j][1]等等,甚至可以组合对象,这样你就可以进行a[i] [j] .terrain,a[i] [j].object等操作。

[编辑]DzinX的计时实际上显示,对于重新查找索引的性能惩罚,与额外检查b_item的影响并不显着,因此上面的方法(使用izip)似乎是最快的。

现在我已经为3d方法进行了快速测试,它似乎仍然更快,因此如果你可以以这种方式存储数据,那么访问数据可能既更简单又更快。这里有一个使用它的例子:

# Initialise 3d list:
alist = [ [[A(a_args), B(b_args)] for i in xrange(WIDTH)] for j in xrange(HEIGHT)]

# Process it:
for row in xlist:
    for a,b in row:
        if a.isWhatever(): 
            b.doSomething()

以下是我使用1000x1000数组进行10次循环的时间统计结果,不同的isWhatever为true的比例:

            ( Chance isWhatever is True )
Method      100%     50%      10%      1%

3d          3.422    2.151    1.067    0.824
izip        3.647    2.383    1.282    0.985
original    5.422    3.426    1.891    1.534

1
这是这里最快的解决方案,但只有在您将zip更改为itertools.izip时才是如此(请参阅我在下面某个帖子中的帖子)。 - Dzinx

5
当您在操作数字网格并需要非常好的性能时,应考虑使用Numpy。它非常易于使用,并使您可以以网格操作代替对网格的循环进行思考。性能来自于运算是使用优化的SSE代码在整个网格上运行。
例如,这里有一些numpy使用代码,我编写了一个由弹簧连接的带电粒子的暴力数值模拟。该代码在31ms内计算具有100个节点和99个边缘的3d系统的时间步长。这比我能想出的最佳纯Python代码快10倍以上。
from numpy import array, sqrt, float32, newaxis
def evolve(points, velocities, edges, timestep=0.01, charge=0.1, mass=1., edgelen=0.5, dampen=0.95):
    """Evolve a n body system of electrostatically repulsive nodes connected by
       springs by one timestep."""
    velocities *= dampen

    # calculate matrix of distance vectors between all points and their lengths squared
    dists = array([[p2 - p1 for p2 in points] for p1 in points])
    l_2 = (dists*dists).sum(axis=2)
    
    # make the diagonal 1's to avoid division by zero
    for i in xrange(points.shape[0]):
        l_2[i,i] = 1

    l_2_inv = 1/l_2
    l_3_inv = l_2_inv*sqrt(l_2_inv)

    # repulsive force: distance vectors divided by length cubed, summed and multiplied by scale
    scale = timestep*charge*charge/mass
    velocities -= scale*(l_3_inv[:,:,newaxis].repeat(points.shape[1], axis=2)*dists).sum(axis=1)

    # calculate spring contributions for each point
    for idx, (point, outedges) in enumerate(izip(points, edges)):
        edgevecs = point - points.take(outedges, axis=0)
        edgevec_lens = sqrt((edgevecs*edgevecs).sum(axis=1))
        scale = timestep/mass
        velocities[idx] += (edgevecs*((((edgelen*scale)/edgevec_lens - scale))[:,newaxis].repeat(points.shape[1],axis=1))).sum(axis=0)

    # move points to new positions
    points += velocities*timestep

3

生成器表达式itertools模块中的izip非常适合此处:

from itertools import izip
for a, b in (pair for (aline, bline) in izip(alist, blist) 
             for pair in izip(aline, bline)):
    if a.isWhatever:
        b.doSomething()

for语句中的行表示:

  • 从组合网格alistblist中取出每一行,并从它们创建一个元组(aline, bline)
  • 现在再次使用izip将这些列表组合起来,并从中取出每个元素(pair)。

此方法有两个优点:

  • 没有使用任何索引
  • 不必使用zip创建列表,而可以使用更高效的生成器izip

我相信是的。通过移除索引,您可以更明确地了解您在这里要完成的目标(操作对象,而不是它们的位置)。 - Dzinx
我认为迭代对象比迭代数字更加简洁。一个不错的方法。 - Brian

3

稍微改变一下样式,您可以使用枚举:

for i, arow in enumerate(alist):
    for j, aval in enumerate(arow):
        if aval.isWhatever():
            blist[i][j].doSomething()

我认为,除非像Federico建议的那样重新排列数据结构,否则您不会得到任何显著简化。这样,您就可以将最后一行转换为类似于“aval.b.doSomething()” 的内容。


2

你确定在并行迭代的两个矩阵中的对象是概念上不同的类的实例吗?如果将这两个类合并,最终得到一个包含 isWhatever() 和 doSomething() 的对象矩阵,会怎样呢?


1
如果在游戏生命周期内这两个2D列表保持不变并且你不能像其他人建议的那样享受Python的多重继承来连接alist[i][j]和blist[i][j]对象类,那么你可以在创建列表后为每个a项添加指向相应b项的指针,就像这样:
for a_row, b_row  in itertools.izip(alist, blist):
    for a_item, b_item in itertools.izip(a_row, b_row):
        a_item.b_item= b_item

这里可以应用各种优化,例如定义了__slots__的类,或将上面的初始化代码与您自己的初始化代码合并等。之后,您的循环将变为:

for a_row in alist:
    for a_item in a_row:
        if a_item.isWhatever():
            a_item.b_item.doSomething()

这应该更有效率。


这绝对是一个意想不到的答案。非常有趣。 - Eugene M

0
其他答案中常见的模式是尝试将两个输入压缩在一起,然后在每对嵌套的“行”列表中遍历元素。我建议反转这个过程,以获得更优雅的代码。正如Python之禅所说,“扁平比嵌套好”。
我采用以下方法设置了一个测试:
>>> class A:
...     def __init__(self):
...         self.isWhatever = True
... 
>>> 
>>> class B:
...     def doSomething(self):
...         pass
... 
>>> alist = [[A() for _ in range(1000)] for _ in range(1000)]
>>> blist = [[B() for _ in range(1000)] for _ in range(1000)]

将原本在3.x中表现最佳的代码进行调整,这是解决方案

def brian_modern():
    for a_row, b_row in zip(alist, blist):
        for a_item, b_item in zip(a_row, b_row):
            if a_item.isWhatever:
                b_item.doSomething()

因为现在,zip返回一个迭代器,而执行的是以前itertools.izip的功能。

在我的平台上(Linux Mint 20.3上的Python 3.8.10; Intel(R) Core(TM) i5-4430 CPU @ 3.00GHz,具有8GB的DDR3 RAM @ 1600MT/s),我得到了这个时间结果:

>>> import timeit
>>> timeit.timeit(brian_modern, number=100)
10.740317705087364

与其重复使用zip函数,我的方法是先将每个输入可迭代对象展开,然后再进行zip操作

from itertools import chain
def karl():
    flatten = chain.from_iterable
    for a_item, b_item in zip(flatten(alist), flatten(blist)):
        if a_item.isWhatever:
            b_item.doSomething()

这几乎提供了同样好的性能:

>>> karl()
>>> timeit.timeit(karl, number=100)
11.126002880046144

作为基准,让我们尝试将循环开销降到最低:

my_a = A()
my_b = B()
def baseline():
    a = my_a # avoid repeated global lookup
    b = my_b # avoid repeated global lookup
    for i in range(1000000):
        if a.isWhatever:
            b.doSomething()

然后检查实际对象检查逻辑使用了多少时间:

>>> timeit.timeit(baseline, number=100)
9.41121925599873 

因此,预扁平化方法确实会产生更多的开销(约为18%,而重复压缩方法约为14%)。但是,即使对于微不足道的循环体,它仍然是相当小的开销,并且还允许我们更优雅地编写代码。


在我的测试中,这是预扁平化最快的方法。将参数展开到itertools.chain中稍微慢一些,而使用生成器表达式来扁平化输入...
def karl_gen():
    a_flat = (i for row in alist for i in row)
    b_flat = (j for row in blist for j in row)
    for a_item, b_item in zip(a_flat, b_flat):
        if a_item.isWhatever:
            b_item.doSomething()

...速度慢得多:

>>> timeit.timeit(karl_gen, number=100)
16.904560427879915

在这里切换到列表推导式几乎对速度与生成器没有什么影响,同时也会暂时将内存需求翻倍。因此,itertools.chain.from_iterable 是一个明显的赢家。


0
如果 a.isWhatever 很少为真,你可以先构建一个“索引”:
a_index = set((i,j) 
              for i,arow in enumerate(a) 
              for j,a in enumerate(arow) 
              if a.IsWhatever())

每当你想要完成某件事情时:

for (i,j) in a_index:
    b[i][j].doSomething()

如果一个变量随着时间而改变,那么你需要保持索引的最新状态。这就是为什么我使用了一个集合,因为可以快速添加和删除元素。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接