0

这是我对 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]))
4

2 回答 2

4

我不会担心内存占用（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
于 2012-06-04T14:38:23.123 回答
1

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

代替

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

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

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

编辑

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

所以 diff 只是（在 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]))
于 2012-06-04T14:21:58.060 回答