Более эффективный цикл в Python

Question

У меня есть ситуация, когда мне нужно перебрать два списка объектов и найти равные, а затем перебрать их по полям и изменить некоторые атрибуты. Похож на это

for new_product in products_and_articles['products']: 
    for old_product in products_for_update: 
    if new_product.article == old_product.article: 
     for old_field in old_product._meta.get_all_field_names(): 
     for new_field in new_product._meta.get_all_field_names(): 
      if old_field == new_field and old_field != 'id' and old_field != 'slug': 
      setattr(old_product, old_field, getattr(new_product, old_field)) 

Очевидно, что это далеко не хорошее или даже приемлемое. Поэтому я ищу совет, как можно избежать так много зацикливания и повышения Algorythm

Answer 1

Это помогает, если вы разбиваете процесс на логические, повторно используемые части.

for new_product in products_and_articles['products']: 
    for old_product in products_for_update: 
    if new_product.article == old_product.article: 
     … 

Например, вот что вы делаете, это найти продукт, который соответствует конкретной article.Поскольку article уникален, мы могли бы написать что-то вроде этого:

def find_products_by_article(products, article): 
    '''Find all products that match the given article. Returns 
    either a product or 'None' if it doesn't exist.''' 
    for products in products: 
    return product 

Затем вызовите его:

for old_product in products_for_update: 
    new_products = find_products_by_article(
        products_and_articles['products'], 
        old_product.article) 
    … 

Но это может быть гораздо более эффективной, если мы могли бы воспользоваться структурой данных, оптимизирован для поиска, а именно: dict (постоянный вместо линейной сложности). Так что мы могли бы сделать вместо этого:

# build a dictionary that stores products indexed by article 
products_by_article = dict(product.article, product for product in 
          products_and_articles['products']) 

for old_product in products_for_update: 
    try: 
    # look up product in the dictionary 
    new_product = products_by_article[old_product.article] 
    except KeyError: 
    # silently ignore products that don't exist 
    continue 
    … 

Если вы делаете такие Lookups часто, было бы лучше, чтобы повторно использовать products_by_article словарь в другом месте, а вместо того, чтобы строить с нуля каждый раз. Будьте осторожны:: если вы используете несколько представлений записей продукта, вам нужно заставить их всегда оставаться в синхронизации!

Для внутренних петель, обратите внимание, что new_field здесь служит только в качестве проверки для того, существует поле:

… 
    for old_field in old_product._meta.get_all_field_names(): 
    for new_field in new_product._meta.get_all_field_names(): 
     if old_field == new_field and old_field != 'id' and old_field != 'slug': 
     setattr(old_product, old_field, getattr(new_product, old_field)) 

(Обратите внимание, что это немного подозрительно: новые поля, которые уже не существуют в old_product отбрасываются: это намеренное)

Это можно упаковать следующим образом:

def transfer_fields(old, new, exclusions=('id', 'slug')): 
    '''Update all pre-existing fields in the old record to have 
    the same values as the new record. The 'exclusions' parameter 
    can be used to exclude certain fields from being updated.''' 
    # use a set here for efficiency reasons 
    fields = frozenset(old._meta.get_all_field_names()) 
    fields.difference_update(new._meta.get_all_field_names()) 
    fields.difference_update(exclusions) 
    for field in fields: 
    setattr(old, field, getattr(new, field)) 

Собираем все это вместе:

# dictionary of products indexed by article 
products_by_article = dict(product.article, product for product in 
          products_and_articles['products']) 

for old_product in products_for_update: 
    try: 
    new_product = products_by_article[old_product.article] 
    except KeyError: 
    continue   # ignore non-existent products 
    transfer_fields(old_product, new_product) 

Этот окончательный код имеет временную сложность O(n × k), где n является количество продуктов и k является количество полей.

Answer 2

Вы можете использовать set, чтобы найти пересечение вместо петли по обеим спискам и проверить равенство:

set(products_and_articles['products']).intersection(set(products_for_update)) 

Например:

>>> l=[1,2,3] 
>>> a=[2,3,4] 
>>> set(l).intersection(set(a)) 
set([2, 3]) 

Answer 3

первые два для может быть изменен на:

from itertools import product 


for new_product, old_product in product(list1, list2) 
    # logic and other loops 

и вы можете сделать то же самое для двух внутренних контуров:

for old_field in old_product._meta.get_all_field_names(): 
    for new_field in new_product._meta.get_all_field_names(): 

for old_field, new_field in product(list1, list2) 

Answer 4

Мы начинаем с четырьмя петлями и эффективностью O(n^2*k^2), п быть числом элементов и к быть число атрибутов. Давайте посмотрим, что мы можем сделать.

Прежде всего, избавиться от петли new_product, вам не нужно:

for old_field in old_product._meta.get_all_field_names(): 
    for new_field in new_product._meta.get_all_field_names(): 
     if old_field == new_field and old_field != 'id' and old_field != 'slug': 
      setattr(old_product, old_field, getattr(new_product, old_field)) 

To:

for old_field in old_product._meta.get_all_field_names(): 
    if old_field != 'id' and old_field != 'slug': 
     setattr(old_product, old_field, getattr(new_product, old_field)) 

Понял в O (N^2 * к). Теперь для части поиска продукта.

Во-первых, получить два списка сортируются, а затем продолжайте, как вы делаете, когда вы объединяете списки сортировки слиянием:

a = sorted(products_and_articles['products'], key=lambda x: x.article) 
b = sorted(products_for_update, key=lambda x: x.article) 
i = j = 0 
while(i < len(a) and j < len(b)): 
    if (a[i].article < b[j].article): 
     a += 1 
     continue 
    if (a[i].article > b[j].article): 
     b += 1 
     continue 
    ...logic... 
    a += 1 # Maybe you want to get rid of this one, I'm not sure.. 
    b += 1 

В зависимости от размера базы данных, это может быть более или менее адекватной, потому что она требует, чтобы вы делали новые отсортированные списки. Не очень тяжело в памяти (это все равно только refs), но если у вас действительно длинные списки и ограниченное пространство, огромный выигрыш в эффективности может не компенсировать.

Получил его до O(n*logn*k), это лучшее, что я мог сделать. Вы можете, возможно, получить его еще ниже, используя словари, но он требует, чтобы вы изменили свой дБ, поэтому для этого требуется больше времени и усилий.