python - 如何通过遵循相邻标准快速收集点列表

Question

我有一个点列表L=[[x1,y1],[x2,y2],...]并且我想构建一个列表S=[L1 ,L2,...] 通过收集L 的邻近点生成的“表面”。 “表面”的类型与 L 的类型相同，即点列表(但构成基于邻居链接的表面)。但是，我尝试做的还不够快。

我使用了递归函数F(L, P)，它需要点L列表和起点P=[x,y] (调用函数时必须将其从列表L 中删除)。然后，它查找 P 的所有邻居点，如果存在，则回调每个点上的函数(在将它们从 L 中删除之后)。当测试的点不再有邻居点时，达到基本情况。

因此，当达到所有基本情况时，F(L, P) 返回构成表面的点L1列表与P相关联。然后，我对 L 的剩余点重复该过程，依此类推，构建 L2,L3,...。

def F(L,P):   
    nhList=[]
    leftP=[P[0]+1,P[1]]
    rightP=[P[0]-1,P[1]]
    upP=[P[0],P[1]-1]
    dwP=[P[0],P[1]+1] 

    if(upP in L):
        L.remove(upP)
        nhList.append(upP)
    if(dwP in L):
        L.remove(dwP)
        nhList.append(dwP)
    if(leftP in L):
        L.remove(leftP)
        nhList.append(leftP)
    if(rightP in L):
        L.remove(rightP)
        nhList.append(rightP)

    if(nhList!=[]):
        rtList=[P]
        for ad in nhList:
            e=F(L,ad)
            rtList+=e
        return rtList
    else:
        return [P]

L=[[0,0],[1,0],[5,3],[1,1],[5,4],[2,2]] # e.g.
S=[]
while(L!=[]):
    P=L.pop()
    S.append(F(L,P))
print(S)
# Returns [[2, 2]], [[5, 4], [5, 3]], [[1, 1], [1, 0], [0, 0]] as expected

我希望按照简介中的说明检索列表S，并且效果很好。然而，当我在更大的点列表(例如包含 1M 点)上使用此过程时，它会减慢处理速度，有时，我什至达到递归限制。

因此，我希望更快地生成列表S。

Answer 1

我认为你可以通过以下想法来提高性能:

1. 在大数据中，为了避免递归限制，您可以使用迭代而不是递归
2. 为了增强 L 中查询和修改的性能，您可以将L预处理为 >设置
3. 对于算法，BFS 适合这里。

这是我的解决方案:

from collections import deque

L = [[0, 0], [1, 0], [5, 3], [1, 1], [5, 4], [2, 2]]  # e.g.
# convert to set for query and modify performance, change list to immutable tuple.
L = set(map(tuple, L))

S = []
while L:
    # start from a random point
    start = L.pop()
    queue, visited, cur_s = deque([start]), set([start]), [start]

    while queue:
        node = queue.popleft()
        visited.add(node)
        i, j = node
        # find the 4-adjacent neighbors
        for neighbor in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
            if neighbor in L and neighbor not in visited:
                queue.append(neighbor)
                cur_s.append(neighbor)
                L.remove(neighbor)
    S.append(cur_s)

print(S)

输出:

[[(5, 4), (5, 3)], [(0, 0), (1, 0), (1, 1)], [(2, 2)]]

希望对您有帮助，如有疑问请评论。 :)