Tak, wiem, że ten temat był już wcześniej omawiany ( tutaj , tutaj , tutaj , tutaj ), ale o ile wiem, wszystkie rozwiązania, z wyjątkiem jednego, zawodzą na takiej liście:
L = [[[1, 2, 3], [4, 5]], 6]
Gdzie jest pożądane wyjście
[1, 2, 3, 4, 5, 6]
A może nawet lepiej, iterator. Jedyne rozwiązanie, jakie widziałem, które działa dla dowolnego zagnieżdżenia, można znaleźć w tym pytaniu :
def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result
flatten(L)
Czy to najlepszy model? Czy coś przeoczyłem? Jakieś problemy?
python
list
optimization
nested-lists
flatten
telliott99
źródło
źródło
list
ma być jednorodny) nie oznacza, że jest to wina Pythona i potrzebujemy wbudowanego do takiego zadaniaOdpowiedzi:
Korzystanie z funkcji generatora może sprawić, że twój przykład będzie trochę łatwiejszy do odczytania i prawdopodobnie zwiększy wydajność.
Python 2
Użyłem Iterable ABC dodanego w wersji 2.6.
Python 3
W Pythonie 3
basestring
nie ma już, ale możesz użyć krotkistr
i,bytes
aby uzyskać ten sam efekt.yield from
Operator zwraca element z jednego generatora na raz. Ta składnia delegowania do subgeneratora została dodana w 3.3źródło
l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))
gdy to zrobiłemlist(flatten(l))
. Wszyscy inni zaczną działać i będą trwać wiecznie!collections.Sequence
zamiastcollections.Iteratable
?for i in flatten(42): print (i)
. Można to naprawić, przesuwającisinstance
klauzulę -test i else-pozafor el
pętlę. (Wtedy mógłbyś cokolwiek na to rzucić, a to by z niego spłaszczyło listę)collections.Iterable
jest przestarzałe. Użyjcollections.abc.Iterable
zamiast tego.Moje rozwiązanie:
Trochę bardziej zwięzły, ale prawie taki sam.
źródło
try: iter(x)
przetestujesz, czy jest to iterowalne… Ale nie sądzę, że importowanie modułu stdlib jest wadą, której warto unikać.int
def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]
ale czytelność może być tutaj subiektywna.if isinstance(x, collections.Iterable) and not isinstance(x, basestring)
Generator wykorzystujący rekurencję i pisanie kaczych (zaktualizowany dla Python 3):
źródło
for i in flatten(item): yield i
Wersja generatora nierekurencyjnego rozwiązania @ unutbu, zgodnie z żądaniem @Andrew w komentarzu:
Nieco uproszczona wersja tego generatora:
źródło
Oto moja funkcjonalna wersja rekurencyjnego spłaszczania, która obsługuje zarówno krotki, jak i listy, i pozwala wrzucić dowolną mieszankę argumentów pozycyjnych. Zwraca generator, który produkuje całą sekwencję w kolejności, arg po arg:
Stosowanie:
źródło
e
,a
,n
patrzargs
dlan
,intermediate
(lub krótszymid
lub może woliszelement
) dlaa
iresult
dlae
tak:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
compiler.ast.flatten
. Świetny, zwarty kod, działa na każdym (chyba) typie obiektu.Ta wersja
flatten
pozwala uniknąć limitu rekurencji Pythona (a zatem działa z dowolnie głębokimi, zagnieżdżonymi iteracjami). Jest to generator, który może obsługiwać ciągi znaków i dowolne iterowalne (nawet nieskończone).Oto kilka przykładów demonstrujących jego użycie:
Chociaż
flatten
może obsługiwać nieskończone generatory, nie może obsługiwać nieskończonego zagnieżdżania:źródło
sets
,dicts
,deques
,listiterators
,generators
, Uchwytów plików oraz niestandardowe zajęcia z__iter__
zdefiniowane są wszystkie przypadkicollections.Iterable
, ale niecollections.Sequence
. Rezultat spłaszczenia adict
jest nieco niepewny, ale poza tym uważam, żecollections.Iterable
lepszym rozwiązaniem jest domyślnie niżcollections.Sequence
. To zdecydowanie bardziej liberalne.collections.Iterable
jest to, że obejmuje to nieskończone generatory. Zmieniłem odpowiedź na tę sprawę.StopIteration
. Wygląda na to, żewhile True: first = next(remainder)
można go zastąpićfor first in remainder:
.try-except StopIteration block
.Oto kolejna odpowiedź, która jest jeszcze bardziej interesująca ...
Zasadniczo konwertuje zagnieżdżoną listę na ciąg, używa wyrażenia regularnego, aby usunąć zagnieżdżoną składnię, a następnie konwertuje wynik z powrotem na (spłaszczoną) listę.
źródło
[['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]
:) Z drugiej strony, biorąc pod uwagę listę, która zawiera samą siebie, zrobi to trochę lepiej niż inne odpowiedzi, podnosząc wyjątek zamiast tylko zapętlania, aż skończy się pamięć / rekursowanie, aż do wyczerpania stosu ...[x for x in c]
jest to powolny i pełny sposób na zrobienie kopiic
, więc dlaczego miałbyś to zrobić? Po drugie, twój kod oczywiście zamieni się'APPLE ]['
w'APPLE '
, ponieważ nie obsługuje cytowania, po prostu zakłada, że wszelkie nawiasy są nawiasami listowymi.arr_str = str(arr)
a potem[int(s) for s in re.findall(r'\d+', arr_str)]
naprawdę. Zobacz github.com/jorgeorpinel/flatten_nested_lists/blob/master/…źródło
Możesz użyć
deepflatten
z pakietu innej firmyiteration_utilities
:Jest to iterator, więc musisz iterować (na przykład owijając go
list
lub używając w pętli). Wewnętrznie wykorzystuje podejście iteracyjne zamiast podejścia rekurencyjnego i jest napisane jako rozszerzenie C, dzięki czemu może być szybsze niż podejście czysto pythonowe:Jestem autorem
iteration_utilities
biblioteki.źródło
Zabawnie było stworzyć funkcję, która mogłaby spłaszczyć nieregularne listy w Pythonie, ale oczywiście do tego właśnie służy Python (aby programowanie było przyjemnością). Poniższy generator działa dość dobrze z pewnymi zastrzeżeniami:
Będzie spłaszczyć typy danych, które można chcesz pozostawione same (jak
bytearray
,bytes
orazstr
obiektów). Ponadto kod opiera się na fakcie, że żądanie iteratora od nie iterowalnego powoduje podniesienie wartości aTypeError
.Edytować:
Nie zgadzam się z poprzednim wdrożeniem. Problem polega na tym, że nie powinieneś być w stanie spłaszczyć czegoś, co nie jest iterowalne. Jest to mylące i daje błędne wrażenie argumentu.
Poniższy generator jest prawie taki sam jak pierwszy, ale nie ma problemu ze spłaszczeniem obiektu, który nie jest iterowalny. Nie udaje się, jak można się spodziewać, gdy zostanie podany niewłaściwy argument.
Testowanie generatora działa poprawnie z dostarczoną listą. Jednak nowy kod podniesie wartość,
TypeError
gdy zostanie mu podany obiekt nieuleczalny. Przykłady pokazano poniżej nowego zachowania.źródło
Chociaż wybrano elegancką i bardzo pytoniczną odpowiedź, przedstawię moje rozwiązanie tylko do recenzji:
Powiedz, jak dobry lub zły jest ten kod?
źródło
isinstance(i, (tuple, list))
. Inicjowanie pustych zmiennych jest dla mnie flagą do szukania alternatywnych struktur kodu, zwykle pojęć, generatorów, rekurencji itp.return type(l)(ret)
otrzymamy z powrotem ten sam typ kontenera, który został przekazany. :)Wolę proste odpowiedzi. Brak generatorów. Brak limitów rekurencyjnych lub rekurencyjnych. Tylko iteracja:
Działa to z dwiema listami: wewnętrzną pętlą for i zewnętrzną pętlą while.
Wewnętrzna pętla for iteruje listę. Jeśli znajdzie element listy, to (1) używa list.extend () do spłaszczenia tej części pierwszego poziomu zagnieżdżenia i (2) przełącza opcję KeepChecking na True. keepchecking służy do sterowania zewnętrzną pętlą while. Jeśli zewnętrzna pętla zostanie ustawiona na wartość true, wyzwala wewnętrzną pętlę dla kolejnego przejścia.
Te przejścia odbywają się, dopóki nie zostaną znalezione zagnieżdżone listy. Kiedy w końcu nastąpi podanie, gdy nie zostanie znalezione, keepChecking nigdy nie zostanie wyzwolony na true, co oznacza, że listIsNested pozostaje fałszywy, a zewnętrzna pętla while kończy działanie.
Spłaszczona lista jest następnie zwracana.
Testowe uruchomienie
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
źródło
Oto prosta funkcja, która spłaszcza listy o dowolnej głębokości. Brak rekurencji, aby uniknąć przepełnienia stosu.
źródło
Dziwię się, że nikt o tym nie pomyślał. Cholerna rekursja Nie otrzymuję rekurencyjnych odpowiedzi, które zrobili tu zaawansowani ludzie. w każdym razie tutaj jest moja próba. zastrzeżenie jest bardzo specyficzne dla przypadku użycia PO
wynik:
źródło
Nie przejrzałem tutaj wszystkich już dostępnych odpowiedzi, ale oto jeden linijka, którą wymyśliłem, zapożyczając z pierwszego sposobu lisp i przetwarzania listy odpoczynku
oto jedna prosta i jedna nie taka prosta sprawa -
źródło
def foo():
jest to osobna linia. Jest to również bardzo nieczytelne.Próbując odpowiedzieć na takie pytanie, naprawdę musisz podać ograniczenia kodu, który zaproponujesz jako rozwiązanie. Gdyby chodziło tylko o występy, nie miałbym nic przeciwko, ale większość kodów zaproponowanych jako rozwiązanie (w tym zaakceptowana odpowiedź) nie spłaszcza żadnej listy o głębokości większej niż 1000.
Kiedy mówię większość kodów, mam na myśli wszystkie kody, które używają dowolnej formy rekurencji (lub wywołują standardową funkcję biblioteki, która jest rekurencyjna). Wszystkie te kody zawodzą, ponieważ dla każdego z wykonanych wywołań rekurencyjnych stos (wywołań) rośnie o jedną jednostkę, a stos (domyślny) wywołań python ma rozmiar 1000.
Jeśli nie znasz się zbytnio na stosie wywołań, być może poniższe informacje pomogą (w przeciwnym razie możesz po prostu przewinąć do Implementacji ).
Rozmiar stosu wywołań i programowanie rekurencyjne (analogia lochów)
Odnalezienie skarbu i wyjście
Wyobraź sobie, że wchodzisz do ogromnego lochu z ponumerowanymi pokojami i szukasz skarbu. Nie znasz tego miejsca, ale masz pewne wskazówki, jak znaleźć skarb. Każde wskazanie jest zagadką (trudność jest różna, ale nie można przewidzieć, jak trudne będą). Postanawiasz trochę pomyśleć o strategii oszczędzania czasu, robisz dwie obserwacje:
Wchodząc do lochu, zauważysz mały notatnik . Postanawiasz użyć go do spisania każdego pomieszczenia, z którego wyjdziesz po rozwiązaniu zagadki (po wejściu do nowego pokoju), w ten sposób będziesz mógł wrócić z powrotem do wejścia. To genialny pomysł, nawet nie wydasz ani grosza wdrożenie swojej strategii.
Wchodzisz do lochu, rozwiązując z powodzeniem pierwsze 1001 zagadek, ale nadchodzi coś, czego nie planowałeś, nie ma już miejsca w pożyczonym notesie. Postanawiasz porzucić swoją misję, ponieważ wolisz nie mieć skarbu niż zagubić się na zawsze w lochu (to wygląda naprawdę mądrze).
Wykonywanie programu rekurencyjnego
Zasadniczo jest to dokładnie to samo, co znalezienie skarbu. Loch jest pamięcią komputera , Twoim celem nie jest teraz znalezienie skarbu, ale obliczenie jakiejś funkcji (znajdź f (x) dla danego x ). Wskazania są po prostu podprogramami, które pomogą ci rozwiązać f (x) . Twoja strategia jest taka sama jak strategia stosu wywołań , notebook to stos, pokoje to adresy zwrotne funkcji:
Problem napotkany w lochu będzie tutaj taki sam, stos wywołań ma skończony rozmiar (tutaj 1000), a zatem jeśli wprowadzisz zbyt wiele funkcji bez powrotu, wypełnisz stos wywołań i pojawi się błąd, który wygląda jak
„Drogi poszukiwaczu przygód, bardzo mi przykro, ale twój notatnik jest pełny”:RecursionError: maximum recursion depth exceeded
. Zauważ, że nie potrzebujesz rekurencji, aby wypełnić stos wywołań, ale jest bardzo mało prawdopodobne, aby nierekurencyjny program wywoływał 1000 funkcji bez powrotu. Ważne jest również, aby zrozumieć, że po powrocie z funkcji stos wywołań jest zwalniany z użytego adresu (stąd nazwa „stos”, adres zwrotny jest wpychany przed wejściem do funkcji i wyciągany podczas powrotu). W szczególnym przypadku prostej rekurencji (funkcjaf
które wywołują się raz po raz - raz za razem - będziesz wchodziłf
w kółko, aż obliczenia się zakończą (aż do znalezienia skarbu) i powrócisz,f
dopóki nie wrócisz do miejsca, do którego dzwoniłeśf
w pierwszej kolejności. Stos wywołań nigdy nie zostanie uwolniony od niczego, dopóki nie zostanie zwolniony ze wszystkich adresów zwrotnych jeden po drugim.Jak uniknąć tego problemu?
To właściwie dość proste: „nie używaj rekurencji, jeśli nie wiesz, jak głęboko może ona sięgać”. Nie zawsze jest to prawdą, ponieważ w niektórych przypadkach rekurencję Tail Call można zoptymalizować (TCO) . Ale w Pythonie tak nie jest, a nawet „dobrze napisana” funkcja rekurencyjna nie zoptymalizuje wykorzystania stosu. Guido ma interesujący post na ten temat: Eliminacja rekurencji ogona .
Istnieje technika, której można użyć do iteracji dowolnej funkcji rekurencyjnej, którą możemy nazwać przyniesieniem własnego notatnika . Na przykład w naszym konkretnym przypadku po prostu przeglądamy listę, wejście do pokoju jest równoznaczne z wejściem na listę podrzędną. Pytanie, które powinieneś sobie zadać, to jak mogę wrócić z listy do listy nadrzędnej? Odpowiedź nie jest tak skomplikowana, powtarzaj następujące czynności, aż
stack
będzie pusta:address
iindex
wstack
przypadku wprowadzania nowego podmenu (Należy pamiętać, że adres lista + indeks jest również adres, dlatego wystarczy użyć dokładnie taką samą technikę stosowaną przez stos wywołań);yield
to (lub dodaj je do listy);stack
returnaddress
(iindex
) .Zauważ również, że jest to równoważne z DFS w drzewie, w którym niektóre węzły są listami podrzędnymi,
A = [1, 2]
a niektóre są prostymi elementami:0, 1, 2, 3, 4
(dlaL = [0, [1,2], 3, 4]
). Drzewo wygląda następująco:Wstępne zamówienie przejścia DFS to: L, 0, A, 1, 2, 3, 4. Pamiętaj, że aby zaimplementować iteracyjny DFS, musisz również „mieć stos”. Wdrożenie, które zaproponowałem wcześniej, skutkuje następującymi stanami (dla
stack
iflat_list
):W tym przykładzie maksymalny rozmiar stosu wynosi 2, ponieważ lista wejściowa (a zatem drzewo) ma głębokość 2.
Realizacja
W przypadku implementacji w Pythonie można nieco uprościć, używając iteratorów zamiast prostych list. Odniesienia do (pod) iteratorów będą używane do przechowywania adresów zwrotnych list podrzędnych (zamiast posiadania zarówno adresu listy, jak i indeksu). Nie jest to duża różnica, ale uważam, że jest to bardziej czytelne (a także nieco szybsze):
Zauważ też, że w „
is_list_like
Mam”isinstance(item, list)
, który można zmienić w celu obsługi większej liczby typów danych wejściowych, tutaj chciałem mieć najprostszą wersję, w której (iterowalna) jest tylko listą. Ale możesz też to zrobić:Traktuje to ciągi jako „proste elementy” i dlatego
flatten_iter([["test", "a"], "b])
wróci["test", "a", "b"]
i nie["t", "e", "s", "t", "a", "b"]
. Zauważ, że w takim przypadkuiter(item)
jest wywoływany dwukrotnie na każdym elemencie, udawajmy, że jest to ćwiczenie dla czytelnika, aby uczynić to czystszym.Testowanie i uwagi na temat innych wdrożeń
W końcu, należy pamiętać, że nie można wydrukować nieskończenie zagnieżdżonej listy
L
używającprint(L)
ponieważ wewnętrznie użyje do wywołań cyklicznych__repr__
(RecursionError: maximum recursion depth exceeded while getting the repr of an object
). Z tego samego powodu rozwiązaniaflatten
dotyczącestr
niepowodzenia zakończy się niepowodzeniem z tym samym komunikatem o błędzie.Jeśli potrzebujesz przetestować swoje rozwiązanie, możesz użyć tej funkcji do wygenerowania prostej listy zagnieżdżonej:
Co daje:
build_deep_list(5)
>>>[4, [3, [2, [1, [0]]]]]
.źródło
Oto
compiler.ast.flatten
implementacja w 2.7.5:Są lepsze, szybsze metody (jeśli tu dotarłeś, już je widziałeś)
Uwaga:
źródło
całkowicie hacky, ale myślę, że to zadziała (w zależności od typu data_type)
źródło
Wystarczy użyć
funcy
biblioteki:pip install funcy
źródło
Oto inne podejście do py2, nie jestem pewien, czy jest to najszybsze, najbardziej eleganckie i najbezpieczniejsze ...
Może zignorować dowolny określony (lub wyprowadzony) typ, który chcesz, zwraca iterator, dzięki czemu można go przekonwertować na dowolny konkretny kontener, taki jak lista, krotka, dykta lub po prostu zużyć w celu zmniejszenia zużycia pamięci, na lepsze lub gorsze może obsłużyć początkowe obiekty, które nie są iterowalne, takie jak int ...
Zauważ, że większość ciężkiego podnoszenia odbywa się w C, ponieważ o ile wiem, jak to jest zaimplementowane itertools, więc podczas gdy jest rekurencyjny, AFAIK nie jest ograniczony głębokością rekurencji pytona, ponieważ wywołania funkcji występują w C, chociaż to nie oznacza, że jesteś ograniczony pamięcią, szczególnie w OS X, gdzie jego rozmiar stosu ma obecnie twardy limit (OS X Mavericks) ...
istnieje nieco szybsze podejście, ale mniej przenośna metoda, użyj go tylko wtedy, gdy możesz założyć, że podstawowe elementy danych wejściowych można jawnie określić inaczej, otrzymasz nieskończoną rekurencję, a OS X z ograniczonym rozmiarem stosu będzie rzucić błąd segmentacji dość szybko ...
tutaj używamy zestawów do sprawdzania typu, więc potrzeba O (1) vs O (liczba typów), aby sprawdzić, czy element powinien zostać zignorowany, ale oczywiście każda wartość z typem pochodnym podanych ignorowanych typów zawiedzie , dlatego używa
str
,unicode
więc używaj go ostrożnie ...testy:
źródło
Bez użycia biblioteki:
źródło
Używanie
itertools.chain
:Lub bez łączenia:
źródło
Użyłem rekurencji do rozwiązania zagnieżdżonej listy z dowolną głębokością
Więc po zdefiniowaniu funkcji Combine_nlist łatwo jest użyć tej funkcji do spłaszczania. Lub możesz połączyć to w jedną funkcję. Podoba mi się moje rozwiązanie, ponieważ można je zastosować do dowolnej listy zagnieżdżonej.
wynik
źródło
current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
Najprostszym sposobem jest użycie biblioteki Morph
pip install morph
.Kod to:
źródło
Wiem, że jest już wiele niesamowitych odpowiedzi, ale chciałem dodać odpowiedź, która wykorzystuje funkcjonalną metodę programowania rozwiązania problemu. W tej odpowiedzi wykorzystuję podwójną rekurencję:
wynik:
źródło
Nie jestem pewien, czy to niekoniecznie jest szybsze czy bardziej skuteczne, ale właśnie to robię:
Ta
flatten
funkcja zamienia listę w ciąg znaków, usuwa wszystkie nawiasy kwadratowe, przyczepia nawiasy kwadratowe z powrotem na końcach i zamienia z powrotem w listę.Chociaż, gdybyś wiedział, że będziesz mieć nawiasy kwadratowe na liście, na przykład
[[1, 2], "[3, 4] and [5]"]
, będziesz musiał zrobić coś innego.źródło
Jest to prosta implementacja spłaszczania na python2
źródło
Spłaszczy to listę lub słownik (lub listę list lub słowników itp.). Zakłada, że wartości są łańcuchami i tworzy ciąg, który konkatenuje każdy element z argumentem separatora. Jeśli chcesz, możesz użyć separatora, aby podzielić wynik na obiekt listy. Używa rekurencji, jeśli następną wartością jest lista lub ciąg znaków. Użyj argumentu klucza, aby określić, czy chcesz, czy klucze lub wartości (ustaw klucz na false) z obiektu słownika.
daje:
źródło
Jeśli podoba Ci się rekurencja, może to być interesujące dla Ciebie rozwiązanie:
Zaadaptowałem to na podstawie kodu schematu ćwiczeń, który napisałem jakiś czas temu.
Cieszyć się!
źródło
Jestem nowy w Pythonie i pochodzę z seplenia. Oto, co wymyśliłem (sprawdź nazwy var dla Lulz):
Wydaje się, że działa. Test:
zwroty:
źródło