ordinare - Creazione di un elenco semplice dall'elenco di elenchi in Python




ordinare lista python (20)

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

Codice semplice per fan del pacchetto underscore.py

from underscore import _
_.flatten([[1, 2, 3], [4, 5, 6], [7], [8, 9]])
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Risolve tutti i problemi di appiattimento (nessuna voce di elenco o nidificazione complessa)

from underscore import _
# 1 is none list item
# [2, [3]] is complex nesting
_.flatten([1, [2, [3]], [4, 5, 6], [7], [8, 9]])
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

È possibile installare underscore.py con pip

pip install underscore.py

Ecco un approccio generale che si applica a numeri , stringhe , elenchi annidati e contenitori misti .

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, la 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 viene 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 un precedente post SO , probabilmente la dimostrazione originale.

Il motivo per cui la tua funzione non ha funzionato: l'estensione estende l'array sul posto e non lo restituisce. Puoi ancora restituire x da lambda, usando un trucco:

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

Nota: l'estensione è più efficiente di + sugli elenchi.


La risposta accettata non ha funzionato per me quando si trattava di liste di lunghezze variabili basate su testo. Ecco un approccio alternativo che ha funzionato per me.

l = ['aaa', 'bb', 'cccccc', ['xx', 'yyyyyyy']]

Risposta accettata che non ha funzionato:

flat_list = [item for sublist in l for item in sublist]
print(flat_list)
['a', 'a', 'a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'c', 'xx', 'yyyyyyy']

Nuova soluzione proposta che ha funzionato per me:

flat_list = []
_ = [flat_list.extend(item) if isinstance(item, list) else flat_list.append(item) for item in l if item]
print(flat_list)
['aaa', 'bb', 'cccccc', 'xx', 'yyyyyyy']

Perché usi l'estensione?

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

Questo dovrebbe funzionare bene.


Prendi in considerazione l'installazione del pacchetto more_itertools .

> pip install more_itertools

Viene fornito con un'implementazione per flatten ( source , dalle ricette itertools ):

import more_itertools


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

A partire dalla versione 2.4, è possibile appiattire più iterable più complessi e nidificati con more_itertools.collapse ( source , contribuito da abarnet).

lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
list(more_itertools.collapse(lst)) 
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

lst = [[1, 2, 3], [[4, 5, 6]], [[[7]]], 8, 9]              # complex nesting
list(more_itertools.collapse(lst))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Puoi usare numpy:
flat_list = list(np.concatenate(list_of_list))


Recentemente mi sono imbattuto in una situazione in cui avevo un mix di stringhe e dati numerici in sottoliste come

test = ['591212948',
['special', 'assoc', 'of', 'Chicago', 'Jon', 'Doe'],
['Jon'],
['Doe'],
['fl'],
92001,
555555555,
'hello',
['hello2', 'a'],
'b',
['hello33', ['z', 'w'], 'b']]

dove metodi come flat_list = [item for sublist in test for item in sublist]non hanno funzionato. Quindi, ho trovato la seguente soluzione per il livello 1+ di sottoliste

def concatList(data):
    results = []
    for rec in data:
        if type(rec) == list:
            results += rec
            results = concatList(results)
        else:
            results.append(rec)
    return results

E il risultato

In [38]: concatList(test)
Out[38]:
 Out[60]:
['591212948',
'special',
'assoc',
'of',
'Chicago',
'Jon',
'Doe',
'Jon',
'Doe',
'fl',
92001,
555555555,
'hello',
'hello2',
'a',
'b',
'hello33',
'z',
'w',
'b']

Se vuoi appiattire una struttura di dati in cui non sai quanto è nidificato puoi usare iteration_utilities.deepflatten 1

>>> 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 è necessario eseguire il cast in un list o eseguirne esplicitamente iterazioni.

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

È 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, la sum sarà più veloce, tuttavia per lunghi iterables solo itertools.chain.from_iterable , iteration_utilities.deepflatten o la comprensione annidata hanno prestazioni ragionevoli con itertools.chain.from_iterable è 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


Seguire mi sembra più semplice:

>>> import numpy as np
>>> l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
>>> print (np.concatenate(l))
[1 2 3 4 5 6 7 8 9]

Si può anche usare l' flat di NumPy:

import numpy as np
list(np.array(l).flat)

Modifica 11/02/2016: Funziona solo quando le sottoliste hanno dimensioni identiche.


Un altro approccio insolito che funziona per liste eterogenee e omogenee di numeri interi:

from typing import List


def flatten(l: list) -> List[int]:
    """Flatten an arbitrary deep nested list of lists of integers.

    Examples:
        >>> flatten([1, 2, [1, [10]]])
        [1, 2, 1, 10]

    Args:
        l: Union[l, Union[int, List[int]]

    Returns:
        Flatted list of integer
    """
    return [int(i.strip('[ ]')) for i in str(l).split(',')]

È possibile evitare le chiamate ricorsive allo stack utilizzando semplicemente una struttura di dati stack effettiva.

alist = [1,[1,2],[1,2,[4,5,6],3, "33"]]
newlist = []

while len(alist) > 0 :
  templist = alist.pop()
  if type(templist) == type(list()) :
    while len(templist) > 0 :
      temp = templist.pop()
      if type(temp) == type(list()) :
        for x in temp :
          templist.append(x)
      else :
        newlist.append(temp)
  else :
    newlist.append(templist)
print(list(reversed(newlist)))

matplotlib.cbook.flatten() funzionerà per gli elenchi annidati anche se si annidano più profondamente dell'esempio.

import matplotlib
l = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
print(list(matplotlib.cbook.flatten(l)))
l2 = [[1, 2, 3], [4, 5, 6], [7], [8, [9, 10, [11, 12, [13]]]]]
print list(matplotlib.cbook.flatten(l2))

Risultato:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

Questo è 18 volte più veloce del carattere di sottolineatura.

Average time over 1000 trials of matplotlib.cbook.flatten: 2.55e-05 sec
Average time over 1000 trials of underscore._.flatten: 4.63e-04 sec
(time for underscore._)/(time for matplotlib.cbook) = 18.1233394636

Nota : qui sotto si applica a Python 3.3+ perché utilizza yield_from. sixè anche un pacchetto di terze parti, sebbene sia stabile. In alternativa, è possibile utilizzare sys.version.

Nel caso di obj = [[1, 2,], [3, 4], [5, 6]], tutte le soluzioni qui sono buone, compresa la comprensione delle liste e itertools.chain.from_iterable.

Tuttavia, considera questo caso leggermente più complesso:

>>> obj = [[1, 2, 3], [4, 5], 6, 'abc', [7], [8, [9, 10]]]

Ci sono diversi problemi qui:

  • Un elemento,, 6è solo uno scalare; non è iterable, quindi le rotte di cui sopra falliranno qui.
  • Un elemento, 'abc', è tecnicamente iterabile (tutti strs sono). Tuttavia, leggendo tra le righe un po ', non si vuole trattarlo come tale - si vuole trattarlo come un singolo elemento.
  • L'elemento finale, [8, [9, 10]]è esso stesso un iterabile nidificato. Comprensione di base delle liste e chain.from_iterablesolo estrarre "1 livello in basso".

Puoi rimediare a questo come segue:

>>> from collections import Iterable
>>> from six import string_types

>>> def flatten(obj):
...     for i in obj:
...         if isinstance(i, Iterable) and not isinstance(i, string_types):
...             yield from flatten(i)
...         else:
...             yield i


>>> list(flatten(obj))
[1, 2, 3, 4, 5, 6, 'abc', 7, 8, 9, 10]

Qui, si controlla che l'elemento secondario (1) sia iterabile con Iterable, un ABC da itertools, ma si desidera anche assicurarsi che (2) l'elemento non sia "simile a una stringa".


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

Un semplice metodo ricorsivo usando reduceda functoolse l' addoperatore sugli elenchi:

>>> from functools import reduce
>>> from operator import add
>>> flatten = lambda lst: [lst] if type(lst) is int else reduce(add, [flatten(ele) for ele in lst])
>>> flatten(l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

La funzione flattenassume lstcome parametro. Fa scorrere tutti gli elementi lstfino a raggiungere gli interi (possono anche essere modificati intin float, strecc. Per altri tipi di dati), che vengono aggiunti al valore di ritorno della ricorsione più esterna.

La ricorsione, a differenza dei metodi come forloop e monade, è che si tratta di una soluzione generale non limitata dalla profondità dell'elenco . Ad esempio, un elenco con profondità di 5 può essere appiattito allo stesso modo di l:

>>> l2 = [[3, [1, 2], [[[6], 5], 4, 0], 7, [[8]], [9, 10]]]
>>> flatten(l2)
[3, 1, 2, 6, 5, 4, 0, 7, 8, 9, 10]

def flatten(alist):
    if alist == []:
        return []
    elif type(alist) is not list:
        return [alist]
    else:
        return flatten(alist[0]) + flatten(alist[1:])

flat_list = []
for i in list_of_list:
    flat_list+=i

Questo codice funziona anche bene, semplicemente estendendo l'elenco fino in fondo. Anche se è molto simile ma ne ha solo uno per loop. Quindi ha meno complessità rispetto all'aggiunta di 2 loop.


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, è possibile utilizzare il modulo timeit 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 + (incluso l'uso implicito in sum ) sono, per necessità, O(L**2) quando ci sono L-Liste - poiché l'elenco dei risultati intermedi continua ad allungarsi, ad ogni passaggio un nuovo risultato intermedio l'oggetto lista viene assegnato e tutti gli elementi nel risultato intermedio precedente devono essere copiati sopra (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.







flatten