2014/01/29

Python Tips:多重リストをフラットにしたい

Pythonで多重リストをフラットにする(平滑化する)方法をご紹介します。

多重リストの階層が必ず2階層と決まっている場合には、リスト内包表記で次のように書くことができます。
a = [[1, 3], [5, 7], [9]]

def flatten(nested_list):
    """2重のリストをフラットにする関数"""
    return [e for inner_list in nested_list for e in inner_list]

flatten(a) 
# => [1, 3, 5, 7, 9]

リスト内包表記に頼らない方法としては extend 関数を使う方法があります。
def flatten_by_extend(nested_list):
    flat_list = []
    for e in nested_list:
        flat_list.extend(e)
    return flat_list

flatten_by_extend(a)
# => [1, 3, 5, 7, 9]

ただ、このextendを使ったやり方は内包表記を使ったやり方よりも遅いようです。そのあたりの議論がStack Overflowでなされています

深さがまちまちな多重リスト、たとえば次のようなリストがあるものとします。
b = [[1, 3], [[5]], [[7], 9]]
このようなリストをフラット化するには、深さ優先探索の要領で処理を行うとよいかと思います。

次の flatten_with_any_depth は、そんな任意の深さの多重リストをフラットにする関数です。
def flatten_with_any_depth(nested_list):
    """深さ優先探索の要領で入れ子のリストをフラットにする関数"""
    # フラットなリストとフリンジを用意
    flat_list = []
    fringe = [nested_list]

    while len(fringe) > 0:
        node = fringe.pop(0)
        # ノードがリストであれば子要素をフリンジに追加
        # リストでなければそのままフラットリストに追加
        if isinstance(node, list):
            fringe = node + fringe
        else:
            flat_list.append(node)

    return flat_list

flatten_with_any_depth([[1, 3], [[5]], [[7], 9]])


参考
Making a flat list out of list of lists in Python - Stack Overflow

0 件のコメント: