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

Question

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

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

С 'somevalue', обозначающим сгенерированную пользователем строку, int или decimal. Теперь второй список очень похож, за исключением того, что значения 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)

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

Полагаю, это не совсем то, как следует проводить такое сравнение. Есть идеи?

Answer 1

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

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)

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

Answer 2

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

1. Создать словарь сопоставлений кортежей других значений в первом словаре с их идентификатором.

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

3. Используйте словарь из пункта 1 для назначения идентификаторов этим кортежам.

Answer 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"

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

Answer 4

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

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') и списки ('list') и переписать в виде одного словаря из 10000 пар ключ: значение.

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

Answer 5

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

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

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

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

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

Answer 6

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

Оттуда решение кажется довольно очевидным: создайте два изначально пустых словаря: N и M (для без совпадений и совпадений .) Точно зацикливайтесь на каждом списке один раз, и для каждого из этих словарей, представляющих транзакцию (назовем это Tx_dict), создайте экземпляр нового класса (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 в N, но не в M, - вставить пару ключ-значение в M с текущим Tx_ptr в качестве ключа и в качестве значения, a список текущих Tx_ptr и Tx_ptr, который уже был в N.

Answer 7

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