3

私は数ヶ月前にプログラミングを学び始め、つい最近codechefを見つけました。
問題は、大量の入力を使用する問題では、私のコードが常に制限時間を超えていることです。入力テストを機能させることすらできないようです。

codechefからの説明：

入力

入力は、2つの正の整数nk（n、k <= 10 ^ 7）で始まります。次のn行の入力には、それぞれ10^9以下の正の整数tiが1つ含まれています。

出力

tiがkで割り切れる整数の数を示す単一の整数を出力に書き込みます。

コードは次のとおりです。

n, t = [int(x) for x in input().split()]
c = 0
for i in range(n):
    if not int(input()) % t:
        c += 1
print(c)

何が欠けているのかわかりません。どうすればこれをより速く処理できますか？

4

3 に答える 3

5

これは本当にコメントになるはずですが、とにかく。

ここには、ランタイム45.77sの受け入れられたPython 2ソリューションがあるので、それは明らかに可能であることに注意してください。あなたはPython3の遅いI/Oの犠牲者だと思います（彼らは3.1.2を使用しているようです）。200万行の入力ファイル（除算可能な数値はありません）：多くの場合はそれほど違いはありません）、2および3と互換性があるように変更されたコードのバージョンでは、次のようになります。

~/coding$ time python2.6 enormread.py < sample.txt 
0

real    0m3.971s
user    0m3.712s
sys 0m0.256s
~/coding$ time python2.7 enormread.py < sample.txt 
0

real    0m2.637s
user    0m2.428s
sys 0m0.204s
~/coding$ time python3.2 enormread.py < sample.txt 
0

real    0m10.412s
user    0m10.065s
sys 0m0.344s
~/coding$ time ~/sys/Python-3.3.0a2/python enormread.py < sample.txt 
0

real    0m6.776s
user    0m6.336s
sys 0m0.436s
~/coding$ time pypy enormread.py < sample.txt 
0

real    0m2.211s
user    0m1.948s
sys 0m0.028s

@agf(sum(not int(line) % t for line in sys.stdin[.buffer]))をミックスに投入するには：

~/coding$ time python2.7 enormfast.py < sample.txt 
0

real    0m1.454s
user    0m1.436s
sys 0m0.016s
~/coding$ time python3.2 enormfast.py < sample.txt 
0

real    0m2.243s
user    0m2.228s
sys 0m0.012s
于 2012-04-25T18:44:09.777 に答える
2

IOパフォーマンスが遅いため、python3を使用してテストを実行することは不可能のようです。以下は私が書くことができる最速のコードです。結果を数か月振り返ると、これは最速のPythonソリューションのようです。len（）の使用は、@ agfが推奨するsum（）の約3倍の速度です。

python2.5:  8.28s

import sys
import psyco
psyco.full()

def main():
    n, k = map(int,sys.stdin.readline().split())
    print len([x for x in sys.stdin if not int(x) % k])

main()
于 2012-04-28T17:33:37.490 に答える
0

Pythonでは、ファイルの先頭に次の2行を追加することで、ソリューションの高速化を試すことができます。

import psyco
psyco.full()

http://www.codechef.com/wiki/faq#Why_do_I_get_a_Time_Limit_Exceeded

于 2012-04-25T18:22:16.783 に答える