如何提高python dict的性能？

debugcn 发表于 Dev

mtk

我最近使用dictoionaries编码了python解决方案，该字典获得了TLE裁决。该解决方案与工作中的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 )

克兰

我发现您的代码有很多小问题，但无法说出它们是否会导致严重的性能问题：

您已经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。可以肯定的是，多集中至少要有一个ai。

然后这样：

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

可以简单地是这样的：

pat[pattern] -= 1

您正在使用19个字符串，但是由于规范指出数字将小于10 ** 18，因此您可以改而使用18个字符串。

getSPattern()先执行azfill()然后处理字符串，应该以相反的顺序进行处理，然后再处理字符串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)

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。