Ускорить поиск совпадений между двумя словарями (Python)

Я работаю над проблемой пространственного анализа, используя 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, где ключ — это идентификатор узла, а значение — координаты узла:

{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))

Это работает, но очень медленно при работе с большими наборами данных (с 100 000 ребер и 90 000 узлов это занимает около 10 минут).

Я понял, как использовать понимание списка при получении каждого из элементов кортежа, но возможно ли объединить мои 3 понимания списка в одно, чтобы избежать повторения ребер с помощью цикла for (если это ускорит процесс)?

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

ОБНОВЛЕНИЕ

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

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))

python list dictionary list-comprehension
person Alex Tereshenkov    schedule 27.02.2015    source источник
comment
Не могли бы вы создать объект, представляющий ребро? Вы могли бы перегрузить функцию equal или другую функцию, чтобы облегчить работу с этой структурой данных?   -  person Marcin    schedule 27.02.2015
comment
@Marcin, вы имели в виду создание класса для граничного объекта? Я надеялся, что смогу найти какое-то умное сопоставление словарей, но смог найти что-нибудь подходящее.   -  person Alex Tereshenkov    schedule 27.02.2015
comment
Да, класс Edge. Кажется, что это может быть просто ваш код и операции по краям.   -  person Marcin    schedule 27.02.2015
comment
Хорошо, спасибо за совет. Операция, которую я пытаюсь ускорить, является последней, которую я буду выполнять в Python, вся обработка данных, которая происходит перед ней, происходит за секунды, это просто последняя часть, которая занимает так много времени. Я хотел бы избежать создания класса для Edge, так как я не буду использовать его ни для чего другого...   -  person Alex Tereshenkov    schedule 27.02.2015
comment
так что ваша проблема в append ()? затем попробуйте использовать дек как edgesList: docs.python.org/2/ library/collections.html#collections.deque Двухсторонние очереди поддерживают потокобезопасные, эффективно использующие память операции добавления и извлечения с любой стороны двухсторонней очереди с примерно одинаковой производительностью O(1) в любом направлении.   -  person donmarkusi    schedule 27.02.2015
comment
Почему вы используете iteritems() везде, точка словаря - это поиск по ключу, с iteritems() у вас есть производительность O (N) при каждом поиске. Либо переупорядочите свои данные, чтобы разрешить поиск по ключу, либо переключитесь на структуру типа двоичного дерева поиска, которая, по крайней мере, даст Olog (n).   -  person user3467349    schedule 27.02.2015
comment
@ user3467349, спасибо, что указали на это. Я считаю, что это то, что Мартин упомянул в ответе, принятом мной.   -  person Alex Tereshenkov    schedule 27.02.2015

Ответы (3)


arrow_upward
2
arrow_downward

Поскольку вы сопоставляете на основе координат, ваш словарь узлов должен быть инвертирован.

То есть это должно выглядеть так:

{(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))

Помните, что словари очень быстро находят соответствующее значение для любого заданного ключа. Настолько быстро, что в среднем скорость поиска почти не изменится, учитывая, что словарь размером 1 или размером 1 миллион.

person Martin Konecny    schedule 27.02.2015
comment
Мартин, что такое переменные координат? Я не понимаю, как работает edgeFeatureId, coordinates = e. - person Alex Tereshenkov; 27.02.2015
comment
x, y = [1, 2] означает, что x станет 1, а y станет 2. Вам нужно использовать код, который я предоставил, а не просто инвертировать словарь. - person Martin Konecny; 27.02.2015
comment
Я немного неправильно понимаю ваш исходный код. Обновил мой ответ - теперь он должен быть более ясным. - person Martin Konecny; 27.02.2015
comment
с 'coordinates = edges[featureId] это имеет смысл. Я только что понял, что просматривал значения с помощью == вместо того, чтобы ссылаться на значение, основанное на ключе с dict[key]. Спасибо за указание на это, это работает правильно и очень быстро. - person Alex Tereshenkov; 27.02.2015

arrow_upward
1
arrow_downward

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

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

но с удовольствием вместо этого вы можете использовать двустороннюю очередь (deque). документация по deque: "Deques поддерживает и выталкивается с любой стороны дека примерно с одинаковой производительностью O(1) в любом направлении».

в коде это означает, что вы инициализируете очередь и добавляете к ней высокую производительность.

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))
person donmarkusi    schedule 27.02.2015
comment
Спасибо за совет. Для какого dict я должен использовать набор вместо этого? И как мне обратиться к ключу set при поиске узла? Любой фрагмент кода? - person Alex Tereshenkov; 27.02.2015
comment
ах, извините, набор использует только значения. я немного устал этим утром :D я снова думаю об этом - person donmarkusi; 27.02.2015

arrow_upward
1
arrow_downward

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

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

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

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

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

person UlfR    schedule 27.02.2015