python - 如何根据2个键删除重复的字典？

Question

我想删除基于 2 个键的重复字典。有没有更快的方法来做到这一点？

到目前为止我已经尝试过了。

def remove_duplicates(documents):
    unique_documents = [documents[0]]  # Initialize first dict
    for document in documents:
        for index, unique_document in enumerate(unique_documents):
            if unique_document['user'] == document['user']:
                if unique_document['text'] == document['text']:
                    # If the user and text are found, then it's a duplicate.
                    # Go to next document.
                    break
                if index == len(unique_documents)-1:
                    # If it reaches the last dict of the unique_documents,
                    # append to list because the dict is unique
                    unique_documents.append(document)

    return unique_documents

字典列表中每个字典有 7 个键，使用上面的代码和测试数据 99942 文档 需要 1457.94099998s或24分钟处理。有没有更有效的方法来做到这一点？

Answer 1

在最坏的情况下，您的方法需要 O(N**2) 时间(所有文档都是唯一的，您循环遍历每个测试文档的所有唯一文档)。

使用单独的集合来跟踪您已经见过的用户文本元组，这样您就可以将其简化为 O(N) 算法，而与唯一文档的数量无关。集合允许您在 O(1) 时间内测试对象是否存在，从而无需嵌套循环:

def remove_duplicates(documents):
    unique_documents = []
    seen = set()
    for document in documents:
        if (document['user'], document['text']) in seen:
            continue
        unique_documents.append(document)
        seen.add((document['user'], document['text']))

    return unique_documents