Как быстро сравнить огромные списки словарей?

Question

[xgyrfalconx]

Допустим у нас есть два списка словарей:
a = [{'column1': 'Россия','column2':'Москва', 'column3': '01.02.2019'}, {'column1': 'Россия','column2':'Мурманск', 'column3': '01.02.2018'}...]
b = [{'column1': 'Россия','column2':'Москва', 'column3': '01.02.2019'}, {'column1': 'Россия','column2':'Мурманск', 'column3': '01.02.2018'}...]

Количество словарей в списках около 190000.
Ключи словарей одинаковые в обоих списках и остаются без изменений , но значения могут изменяться как в словаре a, так и в словаре b. Нужно найти отличия словаря а от б и наоборот. Я использую такое сравнение:

no_in_b = []
        no_in_a = []
        for i in a:
            if i not in b:
                no_in_b.append(i)
            else:
                pass

        for i in b:
            if i not in a:
                no_in_a.append(i)
            else:
                pass

Но выполнение такого рода сравнения занимает около часа , есть ли возможность сравнивать списки словарей быстрее ?

Comments

[ScriptKiddo]

Если хотите без доработок - попробуйте PyPy https://www.pypy.org/

[xgyrfalconx]

Благодарю за комментарий, к сожалению такой возможности нет.

[Viktor T2]

DeepDiff
https://pypi.org/project/deepdiff/

from deepdiff import DeepDiff 

ddiff = DeepDiff(a, b, ignore_order=True)
print(ddiff)

Answer 1

[ScriptKiddo]

from collections import defaultdict

a = [{'a': '1', 'b': '2'},
     {'a': '1', 'b': '2'},
     {'a': '5', 'b': '7'}]
b = [{'a': '3', 'b': '4'},
     {'a': '1', 'b': '2'}]


def make_hash_table(list_of_dicts):
    hashes = defaultdict(list)

    for i, item in enumerate(list_of_dicts):
        calculated_hash = hash(frozenset(item.items()))
        hashes[calculated_hash].append(i)

    return hashes


# Считаем хеши
a_hashes = make_hash_table(a)

b_hashes = make_hash_table(b)

# Определяем через вычитание множеств каких хешей у нас нет

not_in_a = [b[b_hashes[hash_value][0]] for hash_value in b_hashes.keys() - a_hashes.keys()]

not_in_b = [a[a_hashes[hash_value][0]] for hash_value in a_hashes.keys() - b_hashes.keys()]

print('Not in a \n')
print(not_in_a)
print()
print('Not in b \n')
print(not_in_b)

OUT

Not in a 

[{'a': '3', 'b': '4'}]

Not in b 

[{'a': '5', 'b': '7'}]

Answer 2

[Alexandroppolus]

Отсортировать оба массива, сравнивая по column1, column2, column3
(функция сравнения сначала сравнивает строки из column1, при их равенстве - column2, и т.д.)
дальше можно будет за линейное время сделать сравнение, обходя параллельно оба массива.

Answer 3

[Михаил Кростелев]

Я бы вам посоветовал для таких вещей использовать Pandas.
Создавайте 2 Датафрейма, и после используйте merge
Подробности всех действий можно узнать в гугле.