Q: Compare several (but not all) elements in a list of namedtuples I have a list of namedtuples that can be quite long (for the moment it can reach 10.000 rows but in the future it could be much more).
I need to compare several elements of each namedtuple with all other namedtuples from the list. I am looking for an efficient and generic way to do so.
For simplicity, I will make an analogy with cakes, that should make understanding the problem easier.
Having a list of namedtuples, where each namedtuple is a cake:
Cake = namedtuple('Cake', 
                       ['cake_id',
                        'ingredient1', 'ingredient2', 'ingredient3',
                        'baking_time', 'cake_price']
                 )

Both cake_price and baking_time are important. If the cakes have the same ingredients, I want to remove from the list the ones that are not relevant. So any cake (with the same ingredients) that is both equal or more expensive and takes same or longer to bake is not relevant (below there is a detailed example).
What would be the best way to do it?

Approach
What I have done so far is to sort the list of named_tuples by cake_price and baking_time:
sorted_cakes = sorted(list_of_cakes, key=lambda c: (c.cake_price, c.baking_time))

And then creating a new list where I am adding all cakes as long as no cake previously added has the same ingredients, is cheaper and faster to bake.
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

(I know that having a nested loop is far from optimal, but I cannot think of any other way to do it...)

Example:
Having
list_of_cakes = [cake_1, cake_2, cake_3, cake_4, cake_5]

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

The expected result would be:
list_of_relevant_cakes = [cake_1, cake_3, cake_4, cake_5]


*

*cake_1 is the cheapest (and the fastest among the same price) --> IN

*cake_2 has the same price as cake1 and takes longer to bake --> OUT

*cake_3 is a different kind of cake --> IN

*cake_4 is more expensive than cake_1, but faster to bake --> IN

*cake_5 is more expensive than cake_1 and cake_4, but even faster to bake --> IN


A: The running time of your approach is going to be roughly proportional to 
len(list_of_cakes) * len(list_of_relevant_cakes)

... which could get quite large, if you have a lot of cakes and a lot of them are relevant.
We can improve on this by taking advantage of the fact that each cluster of cakes with the same ingredients is likely to be much smaller. First of all, we need a function that checks a new cake against an existing, already optimized cluster with the same ingredients:
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)

What this does is check the new cake against each cake c in a copy of cakes, and then:


*

*If its baking time and price are both greater than or equal to an existing cake, immediately exit (you could return rather than breaking, but I prefer to be explicit about control flow).

*If its baking time and price are both less than or equal to an existing cake, remove that existing cake from the cluster

*If it makes it past all the existing cakes (and so reaches the for statement's else clause), add it to the cluster.
Once we have that, we can use it to filter the cakes:
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]

Here it is in action:
>>> 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)]

The running time of this solution is roughly proportional to
len(list_of_cakes) * len(typical_cluster_size)

I did a little testing with a list of random cakes, each using a selection from your five different ingredients and random prices and baking times, and 


*

*This approach consistently produces the same results as yours (albeit unsorted)

*It runs considerably faster – 0.2 seconds on my machine for 100,000 random cakes, compared to about three seconds for yours.

A: Untested code, but should help point to a better way:
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)]

