迭代列表和更新字典以改进相应的匹配逻辑

Question

我有两份清单：

1. 用户-[<UserObject1>，<UserObject2>，…]
2. 贡献-[<ContributionObject1>，<ContributionObject2>，…]

每个ContributionObject中还可以有一个或多个UserObject，这里称之为person_links，并且ContributionObject和UserObject这两个对象都有特定的方法和属性

UserObject有一个属性affiliation

我必须检查来自用户的UserObject是否与来自贡献的ContributionObject之一的affiliation具有相同的UserObject

如果是，我必须制作一个字典，其中key将是来自用户的user，而value将是一个ceratin ContributionObject属性数组，即title和url

我可以用下面的逻辑来做

我想问这个逻辑是否可以进一步改进

如果有其他有效的方法来完成这项任务，一定要提到这一点。谢谢你的帮助。：）

conflicts = dict()
for user in users:
    if user.affiliation:
        for contribution in contributions:
            if not conflicts.get(user):
                conflicts[user] = [
                    (
                        contribution.title,
                        contribution.url,
                    )
                    for person in contribution.person_links
                    if user.affiliation in person.affiliation
                ]
            else:
                conflicts[user] += [
                    (
                        contribution.title,
                        contribution.url,
                    )
                    for person in contribution.person_links
                    if user.affiliation in person.affiliation
                ]

我试图找到更好的方法来更新上的dict值，但它们主要是更新现有值（覆盖），而不是添加（附加）到现有值

Answer 1

在发表了一些评论之后，我稍微改进了逻辑

以下是改进后的逻辑：

conflicts = defaultdict(list)
for user in users:
    if not user.affiliation:
        continue
    for contribution in self.contributions:
        conflicts[user].extend(
            (
                contribution.title,
                contribution.url
            )
            for person in contribution.person_links
            if user.affiliation in person.affiliation)
return conflicts

Answer 2

通过首先创建包含所需信息的从属关系索引，可以避免查看每个用户的贡献列表

from collections import defaultdict
affiliationIndex = defaultdict(list)
for contrib in contributions:
    for person in contrib.person_links:
        affiliationIndex[person.affiliation].append((contrib.title,contrib.url))
conflicts = { u:affiliationIndex[u.affiliation] for u in users if u.affiliation}

这使用字典存储每个附属机构的列表贡献信息。完成后，您将从每个用户的附属机构直接访问贡献信息

由此产生的性能将是O（U+C），而不是O（UxC）

[编辑]复杂性

大的“O”符号表示程序的处理模式，表示当输入变大时，它在时间或空间测量中产生的曲线类型。线性复杂度O（n）将具有一阶模式，其中时间是输入大小的倍数。随着输入大小（n）的增大，程序使用的时间或空间将增加（n）倍。如果您正在为每个同样具有O（n）复杂度的输入元素执行一个操作，那么yo将获得O（n^2）复杂度。例如，为数字1到n构建乘法表将具有O（n^2）复杂性，因为对于每个数字，您将执行n次乘法。因此，如果n=10，则执行100次乘法，如果n=15，则执行225次，如果n=25>；625，等等

在原始伪代码中，您正在遍历用户列表中每个用户的贡献列表。因此，如果您有U个用户具有从属关系和C贡献，贡献循环中的代码将被称为UxC次（因此O（UxC）复杂度）

另一方面，如果您使用字典来构建从属关系索引，您将执行单次传递贡献：O（C），然后执行单次传递用户O（U）。这将简单地将两个进程相加，而不是将一个进程乘以另一个进程，因此O（U+C）

例如，如果您有100个用户和250个贡献，那么内部循环中的代码块将被调用25000次。使用字典，您将在100个用户上循环一次，在250个贡献上循环一次，从而执行350个代码块。使用字典的优点是，它允许直接访问数据而无需循环（即在O（1）时间内）

请注意，我故意忽略了每个贡献的平均人数，因为这两种方法都会导致通过person\u链接循环的成本。从技术上讲，这使得解决方案分别为O（UxCxP）和O（CxP+U）（其中P是person\U链接中的平均条目数）