如何通过简单的循环获得真正快速的Python

Question

我正在研究一个SPOJ问题,INTEST.目标是指定测试用例的数量(n)和除数(k),然后为程序提供n个数字.该程序将接受stdin换行符上的每个数字,并在收到第n个数字后,将告诉您有多少可被k整除.

这个问题唯一的挑战是让你的代码变得快速,因为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()

Answer 1

[编辑反映新发现并在spoj上传递代码]

通常,在使用Python for spoj时:

• 不要使用"raw_input",请使用sys.stdin.readlines().这可以为大输入带来改变.另外,如果可能的话(对于这个问题),一次读取所有内容(sys.stdin .readlines()),而不是逐行读取("for sys.stdin中的行...").
• 同样,不要使用"print",使用sys.stdout.write() - 并且不要忘记"\n".当然,这仅在多次打印时才有意义.
• 正如S.Mark建议的那样,使用psyco.它可用于python2.5和python2.6,在spoj(测试它,它就在那里,并且很容易发现:使用psyco的解决方案通常具有~35Mb的内存使用偏移量).这很简单:只需在"import sys"之后添加:import psyco; psyco.full()
• 正如Justin建议的那样,将你的代码(除了psyco咒语)放在一个函数中,然后在你的代码末尾调用它
• 有时创建列表并检查其长度可能比创建列表和添加其组件更快.
• 在"for"和"while"之上支持列表推导(以及生成器表达式,如果可能).对于某些构造,map/reduce/filter也可以加速您的代码.

使用(某些)这些指导原则,我设法通过了INTEST.不过还在测试替代品.

Answer 2

嘿,我知道它在时间限制内.我使用了以下内容:

• Psyco与Python 2.5.
• 一个简单的循环,带有一个变量来保持计数
• 我的代码全部在main()函数中(除了psyco导入),我调用了它.

最后一个是有所作为的.我认为它与变量可见性有关,但我不完全确定.我的时间是10.81秒.你可以通过列表理解让它更快.

编辑:

使用列表理解使我的时间缩短到8.23秒.将from sys import stdin, stdout功能内部的线条稍微削掉,使我的时间缩短到8.12秒.

Answer 3

使用psyco,它会JIT你的代码,当有大循环和计算时非常有效.

编辑:看起来不允许第三方模块,

因此,您可以尝试将循环转换为列表推导,它应该在C级别运行,因此它应该更快一点.

sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)