一种高效的列表编辑算法

2024-03-29 10:47:24 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个三维点云,保存在两个列表中。具有5个点(x,y,z)的示例:(3,3,3)、(1,1,1)、(4,4,4)、(2,2,2)、(5,5,5)->;我的列表如下所示:

z = [3, 1, 4, 2, 5] # the z values
pts = [(3,3), (1,1), (4,4), (2,2), (5,5)] # the x and y values

现在我想消除z值大于3的所有值:

# what I want to receive:
z = [3, 1, 2]
pts = [(3,3), (1,1), (2,2)]

我的算法如下:

k = -1
for i in range(len(z)):
    k += 1
    if z[k] > h:
        z.pop(k)
        pts.pop(k)
        k -= 1

这正好返回了我想要的结果—但速度非常慢(对于>;100000个值)。 我想先通过z.sort()对我的列表进行排序,然后执行z=z[:index]——但是当我对z-list执行此操作时,我的pts列表仍然没有排序。即使我可以对这两个列表进行排序,我是否也需要经过一段很长的loop才能找到我的条件是true的索引? 有人知道更有效的解决方案吗?你知道吗


Tags: andthetogt算法示例列表for
3条回答

因为在迭代时要从列表中删除元素,所以这是一个O(N^2)算法。您可以使用简单的列表理解和zip在线性时间内完成这项工作。你知道吗

z = [3, 1, 4, 2, 5] # the z values
pts = [(3,3), (1,1), (4,4), (2,2), (5,5)] # the x and y values

merged = zip(z, pts)    
filtered = [x for x in merged if x[0] <= 3]
z, pts = zip(*filtered)

使用itertools:

from itertools import izip, ifilter

齐头并进

zipped_coords = izip(z, pts)

过滤器(在帖子中你提到了higher,但事实上导出的结果更低,选择了第一个)

filtered_coords = ifilter(lambda x: x[0]>=3, zipped_coords )

解压

znew, ptsnew = map(list, izip(*filtered_coords))

或一体机

>>> znew, ptsnew = map(list, izip(*ifilter(lambda x: x[0]>=3, izip(z, pts))))
>>> print znew, ptsnew
[3, 4, 5] [(3, 3), (4, 4), (5, 5)]
z, pts = zip(*[(z, pt) for z, pt in zip(z, pts) if z <= 3])
print z, pts

输出

(3, 1, 2) ((3, 3), (1, 1), (2, 2))

相关问题 更多 >