在Python中，爲什麼string.count（）比循環更快？

Question

在leetcode中，我有一個問題來檢查一系列無序的字符串「U」，「D」，「L」，「R」是否會形成一個圓。

我的提議是這樣的：

def judgeCircle(moves): 

    l=r=u=d=0 

    for i in moves: 
     if i == 'L': 
      l+=1 
     if i == 'D': 
      d+=1 
     if i == 'R': 
      r+=1 
     if i == 'U': 
      u+=1 

    return ((l-r)==0) and ((u-d)==0) 

和評價者認爲它的成本239ms 而另一條線路上的解決方案：

def judgeCircle(moves): 
    return (moves.count('R')==moves.count('L')) and 
      (moves.count('U')==moves.count('D')) 

只有39MS成本？

雖然我理解的代碼越少越好，但我認爲第二次會循環4次，我誤解了嗎？

感謝

Answer 1

這裏這將是有趣的，看看時機是呈現出各種方法的速度，同時使用完善的數據與所有4個按鍵等於計數一些timeit代碼，隨機數據與每個鍵的數量大致相等。

#!/usr/bin/env python3 

''' Test speeds of various algorithms that check 
    if a sequence of U, D, L, R moves make a closed circle. 

    See https://stackoverflow.com/q/46568696/4014959 

    Written by PM 2Ring 2017.10.05 
''' 

from timeit import Timer 
from random import seed, choice, shuffle 
from collections import Counter, defaultdict 

def judge_JH0(moves): 
    l = r = u = d = 0 
    for i in moves: 
     if i == 'L': 
      l += 1 
     if i == 'D': 
      d += 1 
     if i == 'R': 
      r += 1 
     if i == 'U': 
      u += 1 
    return ((l-r) == 0) and ((u-d) == 0) 

def judge_JH1(moves): 
    l = r = u = d = 0 
    for i in moves: 
     if i == 'L': 
      l += 1 
     elif i == 'D': 
      d += 1 
     elif i == 'R': 
      r += 1 
     elif i == 'U': 
      u += 1 
    return (l == r) and (u == d) 

def judge_count(moves): 
    return ((moves.count('R') == moves.count('L')) and 
     (moves.count('U') == moves.count('D'))) 

def judge_counter(moves): 
    d = Counter(moves) 
    return (d['R'] == d['L']) and (d['U'] == d['D']) 

def judge_dict(moves): 
    d = {} 
    for c in moves: 
     d[c] = d.get(c, 0) + 1 
    return ((d.get('R', 0) == d.get('L', 0)) and 
     (d.get('U', 0) == d.get('D', 0))) 

def judge_defdict(moves): 
    d = defaultdict(int) 
    for c in moves: 
     d[c] += 1 
    return (d['R'] == d['L']) and (d['U'] == d['D']) 


# All the functions 
funcs = (
    judge_JH0, 
    judge_JH1, 
    judge_count, 
    judge_counter, 
    judge_dict, 
    judge_defdict, 
) 

def verify(data): 
    print('Verifying...') 
    for func in funcs: 
     name = func.__name__ 
     result = func(data) 
     print('{:20} : {}'.format(name, result)) 
    print() 

def time_test(data, loops=100): 
    timings = [] 
    for func in funcs: 
     t = Timer(lambda: func(data)) 
     result = sorted(t.repeat(3, loops)) 
     timings.append((result, func.__name__)) 
    timings.sort() 
    for result, name in timings: 
     print('{:20} : {}'.format(name, result)) 
    print() 

# Make some data 
keys = 'DLRU' 
seed(42) 
size = 100 

perfect_data = list(keys * size) 
shuffle(perfect_data) 
print('Perfect') 
verify(perfect_data) 

random_data = [choice(keys) for _ in range(4 * size)] 
print('Random data stats:') 
for k in keys: 
    print(k, random_data.count(k)) 
print() 
verify(random_data) 

loops = 1000 
print('Testing perfect_data') 
time_test(perfect_data, loops=loops) 

print('Testing random_data') 
time_test(random_data, loops=loops) 

典型輸出

Perfect 
Verifying... 
judge_JH0   : True 
judge_JH1   : True 
judge_count   : True 
judge_counter  : True 
judge_dict   : True 
judge_defdict  : True 

Random data stats: 
D 89 
L 100 
R 101 
U 110 

Verifying... 
judge_JH0   : False 
judge_JH1   : False 
judge_count   : False 
judge_counter  : False 
judge_dict   : False 
judge_defdict  : False 

Testing perfect_data 
judge_counter  : [0.11746118000155548, 0.11771785900054965, 0.12218693499744404] 
judge_count   : [0.12314812499971595, 0.12353860199800692, 0.12495016200409736] 
judge_defdict  : [0.20643479600403225, 0.2069275510002626, 0.20834802299941657] 
judge_JH1   : [0.25801684000180103, 0.2689959089984768, 0.27642749399819877] 
judge_JH0   : [0.36819701099739177, 0.37400564400013536, 0.40291943999909563] 
judge_dict   : [0.3991459790049703, 0.4004156189985224, 0.4040740730051766] 

Testing random_data 
judge_count   : [0.061543637995782774, 0.06157537500257604, 0.06704995800100733] 
judge_counter  : [0.11995147699781228, 0.12068584300141083, 0.1207217440023669] 
judge_defdict  : [0.2096717179956613, 0.21544414199888706, 0.220649760995002] 
judge_JH1   : [0.261116588000732, 0.26281095200101845, 0.2706491360004293] 
judge_JH0   : [0.38465088899829425, 0.38476935599464923, 0.3921787180006504] 
judge_dict   : [0.40892754300148226, 0.4094729179996648, 0.4135226650032564] 

這些定時分別運行Linux的Python 3.6.0我的舊2GHz的32位計算機上獲得的。

---

這裏有幾個更多的功能。

def judge_defdictlist(moves): 
    d = defaultdict(list) 
    for c in moves: 
     d[c].append(c) 
    return (len(d['R']) == len(d['L'])) and (len(d['U']) == len(d['D'])) 

# Sort to groups in alphabetical order: DLRU 
def judge_sort(moves): 
    counts = [sum(1 for _ in g) for k, g in groupby(sorted(moves))] 
    return (counts[0] == counts[3]) and (counts[1] == counts[2]) 

judge_defdictlist比judge_defdict慢，但比judge_JH1更快，當然，它使用比judge_defdict更多的內存。

judge_sort比judge_JH0慢，但快於judge_dict。

Answer 2

兩個代碼樣本有算法的複雜O(n)，但你不應該由大O字被愚弄了，因爲它只能說明趨勢。 O(n)算法的執行時間可以表示爲C * n，其中C是常數，取決於許多因素。

對於.count()代碼，您需要在C函數中執行4個循環，但C函數速度很快。它還使用了一些高級算法，如fastsearch。這裏只執行字符串搜索，最小的解釋器開銷。

在純Python代碼中，您只需要單循環，但每次迭代都需要執行更多的低級代碼，因爲Python是解釋型語言*。例如，您正在爲循環的每次迭代創建新的unicode或字符串對象，並且創建對象是一項非常昂貴的操作。由於整數對象是不可變的，所以您需要爲每個計數器重新創建它們。

^{*假設你使用CPython的解釋，這是相當多的默認}

Answer 3

在想你，因爲在處理器分支預測算法放緩的第一代碼。如果循環內有4個不同的if檢查，最有可能的是處理器比後面的代碼更容易產生錯誤的分支預測，其中.count每次只執行一個循環。

如果輸入數據按字母順序排序