提高 Python 解决方案对主要游戏练习的速度

Question

这是我对Codechef上Lead Game问题的解决方案。它运行良好，但需要 2.63 秒和 3.8M 内存，而我看到许多 C 程序在 0.08 秒和 1.6M 内存内完成。如何使其更快？

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

我不会担心内存占用（Python 数据结构占用更多空间，这是正常的），而且很难指望 Python 脚本在速度方面击败 C 程序。

编辑：无需保留潜在客户历史记录

我的 O（n） 算法在 1.18 秒内运行：

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]

编辑

要查看您的算法花费最多时间的位置，您可以使用：

cat inputfile | python -m cProfile yourScript.py

Answer 2

快速的灵感看起来你有O（n^2）算法，你可以使用O（n）算法。

而不是

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

只需组装一个或多个 for 循环（但不嵌套 for 循环）。

没问题，python si太慢了，只是你的算法不够高效

编辑

我错了，也许附加太慢了。尝试使用理解

所以差异只是（不在 for 循环中）

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

并使用尝试使用元组：

然后是代码。

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]))