python dictのパフォーマンスを改善するには？

Question

私は最近、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 

通りのパターンがすでに存在していない場合。

仕様は言うので：

- AI - 多重集合から非負整数AIの単一の発生を削除します。 マルチセットに少なくとも1つのAIがあることが保証されています。

次に、この：

pat[pattern] -= 1 

あなたは19文字列で作業しているが、仕様は数字が10未満になると言うので、**：

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

は単純に、このことができます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) 

で提供されています。