Améliorer la vitesse d'une solution Python à l'exercice Lead Game

Question

Voici ma solution à the Lead Game problem on Codechef. Il fonctionne bien, mais a pris 2.63 sec et 3.8M de mémoire, alors que j'ai vu beaucoup de programmes C qui avaient terminé en 0.08 secondes et 1.6M de mémoire. Comment puis-je le rendre plus rapide?

import sys 
cnt = int(sys.stdin.readline()) 
match = [[int(x) for x in sys.stdin.readline().split()] for i in range(cnt)] 
diff=[] 
for i in range(cnt): 
     if i!=0: 
      match[i]=[sum(vals) for vals in zip(match[i-1],match[i])] 
     diff.append([1 if max(match[i])==match[i][0] else 2,abs(match[i][0]-match[i][1])]) 
maxval = max(diff,key=lambda x:x[1]) 
sys.stdout.write(str(maxval[0]) + ' ' + str(maxval[1])) 

Answer 1

Je ne vous soucier de l'empreinte mémoire (structures de données Python prennent un peu plus d'espace, et il est normal) et aussi il est difficile d'attendre un script Python pour battre un programme C en termes de vitesse.

Modifier: pas besoin de garder conduit l'histoire

Mon O (n) algorithme a couru en 1.18 secondes:

import sys 

rounds = int(sys.stdin.readline()) 

score = [0,0] 
leads = [0,0] 
while rounds > 0: 
    results = map(int, sys.stdin.readline().split()) 
    score[0] += results[0] 
    score[1] += results[1] 
    lead = score[0] - score[1] 
    if (lead < 0 and leads[1] < -lead): leads[1] = -lead 
    if (lead > 0 and leads[0] < lead): leads[0] = lead 
    rounds -= 1 

if (leads[0] > leads[1]): print 1, leads[0] 
else: print 2, leads[1] 

Modifier

Pour voir où votre algorithme passe le plus clair temps que vous pouvez utiliser:

cat inputfile | python -m cProfile yourScript.py 

Answer 2

L'inspiration rapide semble que vous avez l'algorithme O (n^2), où vous pouvez utiliser l'algorithme O (n).

Au lieu de

for: 
    for: #this for comes from line whit list comprehension 

Il suffit de monter un ou plusieurs pour les boucles (mais pas pour les boucles imbriquées).

Il est pas un problème, que si python trop lent, juste votre algorithme est pas assez efficace

EDIT

J'ai eu tort, peut-être ajouter est tout simplement trop lent. Essayez d'utiliser la compréhension

si diff est juste (hors boucle)

diff = [[1 if max(m)==m[0] else 2,abs(m[0]-m[1])] for m in match] 

et utilisez essayer d'utiliser tuples:

Code

est alors.

import sys 
cnt = int(sys.stdin.readline()) 
match = [tuple(int(x) for x in sys.stdin.readline().split()) for i in range(cnt)] 
diff=[] 
for i in range(cnt): 
    if i!=0: 
     match[i]=tuple(sum(vals) for vals in zip(match[i-1],match[i])) 
diff = [tuple((1 if max(m)==m[0] else 2,abs(m[0]-m[1]))) for m in match] 
maxval = max(diff,key=lambda x:x[1]) 
sys.stdout.write(str(maxval[0]) + ' ' + str(maxval[1]))