Domanda Creazione di un elenco semplice dall'elenco di elenchi in Python


Mi chiedo se esiste una scorciatoia per fare una semplice lista di liste di liste in Python.

Posso farlo in un ciclo for, ma forse c'è un "one-liner" interessante? L'ho provato con ridurre, ma ottengo un errore

Codice

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

Messaggio di errore

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

2067
2018-06-04 20:30


origine


risposte:


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

che significa:

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

è più veloce delle scorciatoie pubblicate finora. (l è la lista da appiattire).

Ecco una funzione corrispondente:

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

Per prova, come sempre, puoi usare il timeit modulo nella libreria 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

Spiegazione: le scorciatoie basate su + (compreso l'uso implicito in sum) sono, per necessità, O(L**2) quando ci sono sottoliste L - dato che l'elenco dei risultati intermedi continua ad allungarsi, ad ogni passo viene assegnato un nuovo oggetto elenco risultati intermedi, e tutti gli elementi nel risultato intermedio precedente devono essere copiati (così come alcuni nuovi aggiunti alla fine). Quindi (per semplicità e senza effettiva perdita di generalità) dite di avere L Liste di elementi I ciascuno: i primi elementi I vengono copiati avanti e indietro L-1 volte, il secondo I elementi L-2 volte, e così via; il numero totale di copie è I volte la somma di x per x da 1 a L esclusa, cioè I * (L**2)/2.

La comprensione dell'elenco genera solo una lista, una volta, e copia ogni oggetto (dalla sua posizione originale di residenza alla lista dei risultati) anche esattamente una volta.


2982
2018-06-04 20:37



Puoi usare itertools.chain():

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

oppure, su Python> = 2.6, utilizzare itertools.chain.from_iterable() che non richiede il disimballaggio della lista:

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

Questo approccio è probabilmente più leggibile di [item for sublist in l for item in sublist] e sembra anche essere più veloce:

[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

1077
2018-06-04 21:06



Nota dell'autore: Questo è inefficiente. Ma divertente, perché le monadi sono fantastiche. Non è appropriato per il codice Python di produzione.

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

Questo riassume solo gli elementi di iterable passati nel primo argomento, trattando il secondo argomento come il valore iniziale della somma (se non dato, 0 è usato invece e questo caso ti darà un errore).

Perché stai sommando le liste annidate, in realtà ottieni [1,3]+[2,4] come conseguenza di sum([[1,3],[2,4]],[]), che è uguale a [1,3,2,4].

Nota che funziona solo sugli elenchi di elenchi. Per gli elenchi di elenchi di elenchi, avrai bisogno di un'altra soluzione.


636
2018-06-04 20:35



Ho provato le soluzioni più suggerite con perfplot (un mio progetto per animali, essenzialmente un involucro in giro timeit) e trovato

list(itertools.chain.from_iterable(a))

essere la soluzione più veloce (se più di 10 liste sono concatenate).

enter image description here


Codice per riprodurre la trama:

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]

Il extend() il metodo nel tuo esempio modifica x invece di restituire un valore utile (quale reduce() si aspetta).

Un modo più veloce per fare il reduce la versione sarebbe

>>> 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



Ecco un approccio generale a cui si applica numeri, stringhe, nidificato liste e misto contenitori.

Codice

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

Nota: in Python 3, yield from flatten(x) può sostituire for sub_x in flatten(x): yield sub_x

dimostrazione

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']

Riferimento

  • Questa soluzione è stata modificata da una ricetta in Beazley, D. e B. Jones. Ricetta 4.14, Python Cookbook 3rd Ed., O'Reilly Media Inc. Sebastopol, CA: 2013.
  • Trovato prima SO post, forse la dimostrazione originale.

54
2017-11-29 04:14



Riporto la mia dichiarazione. la somma non è il vincitore. Anche se è più veloce quando la lista è piccola. Ma le prestazioni si degradano in modo significativo con elenchi più grandi. 

>>> 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 versione di somma è ancora in esecuzione per più di un minuto e non ha ancora eseguito l'elaborazione!

Per le liste medie:

>>> 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

Utilizzo di elenchi piccoli e timeit: numero = 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



Perché usi l'estensione?

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

Questo dovrebbe funzionare bene.


25
2018-06-04 20:38



Sembra esserci confusione con operator.add! Quando si aggiungono due elenchi, il termine corretto è quello concat, non aggiungere. operator.concat è quello che devi usare.

Se stai pensando funzionale, è facile come questo:

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

Vedete ridurre il rispetto del tipo di sequenza, quindi quando fornite una tupla, si ottiene una tupla. proviamo con una lista ::

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

Aha, torni una lista.

Che ne dici di prestazioni ::

>>> 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 è abbastanza veloce! Ma non è un confronto da ridurre con 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



Se vuoi appiattire una struttura dei dati in cui non sai quanto è profondo puoi usare 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]

È un generatore quindi devi lanciare il risultato su a list o esplicitamente iterare su di esso.


Per appiattire solo un livello e se ognuno degli elementi è esso stesso iterabile, puoi anche usarlo iteration_utilities.flatten che di per sé è solo un involucro sottile intorno 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]

Solo per aggiungere alcuni tempi (in base alla risposta di Nico Schlömer che non includeva la funzione presentata in questa risposta):

enter image description here

È una trama di log-log per contenere l'enorme intervallo di valori spanning. Per il ragionamento qualitativo: inferiore è meglio.

I risultati mostrano che se l'iterabile contiene solo pochi iterabili interni, allora sum sarà più veloce, tuttavia per lunghissimi iterables solo il itertools.chain.from_iterable, iteration_utilities.deepflatten o la comprensione annidata ha una prestazione ragionevole con itertools.chain.from_iterable essere il più veloce (come già notato da 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: sono l'autore di quella libreria


17
2017-11-26 00:20