0

これが Codechef の Lead Game 問題に対する私の解決策です。正常に動作しますが、2.63 秒と 3.8M のメモリを要しましたが、0.08 秒と 1.6M のメモリで完了した多くの C プログラムを見ました。どうすれば速くなりますか？

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) アルゴリズムを使用できる O(n^2) アルゴリズムを持っているように見えます。

それ以外の

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

1 つまたは複数の 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 に答える