如何提高python dict的性能？

Question

我最近用dictoionaries编写了一个python解决方案，得到了很好的结论。这个解决方案完全类似于c++中的多集解决方案。因此，我们确信逻辑是正确的，但是实现还没有达到目标。在

理解以下代码（http://codeforces.com/contest/714/problem/C）的问题描述：

• 对于每个数字，我们需要得到一个由0和1组成的字符串，如果数字中的第i个数字是偶数/奇数，则第i位是0/1。在
• 我们需要保持与上述点给出的映射相同的数量的计数。在

有什么提示/指针可以提高以下代码的性能？它给出了大型测试用例（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

由于@cdlane已经做了解释，我只需要添加对getSPattern的重写，我认为大部分时间都花在这里了。根据我最初的评论，这可以在https://eval.in/641639上找到

^{1}$

使用zfill（18）可能会稍微节省一些时间。在

Answer 2

我看到您的代码有很多小问题，但不能说它们是否会导致严重的性能问题：

您的defaultdict()设置和使用不正确：

^{1}$

defaultdict()构造函数的参数应该是值的类型，而不是键的类型。正确设置defaultdict后，只需执行以下操作：

^{pr2}$

因为如果模式不存在，那么该值现在将默认为零。在

因为说明书上说：

 -  ai — delete a single occurrence of non-negative integer ai from the multiset. It's guaranteed, that there is at least one ai in the multiset.

那么这个：

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

可以是这样：

pat[pattern] -= 1

但是你可以用小于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)