我有一个命名元组列表，它可能很长(目前可以达到10000行，但将来可能会更多)。
我需要将每个命名元组的几个元素与列表中的所有其他命名元组进行比较。我正在寻找一种高效和通用的方法来做到这一点。
为了简单起见，我将用蛋糕做一个类比，这应该会让理解这个问题更容易。
有一个命名的元组列表，其中每个命名的元组都是一个蛋糕：
Cake = namedtuple('Cake',
['cake_id',
'ingredient1', 'ingredient2', 'ingredient3',
'baking_time', 'cake_price']
)
CCD_ 1和CCD_。如果蛋糕的成分相同，我想把那些不相关的从列表中删除。因此，任何相同或更贵、烘焙时间相同或更长的蛋糕(成分相同)都是不相关的(下面有一个详细的例子)。
最好的方法是什么？
方法
到目前为止，我所做的是按照cake_price和baking_time:对命名元组列表进行排序
sorted_cakes = sorted(list_of_cakes, key=lambda c: (c.cake_price, c.baking_time))
然后创建一个新的列表，我将添加所有蛋糕，只要之前添加的蛋糕没有相同的成分，烘焙起来更便宜、更快。
list_of_good_cakes = []
for cake in sorted_cakes:
if interesting_cake(cake, list_of_good_cakes):
list_of_good_cakes.append(cake)
def interesting_cake(current_cake, list_of_good_cakes):
is_interesting = True
if list_of_good_cakes: #first cake to be directly appended
for included_cake in list_of_good_cakes:
if (current_cake.ingredient1 == included_cake.ingredient1 and
current_cake.ingredient2 == included_cake.ingredient2 and
current_cake.ingredient3 == included_cake.ingredient3 and
current_cake.baking_time >= included_cake.baking_time):
if current_cake.cake_price >= included_cake.cake_price:
is_interesting = False
return is_interesting
(我知道嵌套循环远非最佳，但我想不出其他方法…)
示例：
具有
list_of_cakes = [cake_1, cake_2, cake_3, cake_4, cake_5]
其中
cake_1 = Cake('cake_id'=1,
'ingredient1'='dark chocolate',
'ingredient2'='cookies',
'ingredient3'='strawberries',
'baking_time'=60, 'cake_price'=20)
cake_2 = Cake('cake_id'=2,
'ingredient1'='dark chocolate',
'ingredient2'='cookies',
'ingredient3'='strawberries',
'baking_time'=80, 'cake_price'=20)
cake_3 = Cake('cake_id'=3,
'ingredient1'='white chocolate',
'ingredient2'='bananas',
'ingredient3'='strawberries',
'baking_time'=150, 'cake_price'=100)
cake_4 = Cake('cake_id'=4,
'ingredient1'='dark chocolate',
'ingredient2'='cookies',
'ingredient3'='strawberries',
'baking_time'=40, 'cake_price'=30)
cake_5 = Cake('cake_id'=5,
'ingredient1'='dark chocolate',
'ingredient2'='cookies',
'ingredient3'='strawberries',
'baking_time'=10, 'cake_price'=80)
预期结果是：
list_of_relevant_cakes = [cake_1, cake_3, cake_4, cake_5]
- cake_1是最便宜的(也是同价位中最快的)-->在
- cake_2的价格与cake1的价格相同，烘焙时间更长-->OUT
- cake_3是一种不同的蛋糕-->在
- cake_4比cake_1贵，但烘焙速度更快-->在
- cake_5比cake_1和cake_4更贵，但烘焙速度更快-->在
方法的运行时间将与大致成比例
len(list_of_cakes) * len(list_of_relevant_cakes)
如果你有很多蛋糕，而且其中很多都是相关的，那么它可能会变得很大。
我们可以利用这样一个事实来改进这一点，即每一簇具有相同成分的蛋糕都可能小得多。首先，我们需要一个函数来检查新蛋糕与现有的、已经优化的具有相同成分的集群：
from copy import copy
def update_cluster(cakes, new):
for c in copy(cakes):
if c.baking_time <= new.baking_time and c.cake_price <= new.cake_price:
break
elif c.baking_time >= new.baking_time and c.cake_price >= new.cake_price:
cakes.discard(c)
else:
cakes.add(new)
这样做的目的是对照cakes副本中的每个饼c检查new饼，然后：
如果它的烘焙时间和价格都大于或等于现有蛋糕，请立即退出(您可以使用
return而不是breaking，但我更喜欢明确控制流)。如果其烘焙时间和价格都小于或等于现有蛋糕，则从集群中删除该现有蛋糕
如果它通过了所有现有的蛋糕(因此到达了
cake_price0语句的else子句)，则将其添加到集群中。
一旦我们有了它，我们就可以用它来过滤蛋糕：
def select_from(cakes):
clusters = {}
for cake in cakes:
key = cake.ingredient1, cake.ingredient2, cake.ingredient3
if key in clusters:
update_cluster(clusters[key], cake)
else:
clusters[key] = {cake}
return [c for v in clusters.values() for c in v]
它在这里发挥作用：
>>> select_from(list_of_cakes)
[Cake(cake_id=1, ingredient1='dark chocolate', ingredient2='cookies', ingredient3='strawberries', baking_time=60, cake_price=20),
Cake(cake_id=4, ingredient1='dark chocolate', ingredient2='cookies', ingredient3='strawberries', baking_time=40, cake_price=30),
Cake(cake_id=5, ingredient1='dark chocolate', ingredient2='cookies', ingredient3='strawberries', baking_time=10, cake_price=80),
Cake(cake_id=3, ingredient1='white chocolate', ingredient2='bananas', ingredient3='strawberries', baking_time=150, cake_price=100)]
该解决方案的运行时间与大致成比例
len(list_of_cakes) * len(typical_cluster_size)
我用一份随机蛋糕清单做了一个小测试，每个蛋糕都使用从五种不同成分中选择的，随机价格和烘焙时间，以及
这种方法始终产生与您的相同的结果(尽管未排序)
它的运行速度要快得多——在我的机器上，100000个随机蛋糕的运行速度为0.2秒，而你的大约为3秒。
未测试的代码，但应该有助于指出更好的方法：
equivalence_fields = operator.attrgetter('ingredient1', 'ingredient2', 'ingrediant3')
relevant_fields = operator.attrgetter('baking_time', 'cake_price')
def irrelevent(cake1, cake2):
"""cake1 is irrelevant if it is both
more expensive and takes longer to bake.
"""
return cake1.cake_price > cake2.cake_price and cake1.baking_time > cake2.bake_time
# Group equivalent cakes together
equivalent_cakes = collections.defaultdict(list)
for cake in cakes:
feature = equivalence_fields(cake)
equivalent_cakes[feature].append(cake)
# Weed-out irrelevant cakes within an equivalence class
for feature, group equivalent_cakes.items():
best = min(group, key=relevant_fields)
group[:] = [cake for cake in group if not irrelevant(cake, best)]