查找列表中两个列表之间的公共元素的最快方法

Question

我试图在有向图中识别气泡结构（方向是从左到右）。我从一个可能的开始节点开始遍历图形，例如绿色节点。然后我向所有路径添加一个节点，当路径再次分叉时添加路径的副本，如下所示：

第一次迭代： [[3]，[7]]

第二次迭代：[[3,4]，[3,5]，[7,8]，[7,9]]

每次迭代之后，我都要检查是否有路径相交，并将它们保存为已确认的气泡。目前我正在使用一个嵌套for循环来比较每个路径，但是路径的数量会变得非常大，因此脚本会变得非常慢。路径的顺序很重要。你知道吗

关于如何提高将路径列表中的一条路径与另一条路径进行比较的速度，有什么建议吗？你知道吗

def ExtendPaths(paths, outEdges):
newPaths = []
for path in paths:                                              
    nextNodes = GetNextSegment(path[len(path) - 1], outEdges)   
    if len(nextNodes) == 0:
        j=5
    else:
        for node in nextNodes:                                      
            newPath = list(path)                                    
            newPath.append(node)                                    
            newPaths.append(newPath)                    
return newPaths

def ComparePaths(paths, putativeBubbleStartSegment):
length = len(paths)
for path1 in paths:
    for path2 in paths:
        if path2 != path1:
            if len(set(path1).intersection(path2)) > 0:
                #Bubble confirmed

其中GetNextSegment只返回连接到给定给函数的节点（在本例中是路径的最后一个节点）的节点列表。outEdges是一个字典，具有：node:[out，go，edges]。在ComparePaths（）中，当两条路径的.intersection（）长度大于0时，将确认气泡。你知道吗

气泡是一种图形结构，其中两条路径分开（例如，从绿色节点开始），最后再次聚集在一起。在本例中，气泡将从2变为11，所有节点位于气泡之间。你知道吗

我并不是要一个完整的气泡查找算法，只是想知道如何快速地将所有路径与所有其他路径进行比较。你知道吗

Answer 1

与其使用列表列表，不如考虑使用一组元组（如果顺序重要）或一组冻结集（如果顺序不重要）。用newPaths = set()初始化newPaths，然后将每个路径添加为元组或冻结集（可散列），而不是列表：

for node in nextNodes:                                      
    newPath = tuple(path) + (node,)
    # or: newPath = frozenset(path).union({node})
    newPaths.add(newPath)

这将使检查成员资格和交叉点的速度更快一些。你知道吗

另外，通过循环paths两次，看起来您正在多次检查相同的路径。例如，如果path1等于(3, 4)，path2等于(3, 5)，则不需要检查(3, 4)与(3, 5)以及(3, 5)与(3, 4)，因为您的检查看起来是对称的。您可以使用itertools助手来简化ComparePaths：

from itertools import combinations

def ComparePaths(paths, putativeBubbleStartSegment):
    # This gets all combinations of paths without repeating any pairing.
    for path1, path2 in combinations(paths, 2)
        # Don't need to check the length of the intersection because an
        # empty set is always equivalent to "False" in an if statement.
        if set(path1).intersection(path2):
            # Bubble confirmed

您的示例代码似乎遗漏了一些细节（因为有未使用的函数参数和变量），但我在这里看到的似乎不适合您所尝试的操作。因此，即使有其他方法可以改进算法，也很难提出任何其他的加速建议。你知道吗