为什么代码1比代码2快？

Question

代码1:

n = int(input())
ls = []
for x in range(n):
    ls += [(input())]
ls.sort(key = int)
for x in ls:
    print (x)

代码2:

n = int(input())
ls = []
for x in range(n):
    ls += [int(input())]
ls.sort()
for x in ls:
    print (x)

这是我对HackerRank的“大排序”问题的解决方案：https://www.hackerrank.com/challenges/big-sorting

代码1没有给出超过错误的时间限制，而代码2给出了。

为什么代码1比代码2快？

Answer 1

代码比较慢，因为您现在需要将整数列表转换回字符串，而版本2则保留字符串版本，只转换为整数进行排序。

将整数转换回字符串也需要时间：

>>> import timeit
>>> timeit.timeit("str(235739630407432043190819704398)", number=10**7)
2.4063552810002875

我强烈怀疑，在某些测试中包含的排序值是很多的，而且非常非常大。

我也不会用就地扩展。使用列表理解代替：

ls = [input() for x in range(n)]

就我个人而言，我会使用sys.stdin上的迭代来比input()调用更快地读取；在这里，所有循环都委托给优化的C代码：

import sys
from itertools import islice

n = int(next(sys.stdin))
nums = sorted(map(str.strip, islice(sys.stdin, n)), key=int)
print(*nums, sep='\n')

(因为从stdin读取的最后一行没有换行符，所以不能指望所有行都有换行符，这样就更容易、更快地删除)。

将str.strip替换为int将再次导致超时。