如何提高以下代码的性能?
self.adverts = set() # Around 11k rows
self.old_adverts= set() # Around 11k rows
self.advs = []
...
# Find modified items
for item in self.new_items:
for old_item in self.old_items:
if item.id == old_item.id and item.price != old_item.price:
self.advs.append(
{
'delete': old_item,
'new': item,
'archive': old_item
}
)
Item
班级:
class Item(Base):
...
id = Column(String(25), nullable=False, primary_key=True)
price = Column(Numeric(precision=8), nullable=False, primary_key=True)
# Another multiple additional fields
...
def __eq__(self, other):
return self.id == other.id
def __hash__(self):
return hash(self.id)
以上数据比较耗时太多。我不知道如何禁食。
UPD:但是,下面我设法提高了另一段代码的性能:
# for item in self.items:
# if item not in self.old_items:
# self.insert_items_db.add({'new': item})
# Find absolutely new items
for new_item in self.items- self.old_items:
self.advs.append({'new': new_item})
对象具有预定义__eq__
和__hash__
功能:
def __eq__(self, other):
return self.id == other.id
def __hash__(self):
return hash(self.id)
我没有完全遵循您的代码,但您可以使用字典加快比较两个列表的速度。这是 O(n) 而不是 O(n^2),因为检查存在性从 O(n) 减少到 O(1)。
例如。假设您有一堆带有变量 id、value、color 的对象。
for x in list1: #N operations
for y in list2: #N operations
if x.id == y.id: #O(1)
#do stuff
相反,你可以这样做:
#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}
你的代码现在变成:
for x in dict1.keys(): #O(N)
if x in dict2: #O(1)
#Do some stuff
现在是 O(n) 时间。
现在如果你想比较价格就变得很棘手了。如果我们有多个 Id 元素(例如在同一个集合中有冲突),那么我们可以将字典中的每个条目转换为对象列表。这理论上仍然是 O(N^2) 操作,但与遍历所有 11k 元素相比,这是一个巨大的改进。
让我们假设没有重复的 ID。然后代码变成:
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
如果有重复的 Id,则字典结构应如下所示:
my_dict = {\
1001: [ obj1, obj2, obj3]\ #where obj1.id == obj2.id == obj3.id
1002: [obj4, obj5, obj6]\ #where obj4.id == obj5.id == obj6.id
}
代码经过调整以反映以下内容
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!
这里是最疯狂的部分!
在上面的代码中,我添加了另一个 for 循环。这又是 O(N) 的速度,这就是代码再次减少到 O(N^2) 的原因。但是,如果我们有另一个标识符,比如“Id2”或“color_of_left_toe”,那么我们可以创建另一个字典!!
此时,该结构将演变为对象的字典字典。相当复杂但是!!访问时间可以保持 O(1)!
在第一个代码示例中,您遍历第一个列表,然后再次遍历另一个列表。
因此,对于 list1 中的第一个元素,您可以遍历 len(list2) 或N
因为您正在为 X 中的每个元素循环此循环,所以您将执行N次。
N+N+N+N…………N
\~~~~~~ N次~~~~~~/
或 O(N^2)
现在为什么 dict 更快?
字典对每个元素进行散列,然后根据此散列存储它。这意味着您无需查看复杂的二叉树或数组即可找到您要查找的内容。相反,您进行了一些 O(1) 时间数学运算,并且根据您提供的密钥,您需要立即检查这一点。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句