3

我得到了一些非常令人惊讶的结果，这似乎表明将迭代器包装在列表中并获得它的长度比使用 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
4

3 回答 3

6

不幸的是，你rle_walk有一个错误；它接受参数gen但应该接受参数data，所以它在错误的输入上运行。rle_walk此外，使用内联工作的 lambda也是不公平的rle_list。像这样重写：

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 的必要条件）。

于 2012-07-06T09:50:09.490 回答
2

当我重写rle_walk为

def rle_walk(gen):
    return [(ch, sum(1 for _ in ich)) for ch, ich in groupby(gen)]

那么它比基于列表的版本更快。

计时（使用 IPython）：

>>> def rle_walk(gen):
...     ilen = lambda gen : sum(1 for x in gen)
...     return [(ch, ilen(ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 94.3 us per loop
>>> def ilen(x): return sum(1 for _ in x)
... 
>>> def rle_walk(gen):
...     return [(ch, ilen(ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 93.4 us per loop
>>> def rle_walk(gen):
...     return [(ch, sum(1 for _ in ich)) for ch,ich in groupby(gen)]
... 
>>> %timeit rle_walk(data)
10000 loops, best of 3: 83.8 us per loop
>>> def rle_list(data):
...     return [(k, len(list(g))) for k,g in groupby(data)]
... 
>>> %timeit rle_list(data)
10000 loops, best of 3: 123 us per loop

（请注意，您正在喂食data而不是gento groupbyin rle_walk。）

于 2012-07-06T09:46:39.793 回答
2

Python（与大多数动态语言一样）中的函数调用开销非常高。

来自Python 性能提示：

Python 中的函数调用开销相对较高，尤其是与内置函数的执行速度相比。这强烈表明，在适当的情况下，函数应该处理数据聚合。

在迭代器版本中，您可以调用函数ilen()，然后使用 Python 迭代来构建 1 列表。

在列表版本中，您有两个对内置函数的调用，list()并且len(). 内置作为本地代码执行，从高度优化的 C 编译。最重要的是，使用list()内置的将迭代器转换为列表的迭代是使用此本地代码在内部完成的。

于 2012-07-06T09:49:39.863 回答