如何通过简单循环实现真正快速的Python

Question

如何通过简单循环实现真正快速的Python

pythonperformanceoptimization

22

我正在解决一个 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()

- Michael Westbom

你尝试过读取更大的块吗？你对它进行了分析以查看哪些操作最耗费时间吗？你能减少模运算的强度吗？你能使用映射函数来利用它们基于C的循环吗？我不知道这些中的任何一个是否有帮助，但很明显问题不是算法难题... - msw

哦，我对这些事情都不确定。我尝试解决这个问题的主要原因是想看看Python能跑多快以及如何进行优化。在这个问题中，重点并不在算法难度上，而是在速度方面的优化。 - Michael Westbom

6个回答

8

嘿，我在时间限制内完成了它。我使用了以下方法：

Python 2.5中的Psyco。
一个简单的循环和一个计数变量。
我的代码都在一个main()函数中（除了psyco导入），我调用了这个函数。

最后一个是有所不同的。我相信这与变量可见性有关，但我不完全确定。我的时间是10.81秒。您可以通过列表理解使其更快。

编辑：

使用列表理解将我的时间缩短到8.23秒。将from sys import stdin, stdout行放在函数内部也可以稍微缩短一下时间，将我的时间缩短到了8.12秒。

- Justin Peel

2

该死，听起来有些违反直觉，但把所有东西放在一个函数里确实可以工作 :P - rbp

嗯，已将代码编辑为现在在原帖中看到的样子，但仍然无法通过。有没有更好的方法来调用main()函数？ - Michael Westbom

我没有加入 if __name__ == "__main__": 这一部分。此外，我会取消列表推导式中的 else 部分，并在 sum 内部表达式周围添加 []。我发现如果没有 []，速度会慢很多。 - Justin Peel

1

模块级变量需要查询并修改哈希表来获取或设置它们。函数级变量只需要索引数组。 - jemfinch

Jemfinch，这确实是有价值的信息。我的代码运行时间太长了，但我感觉我们正在取得进展。或者至少你们都在帮助我前进。顺便说一句，非常感谢你们所有人。 - Michael Westbom

@totallymike 尝试只使用像你最初那样的简单循环（当然是在函数内部）。对我来说已经足够快了。 - Justin Peel

6

使用psyco，它将JIT您的代码，在存在大循环和计算时非常有效。

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

因此，您可以尝试将循环转换为列表理解式，它应该在C级别运行，所以速度应该会更快一点。

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

- YOU

1

因为代码在他们的机器上运行，所以不允许使用外部模块。 - Michael Westbom

1

所以我尝试了Psyco，显然它是被支持的。虽然没有让我的速度提升足够多，但确实增加了内存占用，所以我很有信心它是有效的。 - Michael Westbom

你的标准输入数据有多大？我认为只有在数据中有数千个循环或计算时，才能提高速度。 - YOU

SPOJ不允许您查看测试数据，但他们宣称您希望能够每秒处理2.5M的输入数据。问题的整个重点在于查看您的代码可以运行多快。 - Michael Westbom

3

使用psyco和列表推导式是不划算的。

这段代码：

 count = 0
 for l in sys.stdin:
     count += not int(l)%k

运行速度是原来的两倍

count = sum(not int(l)%k for l in sys.stdin)

在使用Psyco时。

- user377964

3

最近，Alex Martinelli说，在函数内调用代码比在模块中运行代码更快（我找不到这篇文章了）。

那么，为什么不试试：

import sys
import psyco

psyco.full1()

def main():

    first_in = raw_input()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0
    i = 0

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

    print total
if __name__ == "__main__":
    main()

据我所知，原因是函数内的代码可以被优化。

- OscarRyz

将 psyco.full() 放在 import psyco 的下面。将其放在函数内部会使其效果非常差。当我将其与我的代码一起放在 main() 函数中时，代码的运行速度与根本不使用 psyco 时一样快。 - Justin Peel

2

对于其他读者，这里是INTEST问题陈述。它旨在进行I/O吞吐量测试。

在我的系统上，我通过用以下内容替换循环，成功将执行时间缩短了15%：

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

- Daniel Stutzbach

感谢更新。我已经加入了求和行，似乎提高了速度，但还不够，可惜。 - Michael Westbom

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rbp · Accepted Answer

[更新以反映新发现并在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。尽管仍在测试替代方案。