代码之家 › 专栏 › 技术社区 › Karl Knechtel

itertools与生成器表达式的展平和重复-我们如何解释这些计时结果?

generator-expression itertools performance python

Karl Knechtel · 技术社区 · 4 年前

this question ,我决定尝试一些性能测试。我设置的任务稍微简单一点-给定一个源代码列表 A ,我们希望创建一个lazy iterable,它将a的每个元素重复N次:

def test(implementation):
    A, N = list('abc'), 3
    assert list(implementation(A, N)) == list('aaabbbccc')

from itertools import chain, repeat, starmap
from timeit import timeit

flatten = chain.from_iterable

def consume(iterable):
    for _ in iterable:
        pass

# FAST approaches
def tools(original, count):
    return flatten(map(repeat, original, repeat(count)))

def tools_star(original, count):
    return flatten(starmap(repeat, zip(original, repeat(count))))

def mixed(original, count):
    return flatten(repeat(a, count) for a in original)

# SLOW approaches
def mixed2(original, count):
    return (x for a in original for x in repeat(a, count))

def explicit(original, count):
    for a in original:
        for _ in range(count):
            yield a

def generator(original, count):
    return (a for a in original for _ in range(count))

def mixed3(original, count):
    return flatten((a for _ in range(count)) for a in original)

if __name__ == '__main__':
    for impl in (tools, tools_star, mixed, mixed2, explicit, generator, mixed3):
        for consumption in (consume, list):
            to_time = lambda: consumption(impl(list(range(1000)), 1000))
            elapsed = timeit(to_time, number=100)
            print(f'{consumption.__name__}({impl.__name__}): {elapsed:.2f}')

下面是我的机器上计时结果的三个示例:

consume(tools): 1.10
list(tools): 2.96
consume(tools_star): 1.10
list(tools_star): 2.97
consume(mixed): 1.11
list(mixed): 2.91
consume(mixed2): 4.60
list(mixed2): 6.53
consume(explicit): 5.45
list(explicit): 8.09
consume(generator): 5.98
list(generator): 7.62
consume(mixed3): 5.75
list(mixed3): 7.67

consume(tools): 1.10
list(tools): 2.88
consume(tools_star): 1.10
list(tools_star): 2.89
consume(mixed): 1.11
list(mixed): 2.87
consume(mixed2): 4.56
list(mixed2): 6.39
consume(explicit): 5.42
list(explicit): 7.24
consume(generator): 5.91
list(generator): 7.48
consume(mixed3): 5.80
list(mixed3): 7.61

consume(tools): 1.14
list(tools): 2.98
consume(tools_star): 1.10
list(tools_star): 2.90
consume(mixed): 1.11
list(mixed): 2.92
consume(mixed2): 4.76
list(mixed2): 6.49
consume(explicit): 5.69
list(explicit): 7.38
consume(generator): 5.68
list(generator): 7.52
consume(mixed3): 5.75
list(mixed3): 7.86

由此我得出以下结论:

itertools 工具提供了很大的性能提升,但前提是我们使用它们 二者都 “展平”迭代器( itertools.chain.from_iterable 而不是通过嵌套的 for 和生成子序列( itertools.repeat 而不是 range repeat 只提供了一个小的改进,并且只使用 chain.from_iterable 实际上似乎让事情变得更糟。
itertools公司 map ,或使用 itertools.starmap . (这并不奇怪,因为这里只发生O(len(A))操作,而不是O(len(A)*N)。这个 starmap 这种方法很难使用,而且肯定不是我推荐的方法,但是我把它包括进来是因为最初的激励讨论中的代码使用了它。)
list(explicit) 两次运行的结果)尽管它们对于快速方法似乎更加一致。这是特别奇怪的,因为我总结的结果,从多个列表创建在每个测试。

itertools公司 ? 我们如何解释这些计时结果?尤其奇怪的是和这里不提供增量性能好处,而是完全依赖于彼此。名单建设是怎么回事?在每种情况下增加的开销是不是都是一样的(重复地将相同的元素序列附加到一个空列表中)?

0 回复 | 直到 4 年前

Shadows In Rain 4 年前

它 主要地

- 但是嵌套如此多的itertools会增加很小但可以测量的开销。
  - I 在下表中。
一个循环仅仅是少数操作码中的1000个。
嵌套循环的数量高达1000000个。
repeat 很少有操作码比从 range 在屈服之前。
- Y 在下表中。
explicit 和 generator
- G 在下表中。

以下是我的结果:

方法	复杂性(仅限解释器)	列表	消费
工具	`O(0) + I`		0.09
	`O(0)+I`	0.21
混合的	`O(N)`	0.20	0.09
混合2	`O(NÂ²)`	0.54	0.47
明确的	`O(NÂ²) + Y`	0.64
发电机	`O(N)+Y`	0.64
工具	`O(NÂ²) + G`	0.71

似乎很有说服力。

我还对代码进行了一些修改,以改进计时方法和可读性。

PRODUCERS = (tools, tools_star, mixed, mixed2, explicit, generator, mixed3)
CONSUMERS = (list, consume)
N = 1000
SAMPLES = 50
BATCH = 10

if __name__ == '__main__':
    for consumer in CONSUMERS:
        print(f"{consumer.__name__}:")
        for producer in PRODUCERS:
            to_time = lambda: consumer(producer(list(range(N)), N))
            elapsed = timeit.repeat(to_time, repeat=SAMPLES, number=BATCH)
            emin = min(elapsed) # get rid of the random fluctuations for the best theoretical time
            print(f'{emin:02.2f} | {producer.__name__}')
        print()