我正在处理 SPOJ问题,INTEST .目标是指定测试用例的数量 (n) 和除数 (k),然后为您的程序提供 n 个数字。该程序将接受标准输入换行符上的每个数字,并在收到第 n 个数字后,将告诉您有多少可以被 k 整除。
这个问题的唯一挑战是让你的代码变得 FAST,因为 k
可以是高达 10^7 的任何东西,而 n
可以高达 10^9 .
我正在尝试用 Python 编写它,但无法加快速度。有什么想法吗?
编辑 2:我终于让它在 10.54 秒通过。我几乎用了你所有的答案来达到这个目的,因此很难选择一个“正确”的答案,但我相信我选择的答案是最好的。谢谢大家。最终通过代码如下。
编辑:我在包含的代码中包含了一些建议的更新。
不允许扩展和第三方模块。代码也是由 SPOJ 判断机器运行的,所以我没有更换解释器的选项。
import sys
import psyco
psyco.full()
def main():
from sys import stdin, stdout
first_in = stdin.readline()
thing = first_in.split()
n = int(thing[0])
k = int(thing[1])
total = 0
list = stdin.readlines()
for item in list:
if int(item) % k == 0:
total += 1
stdout.write(str(total) + "\n")
if __name__ == "__main__":
main()
最佳答案
[编辑以反射(reflect)新发现并在 spoj 上传递代码]
一般情况下,使用 Python 进行 spoj 时:
- 不要使用“raw_input”,使用 sys.stdin.readlines()。这可以对大输入产生影响。此外,如果可能(对于这个问题,确实如此),一次读取所有内容(sys.stdin.readlines()),而不是逐行读取(“for line in sys.stdin ...”)。<
- 同样,不要使用“print”,使用 sys.stdout.write() - 并且不要忘记“\n”。当然,这仅适用于多次打印。
- 按照 S.Mark 的建议,使用 psyco。它适用于 python2.5 和 python2.6,在 spoj(测试它,它就在那里,并且很容易发现:使用 psyco 的解决方案通常有一个 ~35Mb 的内存使用偏移量)。这真的很简单:只需在“import sys”之后添加:import psyco; psyco.full()
- 按照贾斯汀的建议,将您的代码(除了 psyco 咒语)放在一个函数中,然后在代码末尾调用它
- 有时,创建列表并检查其长度可能比创建列表并添加其组件更快。
- 支持列表推导(和生成器表达式,如果可能的话)优于“for”和“while”。对于某些结构,map/reduce/filter 还可以加快您的代码速度。
使用(部分)这些准则,我成功通过了 INTEST。不过,仍在测试替代方案。
关于python - 如何通过一个简单的循环获得真正快速的 Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2650544/