如何提高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）可能会稍微爱惜你一段时间。