将包含未排序内容的元组快速排序到链中

Question

我想对元组列表[（0,9），（5,4），（2,9），（7,4），（7,2）]进行排序，得到[（0,9），（2,9），（7,2），（7,4），（5,4）]

更具体地说，我有一组要连接到链（多段线）中的边（线段）。边的顺序是随机的，我想对它们进行排序。每条边都有两个节点，即起点和终点，它们在最终链中的方向可能匹配也可能不匹配。下面的代码可以工作，但速度非常慢，特别是我必须多次调用这个函数。在我的例子中，节点是自定义节点类的实例，而不是整数。平均而言，可能有大约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)]

Answer 1

我发现了问题所在，最慢的部分是当一个节点上有两条以上的边连接时，我是如何检查Y形的。当我运行该方法时，我已经检查了所有边是否以某种方式连接，但我不知道它们是否形成一条线、一个圆或一个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