循环工作时间过长

Question

我有两个dict列表：prices_distincts，prices。在

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

1. 如果prices_distincts的长度是100000，它适用于30 min

2. 但如果prices_distincts的长度为10000，则它适用于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

正如@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 2

如果价格随着价格的增加而增加或减少，那么如果你将价格的大小乘以10，你原来的10秒将乘以10，然后再乘以10（循环秒数），然后再乘以2，因为“列表（价格）”（顺便说一句，这肯定是在循环外进行的）：

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

Answer 3

因为你的算法是O（N^2）和100000^2=1000000000和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}

不，你可以通过你的数字迭代得到价格：

^{pr2}$