为什么步行迭代器比将其转换为列表并查询长度要慢？

Question

我得到了一些非常令人惊讶的结果,这些结果似乎表明将迭代器包装在列表中更有效,并且与使用lambda行走它相比,获得它的长度.这怎么可能？直觉会建议分配所有这些列表会更慢.

是的 - 我知道你不能总是这样做,因为迭代器可以是无限的.:)

from itertools import groupby
from timeit import Timer

data = "abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac" 

def rle_walk(gen):
    ilen = lambda gen : sum(1 for x in gen)
    return [(ch, ilen(ich)) for ch,ich in groupby(data)]

def rle_list(data):
    return [(k, len(list(g))) for k,g in groupby(data)]

# randomy data
t = Timer('rle_walk("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

# chunky blocks
t = Timer('rle_walk("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

1.42423391342
0.145968914032
1.41816806793
0.0165541172028

Answer 1

不幸的是你rle_walk有一个bug; 它需要参数gen但应该采用参数data,因此它在错误的输入上运行.另外,rle_walk使用rle_list内联工作的lambda 是不公平的.像这样重写:

def rle_walk(data):
    return [(k, sum(1 for _ in g)) for k, g in groupby(data)]

def rle_list(data):
    return [(k, len(list(g))) for k, g in groupby(data)]

和测试:

data_block = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc"
data_random = "abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac"
print [[Timer('r("{data}")'.format(data=data),
              "from __main__ import {r} as r; gc.enable()".format(r=r)).timeit(1000)
        for r in ['rle_walk', 'rle_list']]
        for data in (data_block, data_random)]

给

[[0.02709507942199707, 0.022060155868530273],
 [0.12022995948791504, 0.16360306739807129]]

所以我们看到它walk比list块状数据略慢,但随机数据略快.我猜的原因是,与列表构造函数相比,生成器(在Python中)会产生开销; 并且30项目列表的内存开销太小而不会施加任何重大惩罚.

拆卸这些功能提供了一些见解:

>>> dis.dis(lambda g: (1 for _ in g))
  1           0 LOAD_CONST               0 (<code object <genexpr> at 0x2b9202a6fe40, file "<stdin>", line 1>)
              3 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (g)
              9 GET_ITER            
             10 CALL_FUNCTION            1
             13 RETURN_VALUE        
>>> dis.dis((lambda g: (1 for _ in g)).func_code.co_consts[0])
  1           0 SETUP_LOOP              18 (to 21)
              3 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                11 (to 20)
              9 STORE_FAST               1 (_)
             12 LOAD_CONST               0 (1)
             15 YIELD_VALUE         
             16 POP_TOP             
             17 JUMP_ABSOLUTE            6
        >>   20 POP_BLOCK           
        >>   21 LOAD_CONST               1 (None)
             24 RETURN_VALUE        
>>> dis.dis(lambda g: len(list(g)))
  1           0 LOAD_GLOBAL              0 (len)
              3 LOAD_GLOBAL              1 (list)
              6 LOAD_FAST                0 (g)
              9 CALL_FUNCTION            1
             12 CALL_FUNCTION            1
             15 RETURN_VALUE        

生成器形式的更大代码量将产生一些影响; 虽然列表形式具有用于构造一次性列表的O(log n)因子,但是它将在循环各种迭代器时由k*O(n)因子支配.要做的一件事就是内存分配很快,至少对于单线程环境中的小(子页面)分配(CPython必须是GIL).