2008年10月1日水曜日

Python で flatten - ネストしたリストをフラットにする

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つのリストにして返す。これは再帰的に呼び出されたときに、呼び出し元にリストを返し、他のリストと結合させるため。

上記を実行した結果は、以下のようになる。

[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 ジェネレータ

そして、次のようなジェネレータの動作について考える。

  1. piyo ジェネレータに hoge ジェネレータを渡し、
  2. piyo ジェネレータから hoge ジェネレータを呼出すためには、
  3. next () の呼出しを 2 回呼ばなくてはならない。
def hoge():
    yield "hoge"

def piyo(g):
    yield g

print piyo(hoge()).next().next()

 

gflatten 関数の見直し

これを前提に、上記の gflatten 関数を見直す。

次のように、一つの要素 100 があるリストに対して、gflatten関数を適用したとき、

  1. [100] はリストなので、for 文において、 gflatten(100) が実行される。
  2. 再帰呼出しがされたので、gflatten(100) が独立した文脈で実行される。今度は引数が値なので、 yield 100 が実行。これは、next() の呼出しで 100 が返されるジェネレータが作成されたということ。
  3. gflatte(100) の呼出しに戻り、 for 文がジェネレータの next() を呼出し、e に 100 が渡される。これで next() を呼出すと 100 が返されるジェネレータが作成された。
  4. 呼出し元の list 関数において、ジェネレータの next() 呼出しによって値が取り出される。

多分、このような動作かな… QQQ

081001-001