Эффективно находите «дубликаты» между двумя списками с помощью элементов dict, сравнивая только подмножество полей dict

Question

Чем мой вопрос отличается ...

... от аналогичных здесь, в StackOverflow. В MWE ниже dict имеет 4 поля; но только 2 из них актуальны для сравнения.

Проблема ...

... проста, и я всегда предлагаю решение в моем MWE ниже, но я хотел бы знать , если есть более эффективный c способ pythoni для обработки этого - эффективный в смысле времени процессора.

Два list() с элементами dict() должны быть проверены для «дубликатов». дубликат определяется как если бы поля title и date равны. Содержимое других полей (flag и misc) значения не имеет. Чтобы добавить еще один фактор: элементы dict могут иметь разное количество полей, но title и date присутствуют всегда.

Мое решение

Я просто перевожу свои человеческие слова на python слов (dupli и data - два списка):

for d in dupli[:]:
    for e in data:
        # compare by 'title' and 'date'
        if e['title'] == d['title'] and e['date'] == d['date']:
            print('Duplicate found: {}'.format(d))
            # remove duplicates
            dupli.remove(d)

Мой полный MWE

Этот MWE генерирует список data со 100 случайными элементами. Второй список dupli имеет 10 элементов, 3 из которых имеют «дубликаты» (title и date, НО НЕ misc или flag) в первом списке.

#!/usr/bin/env python3
import random
import string


# helper function
def random_string(n):
    return ''.join([random.choice(string.ascii_letters) for i in range(n)])


# Create persistent data
def create_data(n):
    container = []
    for idx in range(n):
        # create an element with title, date and some misc data
        element = {
           'title': random_string(random.randrange(35)),
           'date': [2020, 5, random.randint(1, 30)],
           'flag': (random.random() < 0.5),  # bool
           'misc': random_string(random.randrange(5)),
        }

        container.append(element)
    return container


# persistent data
data = create_data(100)

# new data elements with possible duplicates
dupli = create_data(10)

# generate 3 duplicates
for idx in [2, 5, 8]:
    dupli[idx]['title'] = data[idx*10]['title']
    dupli[idx]['date'] = data[idx*10]['date']

# MY APPROACH to check for duplicates
for d in dupli[:]:
    for e in data:
        # compare by 'title' and 'date'
        if e['title'] == d['title'] and e['date'] == d['date']:
            print('Duplicate found: {}'.format(d))
            # remove duplicates
            dupli.remove(d)

# add the rest to persistent data
data.extend(dupli)

Справочная информация

Это только MWE. Данные реального мира более сложны. Поэтому для меня важна эффективность. Следующие числа, конечно, зависят от моих пользователей, но просто для того, чтобы дать вам представление:

• Элемент dict имеет от 4 до 12 полей.
• A list имеет 200 до 20 000 элементов.
• В моем приложении от 30 до 300 списков.
• С другой стороны для каждого списка есть список с новыми элементами: от 10 до 40 элементов.

Answer 1

Надеюсь, я понял ваш вопрос. Вы можете сначала подготовить set() с кортежами (<title>, <date>), а затем просто проверить, есть ли элемент из списка data в этом наборе - это будет O (n) .

Для пример:

elems = set((d['title'], tuple(d['date'])) for d in dupli)
for e in data:
    if (e['title'], tuple(e['date'])) in elems:
        print('Duplicate found: {}'.format(e))

Выводит:

Duplicate found: {'title': 'ENhIdksxeNKqCgbbg', 'date': [2020, 5, 5], 'flag': True, 'misc': ''}
Duplicate found: {'title': 'MRyXAmfJjSNjrXYTNpPRQFP', 'date': [2020, 5, 3], 'flag': True, 'misc': 'oTmr'}
Duplicate found: {'title': 'IyeSazUnquqTwYXGnTjHelFGr', 'date': [2020, 5, 12], 'flag': True, 'misc': 'CdhG'}

---

EDIT:

В set((d['title'], tuple(d['date'])) for d in dupli) Сначала я должен создать кортеж из d['date'], потому что исходный тип является списком (без хеширования), и я не могу добавить список для установки.

Лучше будет хранить d['date'] как кортеж изначально (чтобы пропустить этот шаг преобразования и ускорить работу):

'date': (2020, 5, random.randint(1, 30)),  # <-- tuple, not list