Ускорить поиск совпадений между двумя словарями (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, где ключ является NodeId и значение является узлом координаты:

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

Мне нужно, чтобы получить список, который будет выглядеть как (с «п» и «е» в ключах только для целей иллюстрации на этот вопрос, у меня есть целые там):

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

То есть, я перебираю по краям dict, беру каждую клавишу, нахожу значение, которое существует в типе 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 (если это ускорит работу вверх)?

Есть ли другой способ построить такой список быстрее?

UPDATE

Как предположил Мартин, я перевернутой мои узлы Dict:

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

, имеющий узел координирует кортеж в качестве ключа и NodeId в качестве значения. К сожалению, это не ускорит процесс поиска (здесь обновленный код - я перевернул 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 или размер 1 миллион.

Answer 2

Как выяснилось в комментариях, проблема является последней операцией edgesList.append((id,start,end)).

Это похоже на проблему с типом данных: большой словарь замедляется по дизайну. посмотрите here.

, но с радостью вы можете использовать двойную очередь (deque). deque documentation: «Deques поддерживает потокобезопасную, эффективную память, добавляет и всплывает с обеих сторон deque с примерно одинаковой производительностью 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

Основываясь на вашем примере данных здесь пример, я думаю, может работать:

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, но я думаю, что это выглядит проще и быстрее.

Опять основано на вашем примере кода, это то, что отнимает много вашего процессора времени:

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 

Это существует внутри для цикла, так что для каждого ребра вы:

• итерацию один дополнительный время для списка ребер (чтобы найти идентификатор края, который у вас уже есть)
• Идите дважды по списку узлов, чтобы найти начальную и конечную точки (вам это больше не нужно, поскольку мы выяснили, поиск с помощью reverseNodes-dict).

Так с datasizes вы должны получить примерно 100000 * (100000 + 90000 + 90000) или O (N^2) операций, что намного больше, чем просто один проход по краям (100000 или O (N))