python之如何优化这个python问题_编程设计

Here是问题所在。我的解决方案是:

import sys 
LIST_ITEM = [] 
NUMBER_OF_TEST_CASES = int(raw_input()) 
def non_decreasing(my_list): 
    if len(my_list) < 2: 
        return my_list 
    my_list.sort() 
    return my_list 
 
if __name__ == "__main__": 
    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0: 
        sys.exit() 
 
    for val in range(1, NUMBER_OF_TEST_CASES+1): 
        x = int(raw_input()) 
 
        if x >= 1000001 or x<0: 
            sys.exit() 
        else: 
            LIST_ITEM.append(x) 
    values =  non_decreasing(LIST_ITEM) 
    for i in values: 
        print i

但它告诉我 Time Limit Exceeded。 Here is my solution link

请您参考如下方法:

编辑:该死，显然你不应该被骗？这改变了一切，而且您当前的代码无论如何都无法正常工作。现在留下我的旧答案......

简单的答案就是剖析它!我生成的数据是:

import random 
out = open('foobar.txt', 'w') 
 
total = random.randint(100000, 1e6) 
out.write('%s\n' % total) 
 
for x in xrange(total): 
    out.write('%s\n' % random.randint(0, 1e6))

然后我用命令进行了测试:time python -m cProfile -o foo.profile foo.py < foobar.txt > fooout.txt && gprof2dot -f pstats foo.profile | dot -Tpng -o foo_profile.png .使用 gprof2dot 生成这个漂亮的图形工具并报告运行时间(在我的系统上有 266k 输入行时 1.9 秒)。 sort -n foobar.txt > foo_sorted.txt是我的黄金标准，约为 0.41 秒。

因此您可以看到，44.81% 的时间花在基本代码本身上，38.82% 花在 raw_input 上，14% 花在排序上。

那么接下来我们开始优化

首先是将您的代码放入一个方法中。只需添加一个 def main()围绕你所有的代码，最后 if __name__ == '__main__': main() .对我来说，这将运行时间缩短了大约 5%，降至 1.8 秒，并将 raw_input 移到了我们负载的最高百分比。

让我们看看是否可以减少它。也许直接使用 sys.stdin 替换 raw_input？我假设 raw_input 是为交互式使用而设计的，并且可能没有很好地描述它，因为它(可能)不适合大量使用。通过将 raw_input 替换为 sys.stdin.readline() 之类的东西，我们应该使用更高效的代码路径。对我来说，这使运行时间从 1.8 秒减少到 0.952 秒。节省一半!现在是代码和配置文件输出。

import sys  
 
def non_decreasing(my_list): 
    if len(my_list) < 2: 
        return my_list 
    my_list.sort() 
    return my_list 
 
def main(): 
    LIST_ITEM = [] 
    NUMBER_OF_TEST_CASES = int(sys.stdin.readline().strip()) 
 
    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0: 
        sys.exit() 
 
    for x in sys.stdin: 
        x = int(x.strip()) 
 
        if x >= 1000001 or x<0: 
            sys.exit() 
        else: 
            LIST_ITEM.append(x) 
    values =  non_decreasing(LIST_ITEM) 
    for i in values: 
        print i 
 
if __name__ == '__main__': 
    main()

所以这是一个好的开始。我们现在的运行时间还不到原来运行时间的一半。让我们看看现在慢的是什么。主要功能，sort，strip()，和append。也许我们可以在 main 中优化一些东西？好吧，我注意到我们正在一行一行地打印出来。我们可以用一个 sys.stdout.write() 把它换掉，看看是否有帮助吗？我试过 sys.stdout.writelines([str(x) for x in values])而且它实际上看起来更慢，所以我猜 print 非常高效。让我们坚持下去。

我们还能减少什么？也许if x >= 1000001 or x<0:陈述？完全有必要吗？看起来我们可以通过删除它轻松地摆脱百分之几秒。

还有什么？也许整个 non_decreasing 是不必要的，我们可以只使用 LIST_ITEM.sort() 吗？我想你的检查和额外的函数调用实际上并没有加快任何速度。是的，这加快了一点点!

理想情况下，此时我们会做一些事情，比如不从输入中去除换行符，将其排序为字符串，然后将其写出。不幸的是，这没有得到所需的排序:(所以让我们尝试一些替代方法

for x in sys.stdin: values.append(x[:-1])
x.rstrip()
x.rstrip('\n')
values = sys.stdin.split('\n')
values = sys.stdin.read().splitlines()
values = sys.stdin.readlines()

在我的测试中，#1 上的一个变体最快并保持正确性，约为 .783 秒。这是我的最终代码:

import sys 
 
def main(): 
    NUMBER_OF_TEST_CASES = int(sys.stdin.readline().strip()) 
    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0: 
        sys.exit() 
 
    values = [int(x) for x in sys.stdin.readlines()] 
    values.sort() 
    for i in values: 
        print i 
 
if __name__ == '__main__': 
    main()

最后的 gprof2dot 配置文件信息...