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

Question

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

{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

如您的评论所述，问题出在最后一个操作 edgesList.append((id,start,end))。

这似乎是一个数据类型问题：一个大字典在设计上会减慢速度。看看here.

但很高兴您可以改用双端队列 (deque)。 deque documentation: "Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction."

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

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 2

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

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

{(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 万。

Answer 3

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

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 时间的原因：

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

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

在边列表上额外迭代一次（以找到您已有的边 ID）
在节点列表上迭代两次以找到起点和终点（您不再需要它，因为我们已经弄清楚如何使用 reverseNodes-dict 进行直接查找）。

因此，对于您的数据大小，您应该获得大约 100000*(100000+90000+90000) 或 O(n^2) 次操作，这远远超过一次边缘传递（100000 或 O(n)）

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

Speed up finding matches between two dictionaries (Python)

python

dictionary

list-comprehension

list