Pytanie Tworzenie płaskiej listy z listy list w Pythonie


Zastanawiam się, czy istnieje skrót do utworzenia prostej listy z listy list w Pythonie.

Mogę to zrobić w pętli for, ale może jest jakiś fajny "one-liner"? Próbowałem tego zmniejszyć, ale pojawia się błąd.

Kod

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

Komunikat o błędzie

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

2083
2018-06-04 20:30


pochodzenie


Tutaj jest dogłębna dyskusja na ten temat: rightfootin.blogspot.com/2006/09/more-on-python-flatten.html, omawianie kilku metod spłaszczania dowolnie zagnieżdżonych list list. Ciekawa lektura! - RichieHindle
Niektóre inne odpowiedzi są lepsze, ale powodem twojego niepowodzenia jest to, że metoda 'extend' zawsze zwraca None. Dla listy o długości 2 będzie działać, ale zwróci Brak. Dla dłuższej listy zużyje pierwsze 2 argumenty, które zwrócą Brak. Następnie kontynuuje z None.extend (<third arg>), co powoduje tę erro - mehtunguh
@ Shawn-chin to rozwiązanie bardziej pythonowe, ale jeśli chcesz zachować typ sekwencji, powiedz, że masz krotkę krotek zamiast listy list, powinieneś użyć reduce (operator.concat, tuple_of_tuples). Używanie operatora.concat z krotkami działa szybciej niż chain.from_itersables z listą. - Meitham
numpy.array ([[1], [2]]). flatten (). tolist (), który usuwa wewnętrzną strukturę i zwraca listę [1,2] - user5920660
Teraz obsługiwane przez mpu: import mpu; mpu.datastructures.flatten([1, [2, 3], [4, [5, 6]]]) daje [1, 2, 3, 4, 5, 6] - Martin Thoma


Odpowiedzi:


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

co znaczy:

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

jest szybszy niż dotychczasowe skróty. (l to lista do spłaszczenia.)

Oto odpowiednia funkcja:

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

Dla dowodu, jak zawsze, możesz użyć timeit moduł w standardowej bibliotece:

$ 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

Objaśnienie: skróty oparte na + (w tym dorozumiane użycie w sum) są, z konieczności, O(L**2) gdy istnieją podlisty L - gdy lista wyników pośrednich jest coraz dłuższa, na każdym kroku zostaje przydzielony nowy obiekt listy wyników pośrednich, a wszystkie elementy poprzedniego wyniku pośredniego muszą zostać skopiowane (a także kilka nowych elementów dodanych na końcu). Tak więc (dla uproszczenia i bez faktycznej utraty ogólności) powiedzmy, że masz L podlisty każdego z I elementów: pierwsze elementy I są kopiowane tam iz powrotem L-1 razy, drugie, które umieszczam L-2 razy, i tak dalej; całkowita liczba kopii jest 1 razy większa od sumy x dla x od 1 do L, tzn. I * (L**2)/2.

Zrozumienie listy po prostu generuje jedną listę, jeden raz, i kopiuje każdy element ponad (z pierwotnego miejsca zamieszkania do listy wyników) również dokładnie jeden raz.


3001
2018-06-04 20:37



Próbowałem testu z tymi samymi danymi, używając itertools.chain.from_iterable: $ python -mtimeit -s'from itertools import chain; l=[[1,2,3],[4,5,6], [7], [8,9]]*99' 'list(chain.from_iterable(l))'. Działa nieco ponad dwa razy szybciej niż w przypadku zagnieżdżonej listy, która jest najszybszą spośród przedstawionych tu alternatyw. - intuited
Zauważyłem, że składnia jest trudna do zrozumienia, dopóki nie uświadomiłem sobie, że możesz myśleć o niej dokładnie tak, jak zagnieżdżone dla pętli. dla podlist w l: dla pozycji w podlistie: pozycja zysku - Rob Crowell
@BorisChervenkov: Zauważ, że zawarłem wezwanie list() aby przekształcić iterator w listę. - intuited
[liść drzewa w lesie na liść w drzewie] może być łatwiejszy do zrozumienia i zastosowania. - John Mee
@Joel, właściwie w dzisiejszych czasach list(itertools.chain.from_iterable(l)) jest najlepszy - jak zauważono w innych komentarzach i odpowiedzi Shawna. - Alex Martelli


Możesz użyć itertools.chain():

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

lub, w Pythonie> = 2.6, użyj itertools.chain.from_iterable() który nie wymaga rozpakowania listy:

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

To podejście jest prawdopodobnie bardziej czytelne niż [item for sublist in l for item in sublist] i wydaje się być również szybszy:

[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

1083
2018-06-04 21:06



@ShawnChin BTW, część sprzętu, którą posiadałeś, odpowiadając na to pytanie, moja obecna stacja robocza jest o połowę szybsza i ma 4 lata. - Manuel Gutierrez
@alexandre zobacz docs.python.org/2/tutorial/... - Shawn Chin
The * to najtrudniejsza rzecz, która sprawia chain mniej proste niż zrozumienie listy. Musisz wiedzieć, że ten łańcuch łączy tylko iterables przekazane jako parametry, a * powoduje, że lista najwyższego poziomu jest rozszerzana na parametry, więc chain łączy wszystkie te iterables, ale nie schodzi dalej. Myślę, że to sprawia, że ​​zrozumienie jest bardziej czytelne niż użycie łańcucha w tym przypadku. - Tim Dierks
@TimDierks: Nie jestem pewien "wymaga to zrozumienia składni Pythona" jest argumentem przeciwko używaniu danej techniki w Pythonie. Oczywiście złożone użycie może wprowadzać w błąd, ale operator "splat" jest ogólnie przydatny w wielu okolicznościach i nie używa go w szczególnie niejasny sposób; Odrzucenie wszystkich funkcji językowych, które niekoniecznie są oczywiste dla początkujących użytkowników, oznacza, że ​​tylekroć łapiesz jedną rękę za plecami. Może również wyrzucać ze zrozumieniem listy, gdy jesteś na tym; użytkownicy z innych środowisk znajdą for pętla, która wielokrotnie appends bardziej oczywiste. - ShadowRanger
co powiesz na ['abcde_', ['_abcde', ['e_abcd', ['de_abc', ['cde_ab', ['bcde_a']]]]]] - Aymon Fournier


Uwaga od autora: Jest to nieefektywne. Ale fajnie, bo monady są niesamowite. Nie nadaje się do produkcji kodu Python.

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

To po prostu sumuje elementy iteracji przekazane w pierwszym argumencie, traktując drugi argument jako wartość początkową sumy (jeśli nie podano, 0 jest używany zamiast tego, a ten przypadek spowoduje błąd).

Ponieważ podsumowujesz zagnieżdżone listy, faktycznie dostajesz [1,3]+[2,4] w wyniku sum([[1,3],[2,4]],[]), który jest równy [1,3,2,4].

Zauważ, że działa tylko na listach list. W przypadku list list list potrzebujemy innego rozwiązania.


638
2018-06-04 20:35



to całkiem schludne i sprytne, ale nie użyłbym go, ponieważ czytanie jest mylące. - andrewrk
To jest Shlemiel, algorytm malarza joelonsoftware.com/articles/fog0000000319.html - niepotrzebnie nieefektywne, a także niepotrzebnie brzydkie. - Mike Graham
Operacja dołączenia do list tworzy a Monoid, która jest jedną z najwygodniejszych abstrakcji do myślenia o + operacja w sensie ogólnym (nie tylko w przypadku numerów). Tak więc ta odpowiedź zasługuje na +1 ode mnie za (poprawne) traktowanie list jako monoidów. Spektakl dotyczy jednak ... - ulidtko
@ Andrewrk Niektórzy uważają, że jest to najczystszy sposób na zrobienie tego: youtube.com/watch?v=IOiZatlZtGU Ci, którzy nie rozumieją, dlaczego to jest fajne, muszą po prostu poczekać kilka dekad, aż wszyscy to zrobią :) wykorzystajmy języki programowania (i abstrakcje), które są odkrywane, a nie wymyślone, odkryto Monoid. - jhegedus
jest to bardzo nieefektywny sposób ze względu na kwadratowy aspekt sumy. - Jean-François Fabre


Testowałem najbardziej zalecane rozwiązania z perfplot (mój ulubiony projekt, w zasadzie owinięty wokół timeit), i znalezione

list(itertools.chain.from_iterable(a))

być najszybszym rozwiązaniem (jeśli więcej niż 10 list jest połączonych).

enter image description here


Kod do odtworzenia fabuły:

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

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

The extend() Metoda w twoim przykładzie modyfikuje x zamiast zwracania użytecznej wartości (która reduce() oczekuje).

Szybszy sposób na zrobienie tego reduce wersja będzie

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

100
2018-06-04 20:35



reduce(operator.add, l) byłby właściwy sposób na zrobienie tego reduce wersja. Wbudowane są szybsze niż lambdy. - agf
@agf tutaj jest jak: * timeit.timeit('reduce(operator.add, l)', 'import operator; l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]', number=10000)  0,017956018447875977   * timeit.timeit('reduce(lambda x, y: x+y, l)', 'import operator; l=[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7]]', number=10000)  0.025218963623046875 - lukmdo
To jest Shlemiel, algorytm malarza joelonsoftware.com/articles/fog0000000319.html - Mike Graham
to może używać tylko dla integers. Ale co jeśli lista zawiera string? - Freddy
@Freddy: The operator.add Funkcja działa równie dobrze dla obu list całkowitych i list ciągów. - Greg Hewgill


Oto ogólne podejście, które dotyczy liczby, smyczki, zagnieżdżony listy i mieszany pojemniki.

Kod

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

Uwaga: w Pythonie 3, yield from flatten(x) można wymienić for sub_x in flatten(x): yield sub_x

Próbny

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

Odniesienie

  • To rozwiązanie jest modyfikowane z przepisu w Beazley, D. i B. Jones. Przepis 4.14, Python Cookbook 3rd Ed., O'Reilly Media Inc. Sebastopol, CA: 2013.
  • Znaleziono wcześniej SO post, być może oryginalna demonstracja.

55
2017-11-29 04:14



Właśnie napisałem prawie tak samo, ponieważ nie widziałem twojego rozwiązania ... Oto, czego szukałem "rekursywnie spłaszczaj kompletne listy" ... (+1) - Martin Thoma
@MartinThoma Bardzo docenione. FYI, jeśli spłaszczanie iterables zagnieżdżonych jest powszechną praktyką, istnieje kilka pakietów osób trzecich, które radzą sobie z tym dobrze. Może to uchronić przed wynalezieniem nowego koła. Wspominałem more_itertools między innymi omówione w tym poście. Twoje zdrowie. - pylang
Nice - właśnie zastanawiałeś się nad a yield from rodzaj budowy na pytonie po poznaniu yield * w es2015. - Triptych
zastąpiony przez if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): do obsługi ciągów. - Jorge Leitão
Poprawny. Oryginalny przepis na książkę kucharską pokazuje, jak obsługiwać ciągi i bajty. Jeśli dokonałeś edycji, aby odzwierciedlić to wsparcie. - pylang


Odzyskuję moje oświadczenie. suma nie jest zwycięzcą. Chociaż jest szybszy, gdy lista jest mała. Ale wydajność spada znacząco w przypadku większych list. 

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

Wersja sumowa działa jeszcze przez ponad minutę i nie została jeszcze przetworzona!

Dla średnich list:

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

Używanie małych list i timeit: number = 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



dla naprawdę niewielkiej listy, np. jeden z 3 podlistami, może - ale ponieważ suma wydajności idzie z O (N ** 2), podczas gdy zrozumienie listy idzie w parze z O (N), samo powiększanie listy wejściowej trochę odwróci rzeczy - faktycznie LC będzie " nieskończenie szybszy "niż suma na granicy, gdy N rośnie. Byłem odpowiedzialny za zaprojektowanie sumy i wykonanie jej pierwszej implementacji w środowisku wykonawczym Python i nadal żałuję, że nie znalazłem sposobu, aby skutecznie ograniczyć ją do sumowania liczb (w czym jest naprawdę dobry) i zablokować "atrakcyjne niedogodności", które oferuje ludziom którzy chcą "sumować" listy ;-). - Alex Martelli


Dlaczego korzystasz z przedłużenia?

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

To powinno działać dobrze.


25
2018-06-04 20:38



To prawdopodobnie tworzy wiele, wiele pośrednich list. - Reut Sharabani
dla python3 from functools import reduce - andorov
Przepraszam, że to naprawdę wolno, zobacz resztę odpowiedzi - Mr_and_Mrs_D


Wydaje się, że jest zamieszanie operator.add! Gdy dodasz dwie listy razem, właściwym terminem jest concatnie dodawaj. operator.concat jest to, czego potrzebujesz.

Jeśli uważasz, że funkcjonalne, to jest tak proste, jak to:

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

Zobaczysz, że zmniejszasz typ sekwencji, więc gdy dostarczasz krotkę, odzyskujesz krotkę. spróbujmy z listą ::

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

Aha, wrócisz do listy.

A co z wydajnością ::

>>> 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 jest dość szybki! Ale nie ma porównania do zmniejszenia z 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



Hmm, aby być uczciwym drugim przykładem powinna być również lista (lub pierwsza krotka?) - Mr_and_Mrs_D


Jeśli chcesz spłaszczyć strukturę danych, w której nie wiesz, jak głęboko jest zagnieżdżona, możesz użyć 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]

To generator, więc musisz rzucić wynik na list lub jawnie iterować nad nim.


Aby spłaszczyć tylko jeden poziom i jeśli każdy z elementów jest sam w sobie iterowalny, możesz również użyć iteration_utilities.flatten który sam w sobie jest cienkim opakowaniem 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]

Aby dodać trochę czasu (na podstawie odpowiedzi Nico Schlömera, która nie zawiera funkcji przedstawionej w tej odpowiedzi):

enter image description here

Jest to wykres log-log, który uwzględnia szeroki zakres wartości. Dla jakościowego rozumowania: Niższy jest lepszy.

Wyniki pokazują, że jeśli iteracja zawiera tylko kilka wewnętrznych iteracji sum będzie najszybszy, jednak na długie iterables tylko itertools.chain.from_iterable, iteration_utilities.deepflatten lub zagnieżdżone zrozumienie ma rozsądną wydajność itertools.chain.from_iterable będąc najszybszym (jak już zauważył 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: Jestem autorem tej biblioteki


17
2017-11-26 00:20



sum nie działa już na dowolnych sekwencjach, od początku 0, robienie functools.reduce(operator.add, sequences) zastępstwo (nie jesteśmy zadowoleni, że usunięto reduce z wbudowanych?). Kiedy typy są znane, może być szybsze w użyciu type.__add__. - Yann Vernier
@YannVernier Dzięki za informacje. Myślałem, że przeprowadziłem te testy porównawcze w Pythonie 3.6 i to działało sum. Czy zdajesz sobie sprawę z tego, które wersje Pythona przestały działać? - MSeifert
Byłem trochę w błędzie. 0 jest po prostu domyślną wartością początkową, więc działa, jeśli używa się rozpocznij argument na początek z pustą listą ... ale nadal ciągi znaków specjalnych i mówi mi, żebym użył join. Wdraża foldl zamiast foldl1. Ten sam problem pojawia się w 2.7. - Yann Vernier