Сравнение массивных списков словарей в python

Я никогда не думал, что столкнулся с проблемами скорости с python, но у меня есть. Я пытаюсь сравнить действительно большие списки словарей друг с другом на основе значений словаря. Я сравниваю два списка, с первым таким образом

biglist1=[{'transaction':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, ...]

С 'somevalue', стоящим для генерируемой пользователем строки, int или десятичной. Теперь второй список довольно похож, за исключением того, что значения id всегда пусты, поскольку они еще не назначены.

biglist2=[{'transaction':'somevalue', 'id':'', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'', 'date':'somevalue' ...}, ...]

Итак, я хочу получить список словарей в biglist2, которые соответствуют словарям в biglist1 для всех других ключей, кроме id.

Я делал

for item in biglist2:
    for transaction in biglist1:
       if item['transaction'] == transaction['transaction']:
          list_transactionnamematches.append(transaction)

for item in biglist2:
    for transaction in list_transactionnamematches:
       if item['date'] == transaction['date']:
          list_transactionnamematches.append(transaction)

... и т.д., не сравнивая значения id, пока не получу окончательный список совпадений. Так как списки могут быть действительно большими (около 3000+ элементов каждый), это займет довольно много времени, чтобы python прошел цикл.

Я предполагаю, что на самом деле это не так, как это должно быть сделано. Любые идеи?

Ответ 1

Указатель на поля, которые вы хотите использовать для поиска. O (N + M)

matches = []
biglist1_indexed = {}

for item in biglist1:
    biglist1_indexed[(item["transaction"], item["date"])] = item

for item in biglist2:
    if (item["transaction"], item["date"]) in biglist1_indexed:
        matches.append(item)

Это, вероятно, в тысячи раз быстрее, чем вы делаете сейчас.

Ответ 2

Что вы хотите сделать, это использовать правильные структуры данных:

Создайте словарь сопоставлений кортежей других значений в первом словаре с их идентификатором.
Создайте два набора кортежей значений в обоих словарях. Затем используйте операции набора, чтобы получить нужный набор кортежей.
Используйте словарь из точки 1, чтобы назначить идентификаторы этим кортежам.

Ответ 3

Простите мой ржавый синтаксис python, это было какое-то время, поэтому рассмотрим этот частично псевдокод

import operator
biglist1.sort(key=(operator.itemgetter(2),operator.itemgetter(0)))
biglist2.sort(key=(operator.itemgetter(2),operator.itemgetter(0)))
i1=0;
i2=0;
while i1 < len(biglist1) and i2 < len(biglist2):
    if (biglist1[i1]['date'],biglist1[i1]['transaction']) == (biglist2[i2]['date'],biglist2[i2]['transaction']):
        biglist3.append(biglist1[i1])
        i1++
        i2++
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) < (biglist2[i2]['date'],biglist2[i2]['transaction']):
        i1++
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) > (biglist2[i2]['date'],biglist2[i2]['transaction']):
        i2++
    else:
        print "this wont happen if i did the tuple comparison correctly"

Сортирует оба списка в один и тот же порядок, по (дата, транзакция). Затем он проходит через них бок о бок, пробираясь через каждый, кто ищет относительно смежные матчи. Он предполагает, что (дата, транзакция) уникальна и что я не полностью покидаю свой рокер в отношении сортировки и сравнения кортежей.

Ответ 4

В O (m * n)...

for item in biglist2:
    for transaction in biglist1:
       if (item['transaction'] == transaction['transaction'] &&
           item['date'] == transaction['date'] &&
           item['foo'] == transaction['foo'] ) :

          list_transactionnamematches.append(transaction)

Ответ 5

Подход, который я, вероятно, возьму на себя, это сделать очень легкий класс с одной переменной экземпляра и одним методом. Переменная экземпляра - указатель на словарь; метод переопределяет встроенный специальный метод __hash__(self), возвращая значение, рассчитанное из всех значений в словаре, кроме id.

Оттуда решение кажется довольно очевидным: создайте два первоначально пустых словаря: N и M (для совпадений и совпадений). Перебирайте каждый список ровно один раз и для каждого из этих словарей, представляющих транзакцию ( назовем его Tx_dict), создайте экземпляр нового класса (a Tx_ptr). Затем проверьте элемент, соответствующий этому Tx_ptr в N и M: если в N нет соответствующего элемента, вставьте текущий Tx_ptr в N; если в N есть соответствующий элемент, но не соответствующий элемент в M, вставьте текущий Tx_ptr в M с самим Tx_ptr в качестве ключа и список, содержащий Tx_ptr в качестве значения; если имеется соответствующий элемент в N и в M, добавьте текущий Tx_ptr к значению, связанному с этим ключом в M.

После того, как вы пройдете каждый элемент один раз, ваш словарь M будет содержать указатели на все транзакции, которые соответствуют другим транзакциям, все они аккуратно сгруппированы в списки для вас.

Изменить: Ой! Очевидно, что правильное действие, если существует соответствие Tx_ptr in N, но не в M, заключается в том, чтобы вставить пару ключ-значение в M с текущим Tx_ptr в качестве ключа, а в качестве значения - список текущих Tx_ptr и Tx_ptr, которые уже были в N.

Ответ 6

Посмотрите на Psyco. Его компилятор Python, который может создать очень быстрый, оптимизированный машинный код из вашего источника.

http://sourceforge.net/projects/psyco/

Хотя это не является прямым решением проблем с эффективностью кода, оно все равно может помочь ускорить работу без необходимости писать новый код. Тем не менее, я по-прежнему настоятельно рекомендую оптимизировать ваш код как можно больше и использовать Psyco, чтобы выжать как можно больше скорости.

В части их руководства конкретно говорится об использовании его для ускорения сложных, сложных и числовых вычислений тяжелых функций.

http://psyco.sourceforge.net/psycoguide/node8.html

Ответ 7

Я тоже новичок. Мой код структурирован так же, как и его.

for A in biglist:
    for B in biglist:
        if ( A.get('somekey') <> B.get('somekey') and #don't match to itself
             len( set(A.get('list')) - set(B.get('list')) ) > 10:
            [do stuff...]

Это занимает несколько часов, чтобы просмотреть список из 10000 словарей. Каждый словарь содержит много материалов, но я могу потенциально вытащить только идентификаторы ( "somekey" ) и списки ( "список" ) и переписать как один словарь из пар ключей 10000: 100.

Вопрос: насколько быстрее это будет? И я предполагаю, что это быстрее, чем использование списка списков, правильно?