この投稿では、5つの異なる方法でリストをフラット化する方法を説明します。それぞれの方法には長所と短所があり、さまざまなパフォーマンスがあります。このチュートリアルの終わりまでに、問題に最も適切な解決策を特定できるようになることを願っています。このチュートリアルで使用したPythonのバージョンは3.8で、私が使用したテストではpytest。

リストまたはジェネレーターの理解でリストを平坦化する

このようなリストの単純なリストが[[1, 3], [2, 5], [1]]あり、それをフラット化したいとします。つまり、このようにしたいのです[1, 3, 2, 5, 1]。それを行う最初の方法は、リスト/ジェネレーターの理解によるものです。すでにそれらに精通している人にとって、これは非常に簡単に聞こえるかもしれません。私たちがする必要があるのは、各サブリストを反復処理し、次にそれらの各サブリストを反復処理して、毎回単一の要素を生成することです。

次の関数は、引数としてリストを受け入れ、ジェネレーターを返します。その理由は、メモリ内にリスト全体を作成することを避けるためです。ジェネレーターを使用すると、オンデマンドで要素を作成できます。

すべてが期待どおりに機能することを確認するために、test_flatten単体テストで動作を表明できます。

def flatten_gen_comp(lst: List[Any]) -> Iterable[Any]:

"""Flatten a list using generators comprehensions."""

return (item

for sublist in lst

for item in sublist)

def test_flatten():

l = [[1, 3], [2, 5], [1]]

assert list(flatten_gen_comp(l)) == [1, 3, 2, 5, 1]

テストを実行すると、合格していることがわかります…

============================= test session starts ==============================

flatten.py::test_flatten PASSED [100%]

============================== 1 passed in 0.01s ===============================

Process finished with exit code 0

でリストを平坦化する sum

2番目の戦略は、少し型破りで、言うまでもなく、非常に「魔法のような」ものです。この関数sumを使用してリストをフラット化できることがわかりました。これを行うのは非常に単純で簡潔なので、空のリストに沿って引数としてリストを渡します。次の関数はそれを示しています。

このアプローチに興味がある場合は、おそらく聞いたことのない5つの非表示のPython機能で詳しく説明します。

def flatten_sum(lst: List[Any]) -> Iterable[Any]:

"""Flatten a list using sum."""

return sum(lst, [])

def test_flatten():

l = [[1, 3], [2, 5], [1]]

assert list(flatten_sum(l)) == [1, 3, 2, 5, 1]

そして、テストも合格します…

flatten.py::test_flatten PASSED

賢いように見えますが、本番環境で使用することはお勧めできません。後で説明するように、これはパフォーマンスの観点からリストをフラット化するための最悪の方法です。

を使用した平坦化 itertools.chain

3番目の方法はchain、itertoolsモジュールの関数を使用することです。一言で言えば、chain他のイテレータのシーケンスから単一のイテレータを作成します。この関数は、私たちのユースケースに完全に一致します。

公式ドキュメントchainから取得した 同等の実装は次のようになります。

def chain(*iterables):

# chain('ABC', 'DEF') –> A B C D E F

for it in iterables:

for element in it:

yield element

次に、次のようにリストをフラット化します。

def flatten_chain(lst: List[Any]) -> Iterable[Any]:

"""Flatten a list using chain."""

return itertools.chain(*lst)

def test_flatten():

l = [[1, 3], [2, 5], [1]]

assert list(flatten_chain(l)) == [1, 3, 2, 5, 1]

そして、テストパス…

[OMITTED]

….

flatten.py::test_flatten PASSED

…

[OMITTED]

不規則なリストのフラット化

私たちはこのようなリストがある場合はどうなるの[[1, 3], [2, 5], 1]か、これを[1, [2, 3], [[4]], [], [[[[[[[[[5]]]]]]]]]]？残念ながら、これらの前述のアプローチのいずれかを適用しようとすると、それはあまりうまくいきません。このセクションでは、そのための2つの独自のソリューション、1つは再帰的、もう1つは反復的ソリューションについて説明します。

再帰的アプローチ

平坦化の問題を再帰的に解決するということは、各アイテムを繰り返し処理し、要素が既に平坦化されているかどうかを判断することを意味します。もしそうなら、私たちはそれを返します、そうでなければ私たちはそれを呼び出すことができますflatten_recursive。しかし、言葉よりもコードの方が優れているので、いくつかのコードを見てみましょう。

def flatten_recursive(lst: List[Any]) -> Iterable[Any]:

"""Flatten a list using recursion."""

for item in lst:

if isinstance(item, list):

yield from flatten_recursive(item)

else:

yield item

def test_flatten_recursive():

l = [[1, 3], [2, 5], 1]

assert list(flatten_recursive(l)) == [1, 3, 2, 5, 1]

ifisinstance(item, list)は、リストでのみ機能することを意味することに注意してください。

反復アプローチ

反復アプローチは、間違いなくそれらすべての中で最も複雑です。このアプローチでは、を使用しdequeて不規則なリストをフラット化します。公式ドキュメントを引用すると、「Dequesはスタックとキューの一般化です（名前は「deck」と発音され、「両端キュー」の略です）。Dequeは、スレッドセーフでメモリ効率の高い追加と、Dequeの両側からのポップをサポートし、どちらの方向でもほぼ同じO（1）パフォーマンスを実現します。」

言い換えると、を使用dequeして再帰的ソリューションのスタッキング操作をシミュレートできます。

そのためには、再帰の場合と同じように開始し、各要素を繰り返し処理します。要素がリストでない場合は、の左側に追加しますdeque。このappendleftメソッドは、要素をの左端の位置に追加します。deque次に例を示します。

>>> from collections import deque

>>> l = deque()

>>> l.appendleft(2)

>>> l

deque([2])

>>> l.appendleft(7)

>>> l

deque([7, 2])

ただし、要素がリストの場合は、最初に要素を逆にして、このように「extendleft」メソッドに渡す必要がありmy_deque.extendleft(reversed(item))ます。再び、と同様list、extendleftの左端の位置に各項目を追加dequeで一連。その結果、dequeは逆の順序で要素を追加します。そのため、左に拡張する前にサブリストを逆にする必要があります。わかりやすくするために、例を見てみましょう。

>>> l = deque()

>>> l.extendleft([1, 2, 3])

>>> l

deque([3, 2, 1])

最後のステップはdeque、左端の要素を削除し、リストでない場合はそれを生成することを繰り返すことです。要素がリストの場合は、左に拡張する必要があります。完全な実装は次のようになります。

def flatten_deque(lst: List[Any]) -> Iterable[Any]:

"""Flatten a list using a deque."""

q = deque()

for item in lst:

if isinstance(item, list):

q.extendleft(reversed(item))

else:

q.appendleft(item)

while q:

elem = q.popleft()

if isinstance(elem, list):

q.extendleft(reversed(elem))

else:

yield elem

def test_flatten_super_irregular():

l = [1, [2, 3], [4], [], [[[[[[[[[5]]]]]]]]]]

assert list(flatten_deque(l)) == [1, 2, 3, 4, 5]

テストを実行すると、問題なく合格します…

============================= test session starts ==============================

…

flatten.py::test_flatten_super_irregular PASSED [100%]

============================== 1 passed in 0.01s ===============================

パフォーマンスの比較

前のセクションで見たように、リストが不規則な場合、選択肢はほとんどありません。しかし、これが頻繁なユースケースではないと仮定すると、これらのアプローチはパフォーマンスの観点からどのように比較されますか？

この最後の部分では、ベンチマークを実行し、どのソリューションが最もパフォーマンスが高いかを比較します。

これを行うには、私たちが使用できるtimeitモジュールを、我々はそれを呼び出すことができるIPythonことによって%timeit [code_to_measure]。以下のリストは、それぞれのタイミングです。ご覧のとおり、これはflatten_chainすべての中で最速の実装です。それlstは7.52 µs平均で私たちのリストを平らにしました。最も遅い実装はflatten_sum、29.3 ms同じリストをフラット化することです。

ジェネレータの理解を平坦化する

In [1]: lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]] * 1_000

In [2]: %timeit flatten_gen_comp(l)

335 ns ± 5.63 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

合計をフラット化

In [3]: %timeit flatten_sum(l)

29.3 ms ± 124 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

チェーンを平らにする

In [4]: %timeit flatten_chain(l)

7.52 µs ± 33 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

再帰をフラット化

In [5]: %timeit flatten_recursive(l)

208 ns ± 3.52 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

両端キューをフラット化

In [6]: %timeit flatten_deque(l)

210 ns ± 1.34 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

結論

Pythonを使用すると、いくつかの異なる方法でリストをフラット化できます。それぞれのアプローチには長所と短所があります。この投稿では、不規則なリストを含め、リストをフラット化する5つの異なる方法を検討しました。