<p>通过首先创建包含所需信息的从属关系索引,可以避免查看每个用户的贡献列表</p>
<pre><code>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}
</code></pre>
<p>这使用字典存储每个附属机构的列表贡献信息。完成后,您将从每个用户的附属机构直接访问贡献信息</p>
<p>由此产生的性能将是O(U+C),而不是O(UxC)</p>
<p>[编辑]复杂性</p>
<p>大的“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,等等</p>
<p>在原始伪代码中,您正在遍历用户列表中每个用户的贡献列表。因此,如果您有U个用户具有从属关系和C贡献,贡献循环中的代码将被称为UxC次(因此O(UxC)复杂度)</p>
<p>另一方面,如果您使用字典来构建从属关系索引,您将执行单次传递贡献:O(C),然后执行单次传递用户O(U)。这将简单地将两个进程相加,而不是将一个进程乘以另一个进程,因此O(U+C)</p>
<p>例如,如果您有100个用户和250个贡献,那么内部循环中的代码块将被调用25000次。使用字典,您将在100个用户上循环一次,在250个贡献上循环一次,从而执行350个代码块。使用字典的优点是,它允许直接访问数据而无需循环(即在O(1)时间内)</p>
<p>请注意,我故意忽略了每个贡献的平均人数,因为这两种方法都会导致通过person\u链接循环的成本。从技术上讲,这使得解决方案分别为O(UxCxP)和O(CxP+U)(其中P是person\U链接中的平均条目数)</p>