python dict 성능을 향상시키는 방법은 무엇입니까?

Question

나는 최근에 TLE 평결을 얻은 dictoionaries를 사용하여 python 솔루션을 코딩했습니다. 이 솔루션은 작동하는 C++의 멀티 세트 솔루션과 정확히 유사합니다. 따라서 우리는 논리가 정확하다는 것을 확신합니다. 그러나 구현은 그 목표에 달려 있습니다.

코드 아래 이해 (http://codeforces.com/contest/714/problem/C)에 대한 문제 설명 : 숫자 i 번째 0/1이되도록 우리는 0과 1의 문자열을 얻을 필요가 각 번호에 대한

• 경우 수의 각각의 i 번째 자리 짝수/홀수
• 위의 설명에 의해 주어진 매핑과 동일한 매핑 수를 유지해야합니다.

아래의 코드 성능 향상을위한 힌트/포인터는 무엇입니까? 그것은 큰 테스트 케이스 (http://codeforces.com/contest/714/submission/20594344)를 위해 TLE (Time Limit Exceeded)를주었습니다.

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 

으로 패턴이 있지 않은 경우.

은 사양 말한다 이후 :

이 - 음이 아닌 정수의 하나의 발생은 MULTISET에서 인공 지능 삭제 - 인공 지능. 멀티셋에는 최소한 하나의 인공 지능이 있다는 것이 보장됩니다.

그런 다음이 :

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

단순히이 될 수 있습니다

pat[pattern] -= 1 

당신은 19 개 문자열로 작업하지만 사양은 말한다 때문에 숫자가 10보다 작아야합니다 ** 18 대신에 18 개의 문자열로 작업 할 수 있습니다. 선두 제로에 논리를 실행할 필요가 없습니다으로

getSPattern()가 zfill()을 수행하고 다음 문자열을 처리, 그것은, 그것을 처리, 역순으로 문자열을 그것을 다음 zfill()한다.

우리는 숫자에 문자를 변환 할 int()의 오버 헤드를 필요가 없습니다 숫자의 ASCII 값이 숫자 자체와 같은 패리티가 대신으로

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

이 ord() 사용을 고려 : ord('4')를 -> 52

인덱스를 반복 할 필요가 없으며 단순히 문자 위로 반복 할 수 있습니다. (!) 아래

가 위의 변경과 코드의 내 재 작업, 그것은 여전히 ​​작동하는지 확인하고 당신에게 어떤 성능을 얻는다 : 이미 @cdlane에 의해 수행 설명과

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

을, 난 그냥 필요 대량의 시간이 소비 된 것 같아 getSPattern의 재 작성을 추가하십시오. 내 초기 의견에 따라 경찰이 당신에게 시간을 절약 소폭 수 zfill (18)를 사용하여 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) 

볼 수 있습니다.