[Python] 最快的方法比較兩條List

日期: 2020-Jan-28, 作者: Tim Wong

方法一： 笨方法，用兩組for loop

random.seed(123)
a = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 1000
b = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 1000
random.shuffle(b)
match = False

start = time.time()
c = [False]*len(b)
for a_ in a:
    for b_idx, b_ in enumerate(b):
        if b_==a_: 
            c[b_idx] = True
    

if all(c):
    match = True

end = time.time()

方法二： 先sort 了，再用zip 一一對比。

random.seed(123)
a = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 100000
b = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 100000
random.shuffle(b)
match = False
start = time.time()
a.sort()
b.sort()
c = [False] * len(b)
for idx, a_b in enumerate(zip(a,b)): 
    if a_b[0] == a_b[1]:
        c[idx] = True
if all(c):
    match = True
end = time.time()

方法三： 唔試過唔知，這個方法最後，用dict。

random.seed(123)
a_dict = dict()
a = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 100000
b = ['Tim', 'Same', 'Byran', 'Jacky', '123', '456', '777', '900', 'happy', 'hello'] * 100000
match = False
random.shuffle(b)
start = time.time()
for a_ in a:
    if a_ not in a_dict:
        a_dict[a_] = 1
    else:
        a_dict[a_] += 1
for b_ in b:
    try:
        a_dict[b_] -= 1
    except:
        pass
    
if all(v == 0 for v in a_dict.values()):
    match = True
end = time.time()

第一個方法O(n²)，第二個方法和第三個方法,表面都是O(n)，但第二個方法需要做 sorting ，所以最快的方法是用dict。 Dict[key] 可以一步到位找到想找的element 而不用loop，不用search。

結果：
方法一： 10.45sec. 
方法二： 0.39sec.
方法三： 0.285sec.

全力衝刺中的一團火

我是阿Tim | timwong.ai@gmail.com