3

几个月前我开始学习编程，最近才发现codechef。
问题是在使用大量输入的问题上，我的代码总是超过时间限制。我什至无法使输入测试工作。

来自codechef的描述：

输入

输入以两个正整数 nk (n, k<=10^7) 开头。接下来的 n 行输入包含一个正整数 ti，每行不大于 10^9。

输出

写一个整数输出，表示有多少整数 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

这真的应该是一个评论，但无论如何。

请注意，这里有一个公认的 Python 2 解决方案，运行时间为 45.77 秒，所以这显然是可能的。我认为您是 Python 3 缓慢 I/O 的受害者（看起来他们使用的是 3.1.2）。在两百万行输入文件（恰好没有任何可整除的数字）上：当有很多时没有太大区别），在修改为与 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

似乎无法使用 python3 运行测试，因为它的 IO 性能较慢。下面是我能写的最快的代码。回顾几个月的结果，这似乎是最快的 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 中，您可以尝试通过在文件开头添加以下两行来加快解决方案：

import psyco
psyco.full()

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

于 2012-04-25T18:22:16.783 回答