巨大的输入 - 比列表理解更快的循环

Question

我正在尝试解决一个codechef初学者问题 - 巨大的输入测试.我的代码

a,b = [ int(i) for i in raw_input().split()]
print [input()%b==0 for i in range(a)].count(True)

得到超时.另一个使用基本for循环的解决方案似乎工作正常.

我相信列表理解比 - 循环更快.那为什么前者慢了？在这种情况下也会使用生成器减少使用的内存并更快地执行计算,如果是这样,我该怎么办呢？

Answer 1

为什么你认为列表理解比基本for循环更快？(提示:它们都使用相同的底层指令实现.)

您的代码将以某种方式执行,如下所示:

a, b = ...
temp = []
for i in range(a):
    temp.append(int(raw_input()) % b == 0)
print temp.count(True)

如您所见,它在内存中创建一个大型列表,迭代它以创建第二个列表,然后迭代第二个列表以创建计数.不需要创建列表.

a, b = ...
count = 0
for i in xrange(a):
    if int(raw_input()) % b == 0:
        count += 1
print count

一些编译器能够优化hylomorphisms以删除中间列表,但我知道没有Python实现能够做到这一点.所以你手动优化了.

注意:不要input在Python 2.x中使用,除非您知道自己在做什么.我已经更改了要使用的代码,int(raw_input())因为这是安全的,而且input()很危险.