如何在简单循环中实现超快的Python性能

Question

我正在做一个叫做 SPOJ 的题目，题目名称是 INTEST。这个题目的目标是先输入测试案例的数量（n）和一个除数（k），然后让你的程序接收 n 个数字。程序会逐行读取这些数字，等到接收到第 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

可以使用 psyco，它会对你的代码进行即时编译，这在处理大循环和复杂计算时非常有效。

编辑: 看起来不允许使用第三方模块，

所以，你可以尝试把你的循环改成列表推导式，这样应该能在C语言的水平上运行，所以会稍微快一点。

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

Answer 2

[编辑以反映新发现和通过的代码在spoj上]

一般来说，当你在spoj上使用Python时：

• 不要用“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()
• 正如Justin建议的，把你的代码（除了psyco的那部分）放在一个函数里，然后在代码的最后简单调用这个函数。
• 有时候，创建一个列表并检查它的长度比创建一个列表并添加它的元素要快。
• 尽量使用列表推导式（以及生成器表达式，如果可能的话）来代替“for”和“while”。对于某些情况，map/reduce/filter也可能加速你的代码。

按照这些建议，我成功通过了INTEST。不过我还在测试其他方法。

Answer 3

嘿，我把时间限制搞定了。我用了以下方法：

• 在 Python 2.5 中使用了 Psyco。
• 用了一个简单的循环，并用一个变量来计数。
• 我的代码全部放在一个 main() 函数里（除了导入 psyco 的那行），然后我调用了这个函数。

最后一个方法是关键。我觉得这和变量的可见性有关，但我不太确定。我的时间是 10.81 秒。你可能用列表推导式能让它更快。

编辑：

使用列表推导式后，我的时间降到了 8.23 秒。把 from sys import stdin, stdout 这行放到函数里，也让我时间减少了一点，最终时间是 8.12 秒。