Python 3.3 的 yield 来自

Question

Python 3 带来了 yield from语义。据我所知，它应该屈服于最外层的生成器，在这种情况下，我希望这段代码在 N 中是线性的。

from collections import Iterable

def flatten(L):
  for e in L:
    if isinstance(e, Iterable):
      yield from flatten(e)
    else:
      yield e 

N = 100
L = [-1]
for i in range(N):
  L = [i, [L], i]
for i in range(100):
  f = list(flatten(L))
print(len(f))

如果我设置 N=200 但是计算时间大约长四倍，这表明 flatten 是 L 长度的二次方。我不明白为什么会这样，因为代码只访问每个元素一次，yield from 关键字应该将值直接从内部生成器发送到将术语收集到列表中的位置。

这是一个错误，根本不是故意的，还是我用错了？有没有一种在 Python 中进行 O(N) 扁平化的好方法？

Answer 1

yield from，就像for item in x: yield x一样，是线性的。但是，函数调用速度很慢，并且由于 l 中的嵌套，当您将 N 加倍时，不仅是将项数加倍，而且还使所需的调用次数加倍。任何与调用次数成比例的东西，比如函数开销本身，尤其是。由于递归，任何 yield from 开销，for 循环初始化开销，无论如何，都会因此导致问题。如果这是正确的，那么我们期望具有相同数量元素且没有嵌套的列表将是线性的，中间嵌套将介于两者之间，并且大量嵌套将非常慢。这就是我们所看到的:

import timeit

s = """

from collections import Iterable

def flatten(l):
   for e in l:
       if isinstance(e, Iterable):
           yield from flatten(e)
       else:
           yield e 

def build_lots(N):
    l = [-1]
    for i in range(N):
        l = [i, [l], i]
    return l

def build_some(N):
    l = [-1]
    for i in range(N):
        l = [i]+l+[i] if i % 2 else [i,[l],i]
    return l

def build_none(N):
    return range(2*N+1)

"""

def get_time(size, which_build, n=100):
    setup = s + "l = build_{}({});".format(which_build, size)
    ans = timeit.Timer(setup=setup, stmt="z=list(flatten(l))").timeit(n)
    return ans

print('length', 'none','some','lots')
for w in range(0, 500, 50):
    print(2*w+1, 
          get_time(w, 'none'), 
          get_time(w, 'some'),
          get_time(w, 'lots'))

产生

length none some lots
1 0.0012789969332516193 0.0006600483320653439 0.000653265044093132
101 0.030214487109333277 0.06863495009019971 0.10554128512740135
201 0.05980244372040033 0.188231083098799 0.3237948380410671
301 0.08960435865446925 0.3752179825678468 0.6493003228679299
401 0.11986956000328064 0.6066137161105871 1.147628225851804
501 0.14737469609826803 0.9323012446984649 1.7087256000377238
601 0.18555369088426232 1.2575508910231292 2.2957410947419703
701 0.20820995513349771 1.712264522910118 3.094764341134578
801 0.23618148919194937 2.100640726275742 4.079551971051842
901 0.26863432209938765 2.617169467266649 4.858607416041195