与列表相比,在生成器上多次迭代的速度

Question

我预计在多循环的情况下,列表迭代将比使用生成器快得多,我的代码表明这是错误的.

我的理解是(通过操作我的意思是任何定义元素的表达式):

• 列表需要初始化n个操作
• 但是然后列表上的每个循环只是从内存中获取一个元素
• 因此,列表上的m循环只需要n次操作
• 生成器不需要初始化任何操作
• 然而,循环生成器在fly中运行操作
• 因此,生成器上的一个循环需要n次操作
• 但是m生成器上的循环需要nxm操作
  

我使用以下代码检查了我的期望:

from timeit import timeit

def pow2_list(n):
    """Return a list with powers of 2"""

    results = []

    for i in range(n):
        results.append(2**i)

    return results

def pow2_gen(n):
    """Generator of powers of 2"""

    for i in range(n):
        yield 2**i

def loop(iterator, n=1000):
    """Loop n times over iterable object"""

    for _ in range(n):
        for _ in iterator:
            pass

l = pow2_list(1000) # point to a list
g = pow2_gen(1000)  # point to a generator


time_list = \
    timeit("loop(l)", setup="from __main__ import loop, l", number=10)

time_gen = \
    timeit("loop(g)", setup="from __main__ import loop, g", number=10)

print("Loops over list took: ", time_list)
print("Loops over generator took: ", time_gen)

结果让我感到惊讶......

Loops over list took:  0.20484769299946493
Loops over generator took:  0.0019217690005461918

以某种方式使用生成器看起来比列表快得多,即使循环超过1000次.在这种情况下,我们谈论的是两个数量级!为什么？

编辑:

谢谢你的回答.现在我看到了我的错误.我错误地认为生成器从一个新循环开始,如范围:

>>> x = range(10)
>>> sum(x)
45
>>> sum(x)
45

但这很天真(范围不是发电机......).

关于可能的重复注释:我的问题涉及生成器上的多个循环,这在另一个线程中没有解释.

Answer 1

你的生成器实际上只循环一次.一旦创建pow2_gen,g存储发电机; 第一次通过loop,这个发生器被消耗,并发出StopIteration.其他时间loop,next(g)(或g.next()在Python 2中)只是继续抛出StopIteration,因此,实际上g代表一个空序列.

为了使比较更公平,每次循环时都需要重新创建生成器.

你接近这种方式的另一个困难是,你正在调用append构建列表,这可能是构建列表的最慢方法.更常见的是,列表是使用列表推导构建的.

以下代码让我们更仔细地分辨时间. create_list并create_gen使用列表推导和生成器表达式分别创建列表和生成器. time_loop就像是你的loop方法,而time_apply为的一个版本loop是重新创建通过循环迭代每次.

def create_list(n=1000):
    return [2**i for i in range(n)]

def create_gen(n=1000):
    return (2**i for i in range(n))

def time_loop(iterator, n=1000):
    for t in range(n):
        for v in iterator:
            pass

def time_apply(create_fn, fn_arg, n=1000):
    for t in range(n):
        iterator = create_fn(fn_arg)
        time_loop(iterator, 1)

print('time_loop(create_list): %.3f' % timeit("time_loop(create_list(1000))",
                                              setup="from __main__ import *",
                                              number=10))

print('time_loop(create_gen): %.3f' % timeit("time_loop(create_gen(1000))",
                                             setup="from __main__ import *",
                                             number=10))

print('time_apply(create_list): %.3f' % timeit("time_apply(create_list, 1000)",
                                               setup="from __main__ import *",
                                               number=10))

print('time_apply(create_gen): %.3f' % timeit("time_apply(create_gen, 1000)",
                                              setup="from __main__ import *",
                                              number=10))

我的方框上的结果表明,构建list(time_apply(create_list))与构建gen​​erator(time_apply(create_gen))的时间相似(或者甚至更快).

time_loop(create_list): 0.244
time_loop(create_gen): 0.028
time_apply(create_list): 21.190
time_apply(create_gen): 21.555

你可以看到你在问题中记录的相同效果,这time_loop(create_gen)比你快一个数量级time_loop(create_list).同样,这是因为创建的生成器只被迭代一次,而不是列表上的许多循环.

正如您所假设的那样,构建一个列表并多次迭代它(time_loop(create_list))比time_apply(create_gen)在这个特定场景中多次迭代生成器()更快.

列表和生成器之间的权衡将在很大程度上取决于您创建的迭代器的大小.有1000个项目,我希望列表非常快.有100,000件物品,情况可能会有所不同.

print('create big list: %.3f' % timeit("l = create_list(100000)",
                                       setup="from __main__ import *",
                                       number=10))

print('create big gen: %.3f' % timeit("g = create_gen(100000)",
                                      setup="from __main__ import *",
                                      number=10))

我在这里得到:

create big list: 209.748
create big gen: 0.023

Python使用700到800 MB的内存来构建大型列表; 发电机几乎什么都没用.内存分配和垃圾清理在Python中计算成本很高,并且可以预测会使代码变慢; 生成器是一种非常简单的方法,可以避免吞噬机器的RAM,并且可以对运行时产生很大的影响.