Сравните несколько (но не все) элементов в списке namedtuples

Question

У меня есть список именованных вершин, которые могут быть довольно длинными (на данный момент он может достигать 10.000 строк, но в будущем это может быть намного больше).

Мне нужно сравнить несколько элементов каждого namedtuple со всеми другими namedtuples из списка. Я ищу эффективный и общий способ для этого.

Для простоты я сделаю аналогию с пирожными, что должно облегчить понимание проблемы.

Имея список namedtuples, где каждый namedtuple является торт:

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

cake_price Оба и baking_time имеют важное значение. Если торты имеют одни и те же ингредиенты, я хочу удалить из списка те, которые не имеют отношения к делу. Таким образом, любой пирог (с теми же ингредиентами), который является равным или более дорогим и принимает такое же или более длительное время для выпекания, не имеет значения (ниже приведен подробный пример).

Какой был бы лучший способ сделать это?

---

подход

То, что я сделал до сих пор является для сортировки списка named_tuples по 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, но еще быстрее испечь -> в

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 торт на каждый торт c в копию cakes, а затем:

1. Если его время выпечки и цена как больше или равна существующей торте, немедленно выйти (вы могли бы return, а не break ИНГ, но я предпочитаю, чтобы быть явными о потоке управления).

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) 

Я сделал немного tes тин со списком случайных пирожных, каждый из которых использует выбор из ваших пяти различных ингредиентов и случайные цены и времени выпечки, и

1. Этот подход последовательно производит те же результаты, как ваша (пусть несортированный)

2. Он работает значительно быстрее - 0,2 секунды на моей машине для 100 000 случайных тортов, по сравнению с примерно тремя секундами для вас.

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