0

我想对元组列表 [(0, 9), (5, 4), (2, 9), (7, 4), (7, 2)] 进行排序以得到 [(0, 9), ( 2, 9), (7, 2), (7, 4), (5, 4)]。

更具体地说，我有一组要连接成链（折线）的边（线段）。边缘的顺序是随机的，我想对它们进行排序。每条边都有两个节点，起点和终点，它们可能与最终链中的方向匹配，也可能不匹配。下面的代码可以工作，但速度非常慢，尤其是当我必须多次调用这个函数时。在我的例子中，节点是自定义 Node 类的实例，而不是整数。平均而言，可能有大约 10 条边要连接。我必须在 Ironpython 中运行它。请问有没有什么好方法可以提高这个速度？非常感谢！

克里斯

from collections import Counter

class Edge():
    def __init__(self,nodeA,nodeB,edges):
        self.nodes = (nodeA,nodeB)
        self.index = len(edges)
        edges.append(self)

def chainEdges(edges):
    # make chains of edges along their connections
    nodesFlat = [node for edge in edges for node in edge.nodes]
    if any(Counter(nodesFlat)[node]>2 for node in nodesFlat): return# the edges connect in a non-linear manner (Y-formation)
    # find first edge
    elif all(Counter(nodesFlat)[node]==2 for node in nodesFlat):# the edges connect in a loop
        chain = [min(edges, key=lambda edge: edge.index)]# first edge in the loop is the one with the lowest index
        edges.remove(chain[-1])
        nodeLast = chain[-1].nodes[-1]
    else:# edges form one polyline
        chain = [min([edge for edge in edges if any(Counter(nodesFlat)[node]==1 for node in edge.nodes)], key=lambda edge: edge.index)]# first edge is the one with the lowest index
        edges.remove(chain[0])
        nodeLast = chain[-1].nodes[0] if Counter(nodesFlat)[chain[-1].nodes[0]]==2 else chain[-1].nodes[1]
    # loop through remaining edges
    while len(edges)>0:
        for edge in edges:
            if nodeLast in edge.nodes:
                chain.append(edge)
                edges.remove(edge)
                nodeLast = edge.nodes[0] if nodeLast==edge.nodes[1] else edge.nodes[1]
                break
    return chain

edges = []
for [nodeA,nodeB] in [(0, 9), (5, 4), (2, 9), (7, 4), (7, 2)]:
    Edge(nodeA,nodeB,edges) 
print [edge.nodes for edge in chainEdges(edges)]

>>>[(0, 9), (2, 9), (7, 2), (7, 4), (5, 4)]
4

1 回答 1

0

我发现了问题，慢的部分是我检查 Y 形的方式，当超过 2 条边连接在一个节点上时。当我运行该方法时，我已经检查了所有边缘是否以某种方式连接，但我不知道它们是形成一条线、一个圆还是一个 Y。以下明显更快：

def chainEdges(edges):
    # make chains of edges along their connections
    chain = [min(edges, key=lambda edge: edge.index)]
    edges.remove(chain[-1])
    nodesSorted = list(chain[-1].nodes)
    while len(edges)>0:
        for edge in edges[:]:
            if nodesSorted[0] in edge.nodes:
                chain.insert(0,edge)
                edges.remove(edge)
                nodesSorted.insert(0,edge.nodes[0] if nodesSorted[0]==edge.nodes[1] else edge.nodes[1])
                if nodesSorted[0] in nodesSorted[1:-1] or (nodesSorted[0]==nodesSorted[-1] and len(edges)>0): chain = [False]# the edges connect in a non-linear manner (Y-formation)
                break
            elif nodesSorted[-1] in edge.nodes:
                chain.append(edge)
                edges.remove(edge)
                nodesSorted.append(edge.nodes[0] if nodesSorted[-1]==edge.nodes[1] else edge.nodes[1])
                if nodesSorted[-1] in nodesSorted[1:-1]: chain = [False]# the edges connect in a non-linear manner (Y-formation)
                break
        else: chain = [False]# the edges connect in a non-linear manner (Y-formation)
        if chain == [False]: break
    return chain
于 2020-08-01T18:11:04.857 回答