python - 循环工作太久

Question

我有两个字典列表：prices_distincts, prices.

它们通过 连接hash_brand_artnum，它们都按hash_brand_artnum 我不明白为什么循环工作这么长时间排序：

1. 如果长度prices_distincts为 100,000 它适用于30 min

2. 但如果长度prices_distincts为 10,000 它适用于10 sec.

代码：

 prices_distincts = [{'hash_brand_artnum':1202},...,..]
 prices = [{'hash_brand_artnum':1202,'price':12.077},...,...]

 for prices_distinct in prices_distincts:
    for price in list(prices):            
        if prices_distinct['hash_brand_artnum'] == price['hash_brand_artnum']:

            print price['hash_brand_artnum']
            #print prices
            del prices[0]
        else:
            continue

我需要寻找价格相同的商品。价格与价格之间的关系是一对多的。和等价的团价['hash_brand_artnum']

Answer 1

它的工作时间很长，因为你的算法是 O(N^2) 和 100000 ^ 2 = 10000000000 和 10000 ^ 2 = 100000000。所以两个数字之间的因子是 100，而因子在 30 分钟和 10 秒之间 ~100。

编辑：你的代码和这么少的数据很难说，我不知道你的任务是什么，但我认为你的字典不是很有用。可以试试这个：

>>> prices_distincts = [{'hash_brand_artnum':1202}, {'hash_brand_artnum':14}]
>>> prices = [{'hash_brand_artnum':1202, 'price':12.077}, {'hash_brand_artnum':14, 'price':15}]
# turning first list of dicts into simple list of numbers
>>> dist = [x['hash_brand_artnum'] for x in prices_distincts]
# turning second list of dicts into dict where number is a key and price is a value
>>> pr = {x['hash_brand_artnum']:x["price"] for x in prices}

不是您可以遍历您的号码并获取价格：

>>> for d in dist:
...     print d, pr[d]

Answer 2

正如@RomanPekar 提到的，您的算法运行缓慢，因为它的复杂性是O(n^2). 要修复它，您应该将其编写为O(n)算法：

import itertools as it

for price, prices_distinct in it.izip(prices, prices_distincts):
    if prices_distinct['hash_brand_artnum'] == price['hash_brand_artnum']:
        # do stuff

Answer 3

如果价格随着prices_distincts或多或少地增长，那么如果您将price_distincts的大小乘以10，您原来的10秒将乘以10，然后再乘以10（第二个for循环），然后再乘以〜2，因为“list（价格）”（顺便说一句，应该明确地在循环之外完成）：

10 秒*10*10*2 = 2000 秒 = 33 分钟

这种转换通常很昂贵。

 prices_distincts = [{'hash_brand_artnum':1202},...,..]
 prices = [{'hash_brand_artnum':1202,'price':12.077},...,...]
 list_prices = list(prices)

 for prices_distinct in prices_distincts:
    for price in list_prices:            
        if prices_distinct['hash_brand_artnum'] == price['hash_brand_artnum']:

            print price['hash_brand_artnum']
            #print prices
            del prices[0]
        else:
            continue