Python: 如何有效地将 4 个字典列表嵌套到一个列表中？

Question

我有一个 MSSQL 存储过程，其中 returns 4 个选项给我：Entities、Certificates、Contacts 和 Logs .我需要在 Pyton 中组合这 4 个选择，我将所有 Entities、Contacts 和 Logs 放在它们的 Certificate 下。这些选择中的每一个都有一个 EntityId 我可以用于合并。

输入是简单的基本数据类列表，其中包含来自 SQL 的信息。我们在合并函数中将这些数据类转换为字典。

当我最初编写代码时，我不知道选择会非常大（Certificates 的 100.000 条以及所有其他记录）。不幸的是，由于循环内列表理解的许多不必要的迭代，这使得下面的代码非常低效。最多可能需要 70 秒。我相信有一种方法可以使它更快。如何提高性能以尽可能高效？

from dataclasses import asdict

def cert_and_details(entities: List[Entity], 
                    certificates: List[Certificate], 
                    req_logs: List[DocumentRequestHistory], 
                    recipients: List[Recipient]) -> List[dict]:

    entities = [asdict(ent) for ent in entities] 
    certificates = [asdict(cert) for cert in certificates]
    req_logs = [asdict(log) for log in req_logs]
    recipients = [asdict(rec) for rec in recipients]

    results = []
    for cert_dict in certificates:

        cert_entity_id = cert_dict["entityid"]

        logs_under_cert = [log for log in req_logs if log["entityid"] == cert_entity_id]
        cert_dict["logs"] = logs_under_cert

        entities_under_cert = [ent for ent in entities if ent["entityid"] == cert_entity_id]
        cert_dict["linkedentity"] = entities_under_cert

        recipients_under_cert = [rec for rec in recipients if rec["entityid"] == cert_entity_id]
        cert_dict["recipients"] = recipients_under_cert

        results.append(cert_dict)

    return results

Answer 1

所提供代码的主要问题是其 计算复杂性：它在 O(C * (L + E + R)) 中运行，其中 C 是证书数量，L 日志数，E 实体数和 R 收件人数。如果 L+E+R 很小，这很好，但如果不是这样，那么代码会很慢。

您可以在 O(C + L + E + R) 时间内编写一个实现运行。这个想法是先建立一个索引，按实体ID 分组logs/entities/recipients。这是一个简短的例子：

# Note: defaultdict should help to make this code smaller (and possibly faster) logIndex = dict() for log in req_logs: entityId = log["entityid"] if entityId in logIndex: logIndex[entityId].append(log) else: logIndex[entityId] = [log]

此代码在（摊销）O(L) 中运行。然后，您可以仅使用 logIndex[entityId].
检索具有给定实体 ID 的 req_log 中的所有项目
提供的代码中还有另一个问题：字典列表效率低下：字典索引很慢，而且字典的内存效率也不高。一种更好的存储和计算数据的方法可能是使用 dataframes（例如 Pandas，它也提供相对优化的 groupby 函数).

Answer 2

下面也可能是另一种计算复杂度顺序的方法(2*C+L+E+R)。

警告：我还没有尝试运行这个，它只是模型代码，并没有试图尽可能高效。我也只是模拟了它，从概念上思考如何让它变得线性复杂，它可能有一些我错过的基本 'Ooops'。

但它基于仅循环遍历每个 C、L、E 和 R 一次的概念。这是通过首先使 certificates 成为字典而不是列表来完成的。关键是entityid。存储每个证书日志、实体和收件人的列表也在那个时候创建。

然后你可以只循环遍历 L、E 和 R 一次，并通过查找 entityid 直接将它们的条目添加到证书字典中。

最后一步（所以为什么 2*C 复杂）将通过证书字典循环并将其转换为列表以匹配所需的输出类型。

from dataclasses import asdict

def cert_and_details(entities: List[Entity], 
                    certificates: List[Certificate], 
                    req_logs: List[DocumentRequestHistory], 
                    recipients: List[Recipient]) -> List[dict]:

    certs = {}

    for cert in certificates:
        cert_dict = asdict(cert)
        cert_id = cert_dict['entityid']

        certs[cert_id] = cert_dict
        certs['logs'] = []
        certs['recipients'] = []
        certs['linkedentity'] = []

    for log in logs:
        log_dict = asdict(log)
        log_id = log_dict['entityid']
        certs[log_id]['logs'].append(log_dict)


    for ent in entities:
        ent_dict = asdict(ent)
        ent_id = ent_dict['entityid']
        certs[ent_id]['linkedentity'].append(ent_dict)

    for rec in recipients:
        rec_dict = asdict(rec)
        rec_id = rec_dict['entityid']
        certs[rec_id]['recipients'].append(rec_dict)

    # turn certs back into list, not dictionary
    certs = [cert for cert in certs.values()]

    return certs

Python: 如何有效地将 4 个字典列表嵌套到一个列表中？

Python: How do I efficiently nest 4 list of dictionaries into one?

python

rest

performance

record

python-dataclasses