59

重複の可能性:
Python で浅いリストをフラット化する Python
でリストの (不規則な) リストをフラット化する

編集：問題はそれを行う方法ではありません-これは他の質問で議論されています-問題は、最も速い方法はどれですか?

以前に解決策を見つけましたが、任意の長さの他のリストを含むリストを平坦化する最速の解決策は何だろうと思っています。

例えば：

[1, 2, [3, 4, [5],[]], [6]]

次のようになります。

[1,2,3,4,5,6]

無限に多くのレベルが存在する可能性があります。一部のリスト オブジェクトは文字列にすることができますが、出力リストで連続する文字にフラット化してはなりません。

4

3 に答える 3

81

文字列に優しい再帰的アプローチを次に示します。

nests = [1, 2, [3, 4, [5],['hi']], [6, [[[7, 'hello']]]]]

def flatten(container):
    for i in container:
        if isinstance(i, (list,tuple)):
            for j in flatten(i):
                yield j
        else:
            yield i

print list(flatten(nests))

戻り値：

[1, 2, 3, 4, 5, 'hi', 6, 7, 'hello']

これは、速度やオーバーヘッドの使用を保証するものではありませんが、役立つことが期待される再帰的なソリューションを示していることに注意してください。

于 2012-05-30T21:18:01.510 に答える
25

再帰的である必要はありません。実際、関数呼び出しに伴うオーバーヘッドのために、反復ソリューションの方が高速なことがよくあります。これは、私がしばらく前に書いた反復バージョンです。

def flatten(items, seqtypes=(list, tuple)):
    for i, x in enumerate(items):
        while i < len(items) and isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
    return items

この特定の実装のパフォーマンスをテストしていませんが、多くのメモリを移動する可能性があるすべてのスライス割り当てのために、おそらくそれほど優れていません。それでも、再帰的でなければならない、またはそのように書く方が簡単だと思い込まないでください。

この実装には、再帰的なソリューションが常に行うように、コピーを返すのではなく、リストを「その場で」フラット化するという利点があります。これは、メモリが不足している場合に役立ちます。フラット化されたコピーが必要な場合は、フラット化するリストの浅いコピーを渡すだけです。

flatten(mylist)                # flattens existing list
newlist = flatten(mylist[:])   # makes a flattened copy

また、このアルゴリズムは再帰的ではないため、Python の再帰制限によって制限されません。ただし、これが事実上機能することはないと確信しています。

try2021 編集: リストの末尾のチェックは/で処理したほうがよいとexcept思います。なぜなら、それは 1 回しか行われず、メイン ループからテストを除外するとパフォーマンスが向上する可能性があるためです。それは次のようになります。

def flatten(items, seqtypes=(list, tuple)):
    try:
        for i, x in enumerate(items):
            while isinstance(items[i], seqtypes):    
                items[i:i+1] = items[i]
    except IndexError:
        pass
    return items

アクセスする代わりに、x返された byを使用するようにさらに微調整すると、これが得られます。これは、リストのサイズと構造に応じて、最初のバージョンよりもわずかにまたは大幅に高速です。enumerateitems[i]

def flatten(items, seqtypes=(list, tuple)):
    try:
        for i, x in enumerate(items):
            while isinstance(x, seqtypes):    
                items[i:i+1] = x
                x = items[i]
    except IndexError:
        pass
    return items
于 2012-05-30T20:52:33.547 に答える
9

この関数は、再帰を使用せずに、ネストされた反復可能なコンテナーをすばやくフラット化できる必要があります。

import collections

def flatten(iterable):
    iterator = iter(iterable)
    array, stack = collections.deque(), collections.deque()
    while True:
        try:
            value = next(iterator)
        except StopIteration:
            if not stack:
                return tuple(array)
            iterator = stack.pop()
        else:
            if not isinstance(value, str) \
               and isinstance(value, collections.Iterable):
                stack.append(iterator)
                iterator = iter(value)
            else:
                array.append(value)

約 5 年後、この問題に関する私の意見は変わりました。

def main():
    data = [1, 2, [3, 4, [5], []], [6]]
    print(list(flatten(data)))


def flatten(iterable):
    iterator, sentinel, stack = iter(iterable), object(), []
    while True:
        value = next(iterator, sentinel)
        if value is sentinel:
            if not stack:
                break
            iterator = stack.pop()
        elif isinstance(value, str):
            yield value
        else:
            try:
                new_iterator = iter(value)
            except TypeError:
                yield value
            else:
                stack.append(iterator)
                iterator = new_iterator


if __name__ == '__main__':
    main()
于 2012-05-30T21:24:07.077 に答える