<p>我没有完全按照你的代码,但你可以通过使用字典来加速比较两个列表。这是O(n)而不是O(n^2),因为检查是否存在从O(n)减少到O(1)</p>
<p>例如。假设你有一堆带有变量id,value,color的对象</p>
<pre><code>for x in list1: #N operations
for y in list2: #N operations
if x.id == y.id: #O(1)
#do stuff
</code></pre>
<p>相反,你可以这样做:</p>
<pre><code>#create two dictionaries where each key is the ID and each value is the
#object, data, other things etc.
dict1 = { x.id:x for x in list1}
dict2 = { y.id:y for y in list2}
</code></pre>
<p>您的代码现在变成:</p>
<pre><code>for x in dict1.keys(): #O(N)
if x in dict2: #O(1)
#Do some stuff
</code></pre>
<p>现在是O(n)时间</p>
<p>现在如果你想比较一下价格,那就很棘手了。如果我们有多个Id元素<em>(例如,在同一个集合中存在冲突)</em>,那么我们可以将字典中的每个条目转换为对象列表。这在理论上仍然是O(N^2)操作,但它比遍历所有11k元素有很大的改进</p>
<p>假设没有重复的ID。然后代码变为:</p>
<pre><code>for x in dict1.keys(): #O(N)
if x in dict2: #O(1)
if dict1[x].price != dict2[x].price: #or any other comparison
#do stuff
</code></pre>
<p>如果存在重复的ID,则字典结构应如下所示:</p>
<pre><code>my_dict = {\
1001: [ obj1, obj2, obj3]\ #where obj1.id == obj2.id == obj3.id
1002: [obj4, obj5, obj6]\ #where obj4.id == obj5.id == obj6.id
}
</code></pre>
<p>对代码进行调整以反映以下内容</p>
<pre><code>for x in dict1.keys():
if x in dict2:
if x in dict2:
for my_object_type in dict2[x]: #something about this seems familiar.....
if x.other_identifier == my_object_type.other_identifer:
#finally do some stuff!
</code></pre>
<p>这是最疯狂的部分</p>
<p>在上面的代码中,我添加了另一个for循环。这又是O(N)速度,这就是为什么代码又减少到O(N^2)。但是,如果我们有另一个标识符,比如“Id2”或“color\u of \u left\u toe”,那么我们就可以创建另一个字典了</强></p>
<p>在这一点上,这个结构将演变成一个对象的字典字典。相当复杂,但是!!访问时间可以保持O(1)</p>
<h2>为什么“在dict中”更快</h2>
<p>在第一个代码示例中,您遍历第一个列表,然后再次遍历另一个列表</p>
<p>因此,对于list1中的第一个元素,您遍历len(list2),或者<strong>N</strong></p>
<p>因为对X中的每一个元素循环这个循环,所以做这个<strong>N次</p>
<p>N+N+N+N………N</p>
<p>\~~~~~~~<strong>N次</strong>~~~~~/</p>
<p>或O(N^2)</p>
<p>为什么dict更快</p>
<p>字典对每个元素进行散列,然后基于此散列存储它。这意味着您不必通过复杂的二叉树或数组来查找所要查找的内容。相反,你做了一点O(1)时间的数学,你有点你需要检查的基础上,你给它的关键马上</p>