python - 在两个列表之间有效地找到 "duplicates"，其中字典元素只比较字典字段的一个子集

Question

是什么让我的问题与众不同...

...来自 StackOverflow 上的类似文章。在MWE下面，dict 有 4 个字段；但其中只有 2 个与比较相关。

问题...

...很简单，我总是在下面的 MWE 中提供解决方案，但我想知道是否有更有效的 pythonic 方式来处理这个问题——在CPU 时间的含义。

两个带有 dict() 元素的 list() 需要检查“重复项”。 duplicate 定义为字段 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 生成包含 100 个随机元素的列表 data。第二个列表 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 个字段。
• 列表 有 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'}

---

编辑:

在set((d['title'], tuple(d['date'])) for d in dupli)我必须首先从 d['date'] 创建元组，因为原始类型是列表(不可散列)，我无法添加列表来设置。

更好的是存储d['date']最初作为元组(跳过这个转换步骤并加快速度):

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