6

yield fromPython 3 はセマンティクスをもたらします。私が理解している限り、それは最も外側のジェネレーターに渡されるはずであり、その場合、このコードは線形であると予想され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、計算時間は約 4 倍長くなり、平坦化の長さは 2 次であることを示唆していLます。yield fromコードが各要素を一度だけ訪問し、キーワードが内部ジェネレーターから用語がリストに収集される場所に値を直接送信する必要があるため、なぜそうなるのか理解できません。

これは単に意図したものではないバグですか、それとも使い方が間違っていますか? PythonでO(N)フラット化を行う良い方法はありますか?

4

1 に答える 1

14

yield fromと同様for item in x: yield xに、は線形です。ただし、関数呼び出しは遅く、 の入れ子のため、lN を 2 倍にすると、項の数が 2 倍になるだけでなく、必要な呼び出しの数も 2 倍になります。関数のオーバーヘッド自体など、呼び出しの数に応じてスケーリングするもの。したがって、再帰、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 に答える