0

我有一个我想合并的“盒子定义”的排序列表。该列表看起来像：

big_list = [\
# ...
# ...
[3, 4, 5, 4, 5, 6, 65],\
[3, 4, 5, 4, 5, 6, 60],\
[3, 4, 5, 4, 5, 6, 55],\
[3, 4, 5, 4, 5, 6, 52],\
[3, 4, 5, 4, 5, 6, 23],\
[3, 4, 5, 4, 5, 6, 17],\
[3, 4, 5, 4, 5, 6, 0],\
[5, 8, 9, 6, 9, 10, 90],\
[5, 8, 9, 6, 9, 10, 84],\
[5, 8, 9, 6, 9, 10, 32],\
[5, 8, 9, 6, 9, 10, 0],\
# ...
# ...
[750, 800, 900, 751, 801, 901, 97],\
[750, 800, 900, 751, 801, 901, 24],\
[750, 800, 900, 751, 801, 901, 17],\
[750, 800, 900, 751, 801, 901, 16],\
[750, 800, 900, 751, 801, 901, 0]\
# ...
# ...
]

其中“格式”框为：[x1, y1, z1, x2, y2, z2, attribute]，我们可以假设 dx=1, dy=1, dz=1

此外，我们可以假设列表已经按以下方式排序：

big_list=sorted(big_list, key=lambda n:n[6], reverse=True)
big_list=sorted(big_list, key=lambda n:n[2])
big_list=sorted(big_list, key=lambda n:n[1])
big_list=sorted(big_list, key=lambda n:n[0])

该列表可能有数百万个项目长，我想减少列表，以便任何离散的“盒子”只能获得最高的“属性”......所以在这种情况下，比如：

reduced_big_list = [\
[3, 4, 5, 4, 5, 6, 65],\
[5, 8, 9, 6, 9, 10, 90],\
[750, 800, 900, 751, 801, 901, 97]\
]

我目前在此列表中使用的方法类似于：

i = 0

while i < len(big_list)-1:
     if big_list[i][0]==big_list[i+1][0]\
     and big_list[i][1]==big_list[i+1][1]\
     and big_list[i][2]==big_list[i+1][2] \
     and big_list[i][6] >= big_list[i+1][6]:
          del big_list[i+1]
     else:
          i=i+1

问题是当列表很“长”（1000 万+“盒子”）时，这个过程非常非常慢。

有没有一种聪明的方法可以并行化这个列表“抽取”过程或者加快这个过程？

4

3 回答 3

1

缓慢是对 的调用del，它将列表的完整尾部的项目移动了一步。在您的情况下，根本不要使用del. 而是创建一个新列表，从一个空列表开始，append然后选择要保留的项目。

于 2013-05-13T21:19:08.173 回答
1

慢的原因是每次你del一行都需要线性时间，使得整个过程为 O(n^2)。

如果不是从原始列表中删除行，而是将要保留的行附加到新列表中，它应该会快得多。

但是还有其他可能更 Pythonic 的方法来执行相同的操作。例如，使用itertools.groupby（假设列表按您指定的方式排序）：

from itertools import groupby
new_list = [next(group) for val,group in groupby(big_list, key=lambda x: x[:3])]

这将按前 3 个元素对列表项进行分组，并返回每个组中第一项的列表。

于 2013-05-13T21:19:53.117 回答
1

布尔and值首先计算左表达式。如果第一个表达式为真，它只评估右手表达式。由于您已经对列表进行了排序，因此相邻元素可能比后面的元素更有可能具有相同的第 0 个元素。尝试

i = 0

while i < len(big_list)-1:
    if big_list[i][2]==big_list[i+1][2]\
    and big_list[i][1]==big_list[i+1][1]\
    and big_list[i][0]==big_list[i+1][0]\
    and big_list[i][6] >= big_list[i+1][6]:
        del big_list[i+1]
    else:
        i=i+1
于 2013-05-13T21:22:37.750 回答