「Python でリスト内のリストを連結」 のつづき
1. Ruby の flatten メソッドと同じ関数を書きたい
前回、Python で「リスト内のリストを結合する」処理を書いた。
Ruby で「ネストしたリストを結合する」メソッドは Array#flatten 。Ruby の flatten は、どれだけネストが深くてもフラットな配列にして返す。また、リスト内の要素のネストの深さが異なっていても、フラットにしてくれる。
irb(main):001:0> [1,[2,3,[4],5],6].flatten => [1, 2, 3, 4, 5, 6]
このような Ruby の flatten メソッドと同じ関数を、Python で書きたい。
2. ネストしたリストを平坦化する関数 flatten
「ネストしたリスト」に対する処理を書いたことがある。
def map2(L):
if isinstance(L, list):
if L == []:
return []
else:
return [map2(L[0])] + map2(L[1:])
else:
return L
print map2(L)
これを元にコードを考える。
def flatten(L):
if isinstance(L, list):
if L == []:
return []
else:
return flatten(L[0]) + flatten(L[1:])
else:
return [L]
L = [1,[21,22],3,[41,[421,422],43,44],5]
print flatten(L)
参考にしたコードとの違いは、対象がリストの場合の処理。リストの先頭要素に対する、関数の呼出し部分が異なる。この関数 flatten では、返ってきた結果をリストにしていない。もし、リストにしたら、ネストした構造を保ってしまう。
リストでない場合は、要素１つのリストにして返す。これは再帰的に呼び出されたときに、呼び出し元にリストを返し、他のリストと結合させるため。
上記を実行した結果は、以下のようになる。
[1, 21, 22, 3, 41, 421, 422, 43, 44, 5]
3. リストに対する処理を reduce で置き換える
前回と同じように、リストの要素に対する処理を、組込み関数 reduce に置き換えて実装する。
def flatten2(L):
if isinstance(L, list):
return reduce(lambda a,b: a + flatten(b), L, [])
else:
return [L]
print flatten2(L)
4. ジェネレータを使って定義する
次に、ジェネレータを使って定義してみる。
Python で順列を生成するときに読んだ
を参考にした。
def gflatten(L):
if isinstance(L, list):
for i in xrange(len(L)):
for e in gflatten(L[i]):
yield e
else:
yield L
print list(gflatten(L))
ジェネレータを使うと、動作のイメージがしにくい。 (+_+) なぜこれで動いているんだろう？
デバッガを利用して動作を見ると、実際に値を取得するために yield が 2 回呼出されているのが確認できる。あたかも、yield 間で値を受渡しているような感じに見える。
ジェネレータについて再考
これを理解するために、ジェネレータについて復習。
例えば、次の 2 つのジェネレータを作成。
- “hoge” と出力する hoge ジェネレータ
- ジェネレータを受けとると、ジェネレータを返す piyo ジェネレータ
そして、次のようなジェネレータの動作について考える。
- piyo ジェネレータに hoge ジェネレータを渡し、
- piyo ジェネレータから hoge ジェネレータを呼出すためには、
- next () の呼出しを 2 回呼ばなくてはならない。
def hoge():
yield "hoge"
def piyo(g):
yield g
print piyo(hoge()).next().next()
gflatten 関数の見直し
これを前提に、上記の gflatten 関数を見直す。
次のように、一つの要素 100 があるリストに対して、gflatten関数を適用したとき、
- [100] はリストなので、for 文において、 gflatten(100) が実行される。
- 再帰呼出しがされたので、gflatten(100) が独立した文脈で実行される。今度は引数が値なので、 yield 100 が実行。これは、next() の呼出しで 100 が返されるジェネレータが作成されたということ。
- gflatte(100) の呼出しに戻り、 for 文がジェネレータの next() を呼出し、e に 100 が渡される。これで next() を呼出すと 100 が返されるジェネレータが作成された。
- 呼出し元の list 関数において、ジェネレータの next() 呼出しによって値が取り出される。
多分、このような動作かな… QQQ
0コメント:
コメントを投稿