python - 加快查找两个词典之间的匹配项 (Python)

Question

我正在使用 Python 2.7 解决空间分析问题。我有一个字典 edges 表示图中的边，其中键是 edgeID，值是起点/终点:

{e1: [(12.8254, 55.3880), (12.8343, 55.3920)], 
e2: [(12.8254, 55.3880), (12.8235, 55.3857)], 
e3: [(12.2432, 57.1120), (12.2426, 57.1122)]}

我还有另一个字典 nodes，其中键是节点 ID，值是节点坐标:

{n14: (12.8254, 55.3880), 
n15: (12.8340, 55.3883), 
n16: (12.8235, 55.3857), 
n17: (12.8343, 55.3920)}

我需要一个列表，看起来像(键中的“n”和“e”只是为了说明这个问题，我在那里有整数):

[(e1,n14,n17),(e2,n14,n16)..]

也就是说，我遍历边缘字典，获取每个键，找到 nodes 字典中存在的值并添加到元组中。这就是我现在的做法:

edgesList = []
for featureId in edges:
        edgeFeatureId = [k for k, v in edges.iteritems() if k == featureId][0]
        edgeStartPoint = [k for k, v in nodes.iteritems() if v == edges[featureId][0]][0]#start point
        edgeEndPoint = [k for k, v in nodes.iteritems() if v == edges[featureId][1]][0]#end point
        edgesList.append((edgeFeatureId,edgeStartPoint,edgeEndPoint))

这是可行的，但在处理大型数据集时速度非常慢(使用 100K 边和 90K 节点大约需要 10 分钟)。

我已经弄清楚如何在获取元组的每个项目时使用列表推导，但是是否可以将我的 3 个列表推导合二为一以避免使用 for 循环迭代边缘(如果这会加快速度)？

还有其他方法可以更快地构建这样的列表吗？

更新

正如 Martin 所建议的，我已经颠倒了我的节点指令:

nodesDict = dict((v,k) for k,v in oldnodesDict.iteritems())

将节点坐标元组作为键，将节点 ID 作为值。不幸的是，它并没有加快查找过程(这是更新后的代码 - 我将 k 和 v 翻转为 edgeStartPoint 和 edgeEndPoint):

edgesList = []
for featureId in edges:
        edgeFeatureId = [k for k, v in edges.iteritems() if k == featureId][0]
        edgeStartPoint = [v for k, v in nodes.iteritems() if k == edges[featureId][0]][0]#start point
        edgeEndPoint = [v for k, v in nodes.iteritems() if k == edges[featureId][1]][0]#end point
        edgesList.append((edgeFeatureId,edgeStartPoint,edgeEndPoint))

Answer 1

由于您是根据坐标进行匹配，因此您的节点字典应该倒置。

也就是说，它应该是这样的:

{(12.8254, 55.3880): n14, 
(12.8340, 55.3883): n15, 
(12.8235, 55.3857): n16, 
(12.8343, 55.3920): n17}

这样，当您遍历边缘时，您可以非常快速地查找相应的节点:

edgesList = []
for featureId in edges:
    coordinates = edges[featureId]
    c0, c1 = coordinates

    n0 = nodes[c0]
    n1 = nodes[c1]

    edgesList.append((featureId, n0, n1))

请记住，字典可以非常快速地找到任何给定键的对应值。如此之快以至于在一般情况下，查找的速度should barely change假设字典的大小为 1 或 100 万。