如何优化这个Python问题？

Question

这里有一个问题，链接在这里。我的解决方案是：

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

但是它告诉我 超出时间限制。我的解决方案链接在这里

Answer 1

因为输入的数据值和大小限制在10^6，所以你可以简单地初始化一个包含10^6个值的数组，并记录哪些值出现过。这样一来，排序和查重就变得很简单了。

这种方法在开始时会有一些成本（初始化数组），但对于大数据量来说，这样做是值得的。

举个例子： import array from sys import stdin from itertools import repeat

low  = 1000001
high = -1
data = array.array('i', repeat(-1, 1000000))
count = int(stdin.readline().strip())

while count:
    v = int(stdin.readline().strip())
    count -= 1
    data[v] = v
    low  = min(v, low)
    high = max(v, high)

for v in xrange(low, high+1):
    if data[v] > 0:
        print v

注意，我使用了array，因为我们事先知道大小和类型，这样就可以避免使用list时的一些额外开销。

如果对内存使用有限制，可以使用位数组，这样可以减小data的大小，但在设置和遍历值时会增加一些额外的开销（和复杂性）。

Answer 2

别排序了！

只需要创建一个长度为1000000的全零数组（可以用numpy来做），然后遍历这个列表，每当遇到数字i，就把数组中第i个位置的值设为1，最后把所有不为零的值打印出来。

我觉得这样可以实现：

import numpy as np
import sys

nn = 1000000
a = np.zeros(nn+1, dtype=np.int)

for l in sys.stdin:
    a[np.int(l)]=1

for i in xrange(nn+1):
    if a[i]: print i

我想应该有办法加快输入输出的速度。

Answer 3

编辑：哎呀，看来你不应该有重复的内容？这改变了情况，而且你现在的代码也不太对。暂时保留我之前的回答吧……

简单的说就是，先进行性能分析！我用以下代码生成了数据：

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是为了交互使用设计的，可能没有经过很好的性能分析，因为它（可能）不适合重度使用。通过用sys.stdin.readline()替代raw_input，我们应该能走上更高效的代码路径。这样做让我运行时间从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()

所以这是个不错的开始。我们的运行时间已经不到原来的二分之一。接下来看看现在哪些地方还慢。主要函数、排序、strip()和append。也许我们可以在main中优化一下？我注意到我们是逐行打印的。能不能用一个sys.stdout.write()替代，看看效果如何？我试了sys.stdout.writelines([str(x) for x in values])，结果似乎更慢，所以我想print是非常高效的。那就继续用print吧。

还有什么可以减少的？也许if x >= 1000001 or x<0:这个判断？真的有必要吗？看起来我们可以轻松地通过去掉它节省几毫秒。

还有什么？也许整个非递减的检查都是多余的，我们可以直接用LIST_ITEM.sort()？我想你的检查和额外的函数调用并没有加快速度。没错，这样确实快了一点！

理想情况下，我们现在可以不去掉输入中的换行符，按字符串排序然后再写出结果。不幸的是，这样做并不能得到想要的排序 :( 所以我们来试试其他方法。

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

在我的测试中，变体#1是最快的，并且保持了正确性，约为0.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性能分析信息……