关注

Py学习 » Python

如何通过一个简单的循环获得非常快的python

totallymike • 5 年前 • 965 次点击

我正在研究 SPOJ 问题, INTEST . 目标是指定测试用例数(n)和除数(k),然后输入程序n个数字。程序将接受stdin新行中的每个数字,并且在接收到第n个数字后,将告诉您有多少数字可以被k整除。

这个问题的唯一挑战是让代码更快,因为 k 最多可以是10^7和 n 可高达10^9。

我试着用python编写它,但在加速时遇到了困难。有什么想法吗?

编辑2:我终于在10.54秒时通过了。我几乎用了你所有的答案,因此很难选择一个“正确的”,但我相信我选择的答案是最好的。谢谢大家。最终通过代码如下。

编辑:我在包含的代码中包含了一些建议的更新。

不允许使用扩展和第三方模块。该代码也由spoj judge机器运行,因此我没有更改解释程序的选择。

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()

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/30331

965 次点击

文章 [ 6 ] | 最新文章 5 年前

• 1 楼

Daniel Stutzbach 14 年前

对于其他读者, here is the INTEST problem statement . 它旨在进行I/O吞吐量测试。

在我的系统中,我可以将循环替换为以下内容,从而节省15%的执行时间:

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

• 2 楼

user377964 13 年前

将列表理解与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时。

• 3 楼

Community Lieven Keersmaekers 6 年前

就在最近 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()

IIRC的原因是函数内的代码可以优化。

• 4 楼

YOU 14 年前

使用 psyco 它会使代码抖动,在有大循环和计算时非常有效。

编辑 :似乎不允许第三方模块,

所以,您可以尝试将循环转换为列表理解,它应该在C级别运行,所以它应该更快一点。

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

• 5 楼

rbp 14 年前

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

通常,当使用python进行spoj时:

不要使用“原始输入”,使用sys.stdin.readlines()。这会对大输入产生影响。另外,如果可能的话(也就是说,对于这个问题),立即读取所有内容(sys.stdin)。readlines(),而不是逐行读取(“for line in sys.stdin…”)。
同样,不要使用“print”,使用sys.stdout.write()-并且不要忘记“\n”。当然,这只在多次打印时才相关。
正如S.Mark建议的,使用psyco。它既适用于Spoj的python2.5也适用于python2.6(测试一下,它就在那里,而且很容易发现:使用psyco的解决方案通常有大约35MB的内存使用偏移)。这很简单:只需在“import sys”:import psyco;psyco.full()之后添加即可。
正如Justin所建议的,将代码(psyco咒语除外)放在一个函数中,并在代码末尾简单地调用它。
有时,创建列表并检查其长度可能比创建列表并添加其组件更快。
支持列表理解(和生成器表达式,如果可能的话)而不是“for”和“while”。对于某些构造,map/reduce/filter还可以加快代码的速度。

根据这些指导方针,我成功地通过了无遗嘱。不过,仍在测试替代方案。

• 6 楼

Justin Peel 14 年前

嘿,我知道在规定的时间内。我使用了以下方法:

psyco和python 2.5。
一个简单的循环,其中包含一个变量来保持计数
我的代码都在我调用的main()函数(psyco导入除外)中。

最后一个就是造成差异的原因。我相信这和能见度变化有关,但我不完全确定。我的时间是10.81秒。如果你能理解列表,你可能会更快。

编辑:

通过列表理解,我的时间降到了8.23秒。接电话 from sys import stdin, stdout 里面的功能剃了一点,使我的时间下降到8.12秒。

登录后回复