如何提高python字典性能？

Question

我最近使用dictoionaries編寫了一個python解決方案，它得到了TLE判決。該解決方案與C++中的multiset解決方案非常相似。所以，我們確信這個邏輯是正確的，但是實現並不符合標準。

問題描述爲下面的代碼的理解（http://codeforces.com/contest/714/problem/C）：

• 對於每一個我們需要得到0和1組成的串號，使得第i個數字是0/1，如果在數量上相應的第i位是偶數。
• 我們需要維護具有上述點給出的相同映射的數量。

任何提示/指針，以改善以下代碼的性能？它爲一個大型測試案例（http://codeforces.com/contest/714/submission/20594344）提供了TLE（超出時間限制）。

from collections import defaultdict 

def getPattern(s): 
    return ''.join(list(s.zfill(19))) 

def getSPattern(s): 
    news = s.zfill(19) 
    patlist = [ '0' if (int(news[i])%2 == 0) else '1' for i in range(19) ] 
    return "".join(patlist) 


t = int(raw_input()) 
pat = defaultdict(str) # holds strings as keys and int as value 

for i in range(0, t): 
    oper, num = raw_input().strip().split(' ') 

    if oper == '+' : 
     pattern = getSPattern(str(num)) 
     if pattern in pat: 
      pat[pattern] += 1 
     else: 
      pat[pattern] = 1 
    elif oper == '-' : 
     pattern = getSPattern(str(num)) 
     pat[pattern] = max(pat[pattern] - 1, 0) 
    elif oper == '?' : 
     print pat.get(getPattern(num) , 0) 

Answer 1

我看到很多的小問題與您的代碼，但不能說，如果他們加起來顯著的性能問題：

您已經成立，並使用您的defaultdict()錯誤：

pat = defaultdict(str) 
... 
if pattern in pat: 
    pat[pattern] += 1 
else: 
    pat[pattern] = 1 

構造函數defaultdict()的參數應該是值的類型，而不是鍵的類型。一旦你設置了defaultdict正確，你可以簡單地做：

pat = defaultdict(int) 
... 
pat[pattern] += 1 

當值現在的默認值爲零，如果該模式是不存在的話。

由於規範說：

- 愛 - 刪除非負整數的單個發生從多重集的AI。這是保證，至少有一個ai在 multiset。

那麼這個：

pat[pattern] = max(pat[pattern] - 1, 0) 

可以簡單地是這樣的：

pat[pattern] -= 1 

你有19個字符串的工作，但由於該規範說的數字將低於10 ** 18，你可以用18個字符串來代替。

getSPattern()做了zfill()，然後處理字符串，它應該做它以相反的順序，過程中的字符串，然後zfill()它，因爲沒有必要的前導零運行的邏輯。

我們不需要的int()開銷將字符轉換爲數字：

(int(news[i])%2 == 0) 

考慮使用ord()而不是作爲數字的ASCII值具有相同的奇偶數字本身：ord('4') - > 52

而且你不需要遍歷索引，你可以簡單地遍歷字符。

下面是我用上面的修改代碼的返工，看它是否仍然有效並獲得您的任何性能（！）：

from collections import defaultdict 

def getPattern(string): 
    return string.zfill(18) 

def getSPattern(string): 
    # pattern_list = (('0', '1')[ord(character) % 2] for character in string) 
    pattern_list = ('0' if ord(character) % 2 == 0 else '1' for character in string) 
    return ("".join(pattern_list)).zfill(18) 

patterns = defaultdict(int) # holds keys as strings as and values as int 

text = int(raw_input()) 

for _ in range(text): 
    operation, number = raw_input().strip().split() 

    if operation == '+': 
     pattern = getSPattern(number) 
     patterns[pattern] += 1 
    elif operation == '-': 
     pattern = getSPattern(number) 
     patterns[pattern] -= 1 
    elif operation == '?': 
     print patterns.get(getPattern(number), 0) 

Answer 2

已同意@cdlane做了解釋，我只需要加上我的重寫getSPattern，我認爲大部分時間都花在這裏。按我最初的註釋，這是可在https://eval.in/641639

def getSPattern(s): 
    patlist = ['0' if c in ['0', '2', '4', '6', '8'] else '1' for c in s] 
    return "".join(patlist).zfill(19) 

使用zfill（18）可能會稍微愛惜你一段時間。