Question Faire une liste à plat de la liste des listes en Python


Je me demande s'il existe un raccourci pour faire une liste simple de listes de listes en Python.

Je peux le faire dans une boucle for, mais peut-être qu'il y a du cool "one-liner"? Je l'ai essayé avec réduire, mais j'ai une erreur.

Code

l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
reduce(lambda x, y: x.extend(y), l)

Message d'erreur

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'extend'

2069
2018-06-04 20:30


origine


Réponses:


flat_list = [item for sublist in l for item in sublist]

ce qui signifie:

for sublist in l:
    for item in sublist:
        flat_list.append(item)

est plus rapide que les raccourcis affichés jusqu'à présent. (l est la liste à aplatir.)

Voici une fonction correspondante:

flatten = lambda l: [item for sublist in l for item in sublist]

Pour preuve, comme toujours, vous pouvez utiliser le timeit module dans la bibliothèque standard:

$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' '[item for sublist in l for item in sublist]'
10000 loops, best of 3: 143 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 3: 969 usec per loop
$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 3: 1.1 msec per loop

Explication: les raccourcis basés sur + (y compris l'utilisation implicite dans sum) sont, par nécessité, O(L**2) quand il y a des sous-listes L - comme la liste des résultats intermédiaires ne cesse de s'allonger, un nouvel objet liste intermédiaire est alloué à chaque étape et tous les éléments du résultat intermédiaire précédent doivent être copiés (ainsi que quelques nouveaux ajoutés à la fin). Donc (pour simplifier et sans perte réelle de généralité) dites que vous avez L sous-listes de I articles chacun: les premiers éléments I sont copiés d'avant en arrière L-1 fois, le deuxième I éléments L-2 fois, et ainsi de suite; le nombre total d'exemplaires est I fois la somme de x pour x de 1 à L exclus, c.-à-d. I * (L**2)/2.

La compréhension de la liste génère une seule liste, une fois, et copie chaque élément (de son lieu de résidence original à la liste des résultats) également exactement une fois.


2984
2018-06-04 20:37



Vous pouvez utiliser itertools.chain():

>>> import itertools
>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> merged = list(itertools.chain(*list2d))

ou, sur Python> = 2.6, utilisez itertools.chain.from_iterable() ce qui ne nécessite pas de déballer la liste:

>>> import itertools
>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> merged = list(itertools.chain.from_iterable(list2d))

Cette approche est sans doute plus lisible que [item for sublist in l for item in sublist] et semble être plus rapide aussi:

[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools' 'list(itertools.chain.from_iterable(l))'
10000 loops, best of 3: 24.2 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' '[item for sublist in l for item in sublist]'
10000 loops, best of 3: 45.2 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'sum(l, [])'
1000 loops, best of 3: 488 usec per loop
[me@home]$ python -mtimeit -s'l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'reduce(lambda x,y: x+y,l)'
1000 loops, best of 3: 522 usec per loop
[me@home]$ python --version
Python 2.7.3

1079
2018-06-04 21:06



Note de l'auteur: Ceci est inefficace. Mais amusant, parce que les monades sont géniales. Ce n'est pas approprié pour le code Python de production.

>>> sum(l, [])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Cela ne fait que résumer les éléments de itérable passés dans le premier argument, en traitant le deuxième argument comme la valeur initiale de la somme (si elle n'est pas donnée, 0 est utilisé à la place et ce cas vous donnera une erreur).

Parce que vous additionnez des listes imbriquées, vous obtenez [1,3]+[2,4] en conséquence de sum([[1,3],[2,4]],[]), qui est égal à [1,3,2,4].

Notez que cela ne fonctionne que sur les listes de listes. Pour les listes de listes de listes, vous aurez besoin d'une autre solution.


636
2018-06-04 20:35



J'ai testé la plupart des solutions suggérées avec Perfplot (un projet d'animal de compagnie de la mienne, essentiellement une enveloppe autour timeit), et trouvé

list(itertools.chain.from_iterable(a))

être la solution la plus rapide (si plus de 10 listes sont concaténées).

enter image description here


Code pour reproduire l'intrigue:

import functools
import itertools
import numpy
import operator
import perfplot


def forfor(a):
    return [item for sublist in a for item in sublist]


def sum_brackets(a):
    return sum(a, [])


def functools_reduce(a):
    return functools.reduce(operator.concat, a)


def itertools_chain(a):
    return list(itertools.chain.from_iterable(a))


def numpy_flat(a):
    return list(numpy.array(a).flat)


def numpy_concatenate(a):
    return list(numpy.concatenate(a))


perfplot.show(
    setup=lambda n: [list(range(10))] * n,
    kernels=[
        forfor, sum_brackets, functools_reduce, itertools_chain, numpy_flat,
        numpy_concatenate
        ],
    n_range=[2**k for k in range(16)],
    logx=True,
    logy=True,
    xlabel='num lists'
    )

129
2017-07-26 09:38



from functools import reduce #python 3

>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> reduce(lambda x,y: x+y,l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

le extend() méthode dans votre exemple modifie x au lieu de renvoyer une valeur utile reduce() s'attend à).

Un moyen plus rapide de faire le reduce la version serait

>>> import operator
>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> reduce(operator.concat, l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

99
2018-06-04 20:35



Voici une approche générale qui s'applique à Nombres, cordes, imbriqué listes et mixte conteneurs.

Code

from collections import Iterable


def flatten(items):
    """Yield items from any nested iterable; see Reference."""
    for x in items:
        if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
            for sub_x in flatten(x):
                yield sub_x
        else:
            yield x

Note: en Python 3, yield from flatten(x) peut remplacer for sub_x in flatten(x): yield sub_x

Démo

lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
list(flatten(lst))                                         # nested lists
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

mixed = [[1, [2]], (3, 4, {5, 6}, 7), 8, "9"]              # numbers, strs, nested & mixed
list(flatten(mixed))
# [1, 2, 3, 4, 5, 6, 7, 8, '9']

Référence

  • Cette solution est modifiée à partir d'une recette dans Beazley, D. et B. Jones. Recette 4.14, Python Cookbook 3e éd., O'Reilly Media Inc. Sébastopol, CA: 2013.
  • Trouvé plus tôt SO post, peut-être la démonstration originale.

54
2017-11-29 04:14



Je reprends ma déclaration. la somme n'est pas le gagnant. Bien que ce soit plus rapide quand la liste est petite. Mais la performance se dégrade de manière significative avec des listes plus grandes. 

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10000'
    ).timeit(100)
2.0440959930419922

La version sum est toujours en cours d'exécution depuis plus d'une minute et n'a pas encore été traitée!

Pour les listes moyennes:

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
20.126545906066895
>>> timeit.Timer(
        'reduce(lambda x,y: x+y,l)',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
22.242258071899414
>>> timeit.Timer(
        'sum(l, [])',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]] * 10'
    ).timeit()
16.449732065200806

Utilisation de petites listes et de temps: nombre = 1000000

>>> timeit.Timer(
        '[item for sublist in l for item in sublist]',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
2.4598159790039062
>>> timeit.Timer(
        'reduce(lambda x,y: x+y,l)',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
1.5289170742034912
>>> timeit.Timer(
        'sum(l, [])',
        'l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]'
    ).timeit()
1.0598428249359131

31
2018-06-04 20:46



Pourquoi utilisez-vous étendre?

reduce(lambda x, y: x+y, l)

Cela devrait fonctionner correctement.


25
2018-06-04 20:38



Il semble y avoir une confusion avec operator.add! Lorsque vous ajoutez deux listes ensemble, le terme correct pour cela est concat, pas ajouter. operator.concat est ce que vous devez utiliser.

Si vous pensez fonctionnel, c'est aussi simple que ça:

>>> list2d = ((1,2,3),(4,5,6), (7,), (8,9))
>>> reduce(operator.concat, list2d)
(1, 2, 3, 4, 5, 6, 7, 8, 9)

Vous voyez réduire respecte le type de séquence, donc quand vous fournissez un tuple, vous récupérez un tuple. Essayons avec une liste ::

>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> reduce(operator.concat, list2d)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Aha, vous obtenez une liste.

Comment sur la performance ::

>>> list2d = [[1,2,3],[4,5,6], [7], [8,9]]
>>> %timeit list(itertools.chain.from_iterable(list2d))
1000000 loops, best of 3: 1.36 µs per loop

from_iterable est assez rapide! Mais ce n'est pas une comparaison à réduire avec concat.

>>> list2d = ((1,2,3),(4,5,6), (7,), (8,9))
>>> %timeit reduce(operator.concat, list2d)
1000000 loops, best of 3: 492 ns per loop

19
2017-09-14 15:09



Si vous voulez aplatir une structure de données où vous ne savez pas à quel point elle est imbriquée, vous pouvez utiliser iteration_utilities.deepflatten1

>>> from iteration_utilities import deepflatten

>>> l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
>>> list(deepflatten(l, depth=1))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> l = [[1, 2, 3], [4, [5, 6]], 7, [8, 9]]
>>> list(deepflatten(l))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

C'est un générateur donc vous devez lancer le résultat à un list ou explicitement itérer dessus.


Pour aplatir un seul niveau et si chacun des éléments est lui-même itérable, vous pouvez également utiliser iteration_utilities.flatten qui lui-même est juste une enveloppe mince autour itertools.chain.from_iterable:

>>> from iteration_utilities import flatten
>>> l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
>>> list(flatten(l))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Juste pour ajouter quelques timings (basé sur Nico Schlömer réponse qui n'incluait pas la fonction présentée dans cette réponse):

enter image description here

Il s'agit d'un graphe log-log pour tenir compte de l'énorme gamme de valeurs qui s'étendent. Pour un raisonnement qualitatif: Baisser est meilleur.

Les résultats montrent que si l'itérable contient seulement quelques itérations internes alors sum sera le plus rapide, mais pour de longs iterables seulement itertools.chain.from_iterable, iteration_utilities.deepflatten ou la compréhension imbriquée ont des performances raisonnables avec itertools.chain.from_iterable être le plus rapide (comme déjà remarqué par Nico Schlömer).

from itertools import chain
from functools import reduce
from collections import Iterable  # or from collections.abc import Iterable
import operator
from iteration_utilities import deepflatten

def nested_list_comprehension(lsts):
    return [item for sublist in lsts for item in sublist]

def itertools_chain_from_iterable(lsts):
    return list(chain.from_iterable(lsts))

def pythons_sum(lsts):
    return sum(lsts, [])

def reduce_add(lsts):
    return reduce(lambda x, y: x + y, lsts)

def pylangs_flatten(lsts):
    return list(flatten(lsts))

def flatten(items):
    """Yield items from any nested iterable; see REF."""
    for x in items:
        if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
            yield from flatten(x)
        else:
            yield x

def reduce_concat(lsts):
    return reduce(operator.concat, lsts)

def iteration_utilities_deepflatten(lsts):
    return list(deepflatten(lsts, depth=1))


from simple_benchmark import benchmark

b = benchmark(
    [nested_list_comprehension, itertools_chain_from_iterable, pythons_sum, reduce_add,
     pylangs_flatten, reduce_concat, iteration_utilities_deepflatten],
    arguments={2**i: [[0]*5]*(2**i) for i in range(1, 13)},
    argument_name='number of inner lists'
)

b.plot()

1 Disclaimer: Je suis l'auteur de cette bibliothèque


17
2017-11-26 00:20



La raison pour laquelle votre fonction n'a pas fonctionné: extend étend le tableau in-place et ne le renvoie pas. Vous pouvez toujours renvoyer x depuis lambda, en utilisant une astuce:

reduce(lambda x,y: x.extend(y) or x, l)

Note: extend est plus efficace que + sur les listes.


13
2018-06-04 20:47