加快查找两个字典之间的匹配项（Python）

Question

我正在使用python2.7处理一个空间分析问题。我有一个字典edges表示图形中的边，其中key是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，其中key是nodeID，value是节点坐标：

^{pr2}$

我需要得到一个列表，它看起来像（键中的'n'和'e'只是为了说明这个问题，我这里有整数）：

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

也就是说，我迭代边dict，获取每个键，找到nodesdict中存在的值并添加到元组中。我现在就是这样做的：

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循环迭代边（如果这样可以加快速度）？在

有没有其他方法可以更快地建立这样的列表？

更新

正如马丁建议的那样，我把我的节点颠倒了一下：

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

将节点坐标元组作为键，节点ID作为值。不幸的是，它没有加快查找过程（这是更新的代码-我为edgeStartPoint和{}翻转了k和{}）：

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

根据您的示例数据，这里有一个我认为可能有用的示例：

edges = {
    1: [(12.8254, 55.3880), (12.8343, 55.3920)],
    2: [(12.8254, 55.3880), (12.8235, 55.3857)],
    3: [(12.2432, 57.1120), (12.2426, 57.1122)]}
nodes = {
    14: (12.8254, 55.3880),
    15: (12.8340, 55.3883),
    16: (12.8235, 55.3857),
    17: (12.8343, 55.3920)}
reverseNodes=dict((v,k) for k, v in nodes.iteritems())
edgesList=[]
for k,v in edges.items():
    edgesList.append( 
            (k,
             reverseNodes.get(v[0], -1),
             reverseNodes.get(v[1], -1)))

也许我不明白你建造的edgesList但我认为这看起来更简单、更快。在

再次根据示例代码，这是消耗cpu时间的原因：

^{pr2}$

这存在于for循环中，因此对于每个边，您：

• 在边列表上多迭代一次（以找到已有的edge id）
• 在nodes列表上迭代两次以查找起点和终点（您不再需要这样做了，因为我们已经了解了如何使用reverseNodes dict进行直接查找）。在

所以用你的数据大小，你应该得到大约100000*（100000+90000+90000）或者O（n^2）操作，这比仅仅一次通过边缘（100000或O（n））要多得多

Answer 2

正如您在评论中发现的，问题是最后一个操作edgesList.append((id,start,end))。在

这似乎是一个数据类型的问题：一个大字典因设计而变慢。看看here。在

但是很高兴您可以使用双端队列（deque）来代替。deque documentation：“Deques支持线程安全、内存高效的附件和pop，在任何一个方向上都具有几乎相同的O（1）性能。”

在代码中，这意味着您可以初始化一个deque并以高性能附加到它。在

edgesList = deque() 
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 3

因为您是基于坐标进行匹配的，所以应该反转节点字典。在

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

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

这样，当您在边上迭代时，可以快速查找相应的节点：

^{pr2}$

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