1

好的，所以无论如何我可能都不应该担心这一点，但是我有一些代码旨在通过一组过滤器和地图以及其他东西传递一个（可能很长，可能很短）的可能性列表，我想知道我的实现是否会表现良好。

作为我想做的事情类型的一个例子，考虑这个操作链：

  • 获取从 1 到 100 的所有数字
  • 只保留偶数
  • 平方每个数字
  • 生成所有对 [i, j] 与上面列表中的 i 和 [1, 2, 3, 4,5] 中的 j
  • 只保留 i + j > 40 的对

现在，在做了所有这些废话之后，我想通过这组对 [i, j] 来寻找满足某个条件的对。通常，解决方案是第一个条目，在这种情况下，我什至不看任何其他条目。但是，有时我必须消耗整个列表，而我找不到答案并且不得不抛出错误。

我想将我的“操作链”实现为一系列生成器，即每个操作迭代由前一个生成器生成的项目，并逐项“产生”自己的输出（如 SICP 流）。这样，如果我从不查看输出的最后 300 个条目，它们甚至不会被处理。我知道 itertools 提供了 imap 和 ifilter 之类的东西来执行我想要执行的许多类型的操作。

我的问题是：在我必须遍历所有可能性的情况下，一系列嵌套生成器是否会对性能造成重大影响？

4

3 回答 3

3

我尝试了两种实现，一种使用生成器，一种不使用生成器。我在 2.7 中对其进行了测试，因此range返回一个列表而不是迭代器。

这是实现

使用生成器

def foo1():
    data = ((a,b) for a in (i*i for i in xrange(1,101) if i%2) for b in [1,2,3,4,5] if a+b > 40)
    return list(data)

没有发电机

def foo2():
    result=[]
    for i in range(1,101):
        if i%2:
            i=i*i
            for j in [1,2,3,4,5]:
                if i+j > 40:
                    result+=[(i,j)]
    return result

混合两者以免附加列表

def foo3():
    data=[(a,b) for a in (i*i for i in range(1,101)) for b in [1,2,3,4,5] if a+b > 40] 
    return data

创建临时列表

def foo4():
    data=[(a,b) for a in [i*i for i in range(1,101)] for b in [1,2,3,4,5] if a+b > 40]
    return data

这是我的结果

>>> t1=timeit.Timer("foo1()","from __main__ import foo1")
>>> t2=timeit.Timer("foo2()","from __main__ import foo2")
>>> t3=timeit.Timer("foo3()","from __main__ import foo3")
>>> t4=timeit.Timer("foo4()","from __main__ import foo4")

>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10000)/10000)
100.95 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10000)/10000)
158.90 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t3.timeit(number=10000)/10000)
130.02 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t4.timeit(number=10000)/10000)
133.68 usec/pass
>>>

结论：

生成器表达式功能强大，您可以对其进行更大程度的优化。正如您在示例中看到的那样foo2，这是最慢的，它很难附加一个导致性能下降的列表。foo3并且foo4时间几乎相同，因此创建临时列表似乎不是瓶颈，因为它在整个迭代中只创建了一次。如果没有生成器，您很快就会遇到一些性能问题，例如附加列表或创建临时列表。因此，懒惰的评估出现在这些性能瓶颈上。

于 2012-04-13T16:06:51.460 回答
2

根据官方文档，使用生成器表达式基本上等同于调用imap它创建一个迭代器。（“生成器表达式产生一个新的生成器对象。 ”）没有明确讨论嵌套表达式是创建单独的（组合的）对象还是内部具有复杂逻辑的单个表达式，但是将自己想象为解释器实现者，嵌套对象似乎是最实现嵌套生成器表达式的直接方法。

然而，在决定什么会表现更好时，还有其他因素在起作用。我了解到，最小化短期对象的创建是性能的一个重要因素，而在 Python 中，当你这样做时有时很难注意到。

表现不佳：(f(x) for x in range(100)) # builds 100-element list

更好的性能：(f(x) for x in xrange(100)) # uses counting iterator

我在自己的实现中一直使用imap,ifilter和izipfromitertools模块，我发现它们表现良好。虽然这些的每次调用都会创建一个新的迭代器对象，但这是相当轻量级的，有点像一个列表，其中永远不会超过一个项目。此外，在 CPython 中，这些都是用 C 实现的，因此非常高效。

在幕后，在纯 Python 中实现的迭代器有一个next被调用来检索每个数据的方法。方法调用的成本不是很高，但也不是零。因此，如果您的代码将在必须尽可能优化的紧密循环中使用，以下是我的建议：

  • 绝对使用imap,ifilter并且izip在可能的情况下而不是map,filter并且zip在内存中构造结果列表并返回它们。如果您的代码使用基于列表的版本，您将通过更改为基于迭代器的版本看到很大的改进。
  • 该itertools模块包含其他函数，如takewhile, starmap,chain并且chain.from_iterable在链式迭代器实现中通常有用。
  • 与其链接多个应用程序，不如ifilter尽可能组合传入的函数。例如，代替ifilter(lambda v: v > 0, ifilter(lambda v: v % 3 == 0, data))，将过滤器组合为ifilter(lambda v: (v > 0) and (v % 3 == 0), data)。在某些情况下，重新排列操作顺序可能是有效的，以便您可以通过这种方式折叠它们。

  • 当您执行映射操作以实现副作用并且对结果不感兴趣时​​，您可以使用它来代替map避免结果在内存中累积：

    def consume(i):
  u'eat all contents of given iterator'
  while True:
    i.next()

consume(imap(side_effect, data))

最后，请注意其他可能会增加内存使用或重复创建和销毁对象的问题，从而给垃圾收集器带来压力。这实际上与迭代器没有任何关系，但它确实会影响性能。下面的函数在内存中创建一个 lambda 表达式，并在每次调用时将其丢弃：

def foo(data):
  return reduce(R, imap(bar, ifilter(lambda v: v % 5 == 0, data)))

修复它的一种方法（此方法每次仍将创建两个迭代器对象，这是必要的，但不是额外的 lambda 表达式）：

_mod5zero = lambda v: v % 5 == 0
def foo(data):
  return reduce(R, imap(bar, ifilter(_mod5zero, data)))

（注意：答案适用于 Python 2。在 Python 3map中，filter并zip返回迭代器。）

于 2012-04-13T16:01:11.113 回答
1

“嵌套”迭代器相当于迭代器实现的功能的组合，因此通常它们没有提出特别新颖的性能考虑。

请注意，由于生成器是惰性的，因此与重复分配一个序列以转换为另一个序列相比，它们也倾向于减少内存分配。

于 2012-04-13T16:10:28.360 回答