python - 比较命名元组列表中的多个(但不是全部)元素

Question

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

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

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

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

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

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)

它的作用是对照 cakes 副本中的每个 cake c 检查 new 蛋糕，然后:

1. 如果它的烘焙时间和价格都大于或等于现有蛋糕，请立即退出(您可以返回而不是打破，但我更喜欢明确控制流)。

2. 如果其烘焙时间和价格均小于或等于现有蛋糕，则从集群中删除该现有蛋糕

3. 如果它越过所有现有的蛋糕(因此到达 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)

我对随机蛋糕列表做了一些测试，每个蛋糕都使用从五种不同成分中选择的内容以及随机价格和烘焙时间，并且

1. 此方法始终会产生与您的结果相同的结果(尽管未排序)

2. 它的运行速度要快得多 - 在我的机器上运行 100,000 个随机蛋糕只需 0.2 秒，而您的机器上运行大约 3 秒。