6

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) 展平的好方法？

4

1 回答 1

14

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

时间与嵌套的简单图

于 2012-09-08T14:40:03.103 回答