學(xué)習(xí)python的小伙伴都知道python語法簡單瘾蛋，學(xué)習(xí)起來上手快。但是代碼的運(yùn)行效率一直讓人詬病矫限。確實哺哼，在一些場景中，python代碼的運(yùn)行效率確實沒有C++或者C效率高叼风。但是在一些場景下取董，我們也可以通過一些優(yōu)化來提升運(yùn)行效率。下面我們從一道算法題入手帶著大家剖析一下无宿。

題目：給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target茵汰，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那兩個整數(shù)，并返回它們的數(shù)組下標(biāo)孽鸡，如果有多組蹂午，只返回一組即可栏豺。這道題非常簡單，是Leecode刷題網(wǎng)站的第1題豆胸。下面我們按步驟來解析優(yōu)化奥洼。

1. 方法1：最簡單的想法，for循環(huán)暴力解決：

最簡單粗暴的方法晚胡，即從列表的第一個數(shù)開始灵奖，依次與后面的數(shù)相加看看是否等于目標(biāo)值。如果不滿足估盘，在取第二個數(shù)桑寨，并與它后面的數(shù)相加直至將所有的數(shù)遍歷一遍，代碼如下：

def find_pairs(target, nums_list):
    """
    :para:target, int, the required target of 2 nums in the nums_list
    :para:nums_list, a list of int nums
    :return: the 2 nums index in the list, which sum is target value.
    """

    for i in range(len(nums_list)):
        for j in range(i + 1, len(nums_list)):
            if nums_list[i] + nums_list[j] == target:
                print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
                return i, j
    return None # 如果循環(huán)結(jié)束還沒有符合的輸出None

我們用兩個測試案例檢驗一下

target1,nums_list1 = 14, [3,6,9,1,4,5] # 正常案例忿檩， 輸出index 2,5
target2,nums_list2 = 20, [3,6,9,1,4,5] # 沒有合適的數(shù)值，輸出None
result1 = find_pairs(target1, nums_list1)
result2 = find_pairs(target2, nums_list2)
print('******* Following is the result ******')
print(result1)
print(result2)
>>>For target: 14, index is: 2, 5 , value is 9, 5
******* Following is the result ******
(2, 5)
None

上面的方法使用了兩重循環(huán)爆阶，其效率非常低燥透。可以稍微換位思考一下辨图，我們使用target依次減去列表中元素獲得一個差值班套，在判斷該差值是否在列表剩下的元素中同樣可以解決問題，這樣我們只使用一個循環(huán)就可以完成故河。

2. 方法二：改進(jìn)版吱韭，查找列表中是否存在target減去當(dāng)前值的差

代碼如下：

def find_pairs_v2(target, nums_list):
    """
    :para:target, int, the required target of 2 nums in the nums_list
    :para:nums_list, a list of int nums
    :return: the 2 nums index in the list, which sum is target value.
    """

    for i in range(len(nums_list)):
        a = target - nums_list[i]
        if a in nums_list[i+1:]:
            j = nums_list.index(a)
            print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
            return i, j
    return None

下面使用兩個測試案例對兩個方法的運(yùn)行時間進(jìn)行比較，看看效率是否有提升
先確保兩個方法都的行為一致鱼的，即輸出同樣的結(jié)果：

# 使用同一個測試用例理盆， 首先確保兩個方法的行為一致，輸出的結(jié)果相同
target,nums_list = 50, [3,6,9,1,4,5,14,20,30]
result1 = find_pairs(target, nums_list)
result2 = find_pairs_v2(target, nums_list)
print(f"result from 2-for-loop is: {result1}")
print(f"result from improved one for loop is: {result2}")

>>>result from 2-for-loop is: (7, 8)
result from improved one for loop is: (7, 8)

上面的案例中凑阶，將target設(shè)置成50猿规，強(qiáng)制程序走到最后一個循環(huán)，對比最差情況下的時間效率宙橱。下面使用%timeit魔法命令測試運(yùn)行時間姨俩。該魔法命令的詳細(xì)用法可以參考：N多Notebook技巧讓你的Jupyter notebook起飛 - 簡書 (jianshu.com)

注意: 以下該魔法命令的演示是在Notebook中完成的。為了讓程序運(yùn)行過程中不在輸出print語句师郑，需要把上面方法定義中的print語句注釋掉环葵。

%timeit find_pairs(target, nums_list)
>>>10.2 μs ± 3.26 μs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit find_pairs_v2(target, nums_list)
>>>4.62 μs ± 1.12 μs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

可以看到改成一個for循環(huán)后運(yùn)行時間減少了一倍左右，這個隨著列表元素的增多效果更加明顯宝冕。

3. 進(jìn)一步提升

上面的方法二在判斷一個元素是否在列表中的時候张遭，實際上內(nèi)部仍然是通過遍歷列表來完成的。在比較極端的情況下時間復(fù)雜度仍然為O(n)猬仁。那么有沒有方法改進(jìn)呢帝璧？有的先誉，在Python查找元素，相對于列表的烁，字典是一種更加高效的數(shù)據(jù)結(jié)構(gòu)褐耳。字典的鍵是有可哈希的數(shù)據(jù)構(gòu)成，查找字典中的鍵以及通過這個鍵取值的時間復(fù)雜度均為O(1)渴庆。所以铃芦，思路來了，我們將列表轉(zhuǎn)換為字典襟雷，使用字典的鍵作為列表中的元素刃滓，值為該元素在列表中的index。查找命中該鍵后直接輸出該鍵對應(yīng)的值即可耸弄，代碼如下：

def find_pairs_v3(target, nums_list):
    temp_map = dict()
    for i, num in enumerate(nums_list):
        if target - num in temp_map:
            j = temp_map[target - num]
            print(f'For target: {target}, index is: {i}, {j} , value is {nums_list[i]}, {nums_list[j]}')
            return [temp_map[target - num], i]
        temp_map[nums_list[i]] = i
    return None

同樣的咧虎，我們使用和上面同一個用例測試一下：

print(target, nums_list)
find_pairs_v3(target, nums_list)
>>>50 [3, 6, 9, 1, 4, 5, 14, 20, 30]
For target: 50, index is: 8, 7 , value is 30, 20

下面使用同一個案例測試V2和V3版本的運(yùn)行時間，看看是不是改成字典后效率有所提升：

%timeit find_pairs_v3(target, nums_list)
>>>2.68 μs ± 4.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

效率有所提升计呈，但是不明顯砰诵。將時間復(fù)雜度從O(n)降低到O(1)，這個是數(shù)量級方面的提升捌显。猜測可能是因為列表的長度不夠茁彭，我們將列表長度增加再來嘗試一下。

image.png

上面代碼中扶歪，在列表的末尾插入兩個元素100,200理肺，在將target設(shè)置成300，強(qiáng)制讓程序走到最后一個循環(huán)測試最差的情況善镰。
可以看到將列表的長度增加到900后妹萨，運(yùn)行時間有了數(shù)量級的提升，但這個還不夠媳禁。這樣的差異對于O(n)和O(1)仍然不夠可觀眠副。其中的原因，猜測可能是Python內(nèi)部對于這種int型的數(shù)據(jù)有相應(yīng)的優(yōu)化竣稽。如果我們將需要查找的元素改為字符串再來對比一下列表和字典元素查找的效率囱怕。

4. 使用字符串測試列表和字典的查找時間效率

首先我們定義一個方法可以生成任意長度的字符串列表name_list，并規(guī)定name_list中字符串元素的長度毫别。代碼如下：

# 首先定義一個方法產(chǎn)生長度為n的列表娃弓，列表中每個元素包含m的字符（大寫或者小寫）
import string
import random
def gen_name_list(list_len, name_len):
    name_list = []
    while len(name_list) < list_len:
        name = ''.join(random.sample(string.ascii_letters, name_len))
        if name not in name_list:
            name_list.append(name)
    return name_list

# test
gen_name_list(5, 6) # 測試：生成一個包含5個元素的列表，每個元素長度6

>>> ['LCBmZR', 'vrFypk', 'GCTdMh', 'eOMqHc', 'dHVxDA']

好了岛宦，有個這個方法后台丛， 我們先用這個方法生成一個包含1000個元素的字符串列表，每個字符串包含8個元素，同時挽霉，將列表的中間元素和最后一個元素取出備用防嗡。另外再將這個列表轉(zhuǎn)成字典：

result_list = gen_name_list(1000, 8)
print(result_list[:5])
mid_str, last_str = result_list [500], result_list[-1]
print(mid_str, last_str)

result_dict = {k:v for v,k in enumerate(result_list)} # 將列表轉(zhuǎn)換成字典，鍵為元素侠坎，值為該元素在列表中的index
print(result_dict[mid_str], result_dict[last_str])
>>>['rGvpIBET', 'igwoZJKC', 'faEXAzTl', 'xIwibYGK', 'DqUClGkZ']
FOosAXyl bWryJKuB
500 999

下面我們只測試列表和字典的查找效率蚁趁，查找的代碼如下：

def find_key_list(key, list):
    if key in list:
        return key
    else:
        return None
    
def find_key_dict(key, dict):
    if key in dict:
        return key
    else:
        return None

測試前，使用測試案例確保兩個方法的行為一致：

r1_list = find_key_list(mid_str, result_list)
r2_list = find_key_list(last_str, result_list)
r1_dict = find_key_dict(mid_str, result_dict)
r2_dict = find_key_dict(last_str, result_dict)
print(r1_list, r2_list)
print(r1_dict, r2_dict)
>>>FOosAXyl bWryJKuB
FOosAXyl bWryJKuB

運(yùn)行時間統(tǒng)計实胸，仍然使用%timeit魔法方法他嫡，結(jié)果如下圖：

image.png

OK， 這個效果就比較明顯了庐完。而且從上面的結(jié)果中钢属，也可以驗證我們的結(jié)論：

• 列表查找時本質(zhì)上仍然是采用循環(huán)來遍歷。我們從查找中間元素和隊列末尾元素的用時也能看出來门躯，隨著該元素越靠后淆党，用時越長。上面的結(jié)果中讶凉，中間元素用時11.5us, 而隊尾元素用時16.8us, 差異明顯
• 而對于字典來說宁否，第一，其查找效率相對于列表有個質(zhì)的提升缀遍。而且，因為其時間復(fù)雜度為O(1), 其查找的時間與元素的位置無關(guān)饱须。上面的結(jié)果中域醇，中間元素用時192ns， 隊尾元素用時198ns, 幾乎沒有差別

注意：以上測試結(jié)果和測試平臺軟硬件均有關(guān)蓉媳，不同的配置結(jié)果可能會有差異

好了譬挚，以上就是本次分享案例的所有內(nèi)容。從這個案例中我們可以深刻的領(lǐng)會到在列表中查找一個元素的時間復(fù)雜度為O(n), 而在字典中獲取一個鍵的時間復(fù)雜度為O(1)酪呻。同時在解析過程帶著大家領(lǐng)略一下Python中列表和字典的一些小技巧减宣，例如將一個列表轉(zhuǎn)成字典，隨機(jī)生成一個固定長度的字符串等等玩荠，希望大家看完有所收獲漆腌。如果對你有所幫忙，還希望點(diǎn)個贊+一鍵3連阶冈！感謝闷尿！