CODEWITHSUNDEEP
pythonpython-2.7performancedictionary
mtk
mtk

Reputation: 13709

How to improve python dict performance?

I recently coded a python solution using dictoionaries which got TLE verdict. The solution is exactly similar to a multiset solution in c++ which works. So, we are sure that the logic is correct, but the implementation is not upto the mark.

The problem description for understanding below code (http://codeforces.com/contest/714/problem/C):

Any hints/pointer to improve the performance of below code? It gave TLE (Time Limit Exceeded) for a large test case(http://codeforces.com/contest/714/submission/20594344).

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 )

Upvotes: 0

Views: 393

Answers (2)

sal
sal

Reputation: 3593

With the explanation already done by @cdlane, I just need to add my rewrite of getSPattern where I think the bulk of time is spent. As per my initial comment this is available on 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)

Using zfill(18) might marginally spare you some time.

Upvotes: 2

cdlane
cdlane

Reputation: 41872

I see lots of small problems with your code but can't say if they add up to significant performance issues:

You've set up, and used, your defaultdict() incorrectly:

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

The argument to the defaultdict() constructor should be the type of the values, not the keys. Once you've set up your defaultdict properly, you can simply do:

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

As the value will now default to zero if the pattern isn't there already.

Since the specification says:

 -  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.

Then this:

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

can simply be this:

pat[pattern] -= 1

You're working with 19 character strings but since the specification says the numbers will be less than 10 ** 18, you can work with 18 character strings instead.

getSPattern() does a zfill() and then processes the string, it should do it in the reverse order, process the string and then zfill() it, as there's no need to run the logic on the leading zeros.

We don't need the overhead of int() to convert the characters to numbers:

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

Consider using ord() instead as the ASCII values of the digits have the same parity as the digits themselves: ord('4') -> 52

And you don't need to loop over the indexes, you can simply loop over the characters.

Below is my rework of your code with the above changes, see if it still works (!) and gains you any performance:

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)

Upvotes: 2

Related Questions