Как эффективно сравнить список строк в словарях с другим списком словарей в Python?

Question

Я хотел бы сравнить список строк в словарях с другим списком словарей в Python. Если href в secondary_list недоступно в main_list, href будет добавлено в main_list.

На основании этого требования был реализован приведенный ниже код.

main_list = [
    {'href': 'red'},
    {'href': 'yellow'},
    {'href': 'yellow'},
]

secondary_list = [
    {'href': 'yellow'},
    {'href': 'redf'},
    {'href': 'blue'},
]
for g in secondary_list:

    if not any(d.get('href', None) == g["href"] for d in main_list):
        main_list.append({'href': g["href"]})

Но, скажем, если у нас очень большой список в обоих словарях, реализация, использующая два цикла for, может быть неэффективной.

Могу ли я узнать, можно ли сделать приведенный выше код более эффективным и уплотнить? Еще лучше, если существует пакет, о котором я не знаю?

Answer 1

Вы можете сделать следующее, O(n) сложность:

main_set = {frozenset(g.items()) for g in main_list}
secondary_set = {frozenset(g.items()) for g in secondary_list}

main_list.extend(dict(g) for g in secondary_set - main_set)
print(main_list)

Вывод

[{'href': 'red'}, {'href': 'yellow'}, {'href': 'yellow'}, {'href': 'blue'}, {'href': 'redf'}]

Идея заключается в создании наборов замороженных словарей frozenset(g.items()) найти разницу и преобразовать обратно в словари. Вы можете думать о frozenset как о хешируемом наборе .

В вашем случае, в частности, словари с одним ключом, где ключ одинаков для всех, вы можете сделать:

main_set = {v for d in main_list for v in d.values()}
secondary_set = {v for d in secondary_list for v in d.values()}

main_list.extend({"href": v} for v in (secondary_set - main_set))
print(main_list)