比较命名元组列表中的几个（但不是全部）元素

Question

我有一个可以很长的命名元组列表（目前它可以达到 10.000 行，但将来可能会更多）。

我需要将每个命名元组的几个元素与列表中的所有其他命名元组进行比较。我正在寻找一种高效且通用的方法来做到这一点。

为简单起见，我将用蛋糕做类比，这样应该更容易理解问题。

有一个命名元组列表，其中每个命名元组都是一个蛋糕：

Cake = namedtuple('Cake', 
                       ['cake_id',
                        'ingredient1', 'ingredient2', 'ingredient3',
                        'baking_time', 'cake_price']
                 )

cake_price和baking_time都很重要。如果蛋糕的成分相同，我想从列表中删除不相关的那些。因此，任何同等或更昂贵且烘烤时间相同或更长的蛋糕（具有相同的成分）都是不相关的（下面有一个详细的例子）。

最好的方法是什么？

方法

到目前为止我所做的是按 cake_price 和 baking_time:

对 named_tuples 的列表进行排序

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是最便宜的（也是同价位中最快的）--> IN
cake_2 与 cake1 价格相同，烘烤时间更长 --> OUT
cake_3是另一种蛋糕 --> IN
cake_4 比 cake_1 贵，但烘烤速度更快 --> IN
cake_5 比 cake_1 和 cake_4 贵，但烘烤速度更快 --> IN

Answer 1

你的运行接近时间将大致与

成正比

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)

这样做是检查 new 蛋糕与 cakes 副本中每个蛋糕 c 的对比，然后：

如果它的烘烤时间和价格都大于或等于现有蛋糕，立即退出（你可以return而不是breaking，但我更喜欢明确控制流程）。
如果它的烘焙时间和价格都小于或等于现有蛋糕，则从集群中移除该现有蛋糕
如果它超过了所有现有的蛋糕（因此达到了 for 语句的 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)

我用一系列随机蛋糕做了一些测试，每个蛋糕都使用了你的五种不同成分和随机价格和烘焙时间的选择，并且

这种方法始终产生与您的方法相同的结果（尽管未排序）
它运行得相当快——在我的机器上 0.2 秒可以随机生成 100,000 个蛋糕，而你的大约需要 3 秒。

Answer 2

未经测试的代码，但应该有助于指出更好的方法：

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)]

比较命名元组列表中的几个（但不是全部）元素

Compare several (but not all) elements in a list of namedtuples

python

list

namedtuple

python-3.x

方法

示例：