Ja, ich weiß, dass dieses Thema bereits behandelt wurde ( hier , hier , hier , hier ), aber soweit ich weiß, schlagen alle Lösungen außer einer auf einer Liste wie dieser fehl:
L = [[[1, 2, 3], [4, 5]], 6]
Wo die gewünschte Ausgabe ist
[1, 2, 3, 4, 5, 6]
Oder vielleicht sogar noch besser, ein Iterator. Die einzige Lösung, die ich für eine beliebige Verschachtelung gesehen habe, ist diese Frage :
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)
Ist das das beste Modell? Habe ich etwas übersehen? Irgendwelche Probleme?
python
list
optimization
nested-lists
flatten
telliott99
quelle
quelle
list
s sollen homogen sein), nicht bedeuten, dass es ein Python-Fehler ist und wir für diese Aufgabe eine integrierte Funktion benötigenAntworten:
Die Verwendung von Generatorfunktionen kann das Lesen Ihres Beispiels erleichtern und wahrscheinlich die Leistung steigern.
Python 2
Ich habe das in 2.6 hinzugefügte Iterable ABC verwendet .
Python 3
In Python 3 ist das
basestring
nicht mehr, aber Sie können ein Tupel vonstr
und verwendenbytes
, um dort den gleichen Effekt zu erzielen.Der
yield from
Bediener gibt einen Artikel einzeln von einem Generator zurück. Diese Syntax zum Delegieren an einen Subgenerator wurde in 3.3 hinzugefügtquelle
l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))
im Handumdrehen abgeflacht hat, als ich dies tatlist(flatten(l))
. Alle anderen würden anfangen zu arbeiten und ewig dauern!collections.Sequence
statt verwendencollections.Iteratable
?for i in flatten(42): print (i)
. Dies könnte behoben werden, indem derisinstance
-test und die else-Klausel außerhalb derfor el
-loop verschoben werden. (Dann könnten Sie alles darauf werfen, und es würde eine abgeflachte Liste daraus machen)collections.Iterable
veraltet. Verwenden Siecollections.abc.Iterable
stattdessen.Meine Lösung:
Ein bisschen prägnanter, aber ziemlich gleich.
quelle
try: iter(x)
testen möchten, ob es iterierbar ist. Aber ich denke nicht, dass es ein Nachteil ist, ein stdlib-Modul importieren zu müssen.int
def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]
aber die Lesbarkeit könnte hier subjektiv sein.if isinstance(x, collections.Iterable) and not isinstance(x, basestring)
Generator mit Rekursion und Ententypisierung (aktualisiert für Python 3):
quelle
for i in flatten(item): yield i
Generatorversion der nicht rekursiven Lösung von @ unutbu, wie von @Andrew in einem Kommentar angefordert:
Leicht vereinfachte Version dieses Generators:
quelle
Hier ist meine funktionale Version von rekursivem Abflachen, die sowohl Tupel als auch Listen verarbeitet und es Ihnen ermöglicht, eine beliebige Mischung von Positionsargumenten einzugeben. Gibt einen Generator zurück, der die gesamte Sequenz in der Reihenfolge arg by arg erzeugt:
Verwendungszweck:
quelle
e
,a
,n
beziehen sich aufargs
fürn
,intermediate
(oder die kürzeremid
oder Sie es vorziehen könntenelement
) füra
undresult
füre
, so:flatten = lambda *args: (result for mid in args for result in (flatten(*mid) if isinstance(mid, (tuple, list)) else (mid,)))
compiler.ast.flatten
. Großartiger, kompakter Code, funktioniert für jeden (glaube ich) Objekttyp.Diese Version von
flatten
vermeidet das Rekursionslimit von Python (und arbeitet daher mit beliebig tiefen, verschachtelten Iterablen). Es ist ein Generator, der Strings und beliebige iterable (auch unendliche) verarbeiten kann.Hier sind einige Beispiele, die seine Verwendung demonstrieren:
Obwohl
flatten
es mit unendlichen Generatoren umgehen kann, kann es nicht mit unendlichen Verschachtelungen umgehen:quelle
sets
,dicts
,deques
,listiterators
,generators
, Dateihandies und benutzerdefinierte Klassen mit__iter__
definierten sind alle Instanzencollections.Iterable
, aber nichtcollections.Sequence
. Das Ergebnis der Abflachung von adict
ist etwas zweifelhaft, aber ansonsten denke ich,collections.Iterable
ist eine bessere Standardeinstellung alscollections.Sequence
. Es ist definitiv liberaler.collections.Iterable
ist, dass dies unendliche Generatoren umfasst. Ich habe meine Antwort in diesem Fall geändert.StopIteration
. Auch sieht aus wiewhile True: first = next(remainder)
könnte durch ersetzt werdenfor first in remainder:
.try-except StopIteration block
.Hier ist eine weitere Antwort, die noch interessanter ist ...
Grundsätzlich konvertiert es die verschachtelte Liste in eine Zeichenfolge, entfernt die verschachtelte Syntax mithilfe eines regulären Ausdrucks und konvertiert das Ergebnis dann zurück in eine (abgeflachte) Liste.
quelle
[['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]
:) Auf der anderen Seite wird eine Liste gegeben , die sich enthält, wird es ein wenig besser als die anderen Antworten, die Erhöhung ein Ausnahme anstatt nur zu schleifen, bis Ihnen der Speicher ausgeht / rekursiv, bis Sie den Stapel erschöpft haben ...[x for x in c]
ist es nur eine langsame und ausführliche Möglichkeit, eine Kopie davon zuc
erstellen. Warum sollten Sie das tun? Zweitens wird der Code eindeutig konvertieren gehen'APPLE ]['
in'APPLE '
, weil es nicht zu zitieren umgehen kann , nimmt sie nur alle Klammern Liste Klammern sind.arr_str = str(arr)
und dann[int(s) for s in re.findall(r'\d+', arr_str)]
wirklich. Siehe github.com/jorgeorpinel/flatten_nested_lists/blob/master/…quelle
Sie können
deepflatten
aus dem Drittanbieter-Paket verwendeniteration_utilities
:Da es sich um einen Iterator handelt, müssen Sie ihn iterieren (z. B. indem Sie ihn mit
list
einer Schleife umschließen oder in einer Schleife verwenden). Intern wird ein iterativer Ansatz anstelle eines rekursiven Ansatzes verwendet und als C-Erweiterung geschrieben, sodass er schneller sein kann als reine Python-Ansätze:Ich bin der Autor der
iteration_utilities
Bibliothek.quelle
Es hat Spaß gemacht, eine Funktion zu erstellen, die unregelmäßige Listen in Python reduzieren kann, aber dafür ist Python natürlich gedacht (damit das Programmieren Spaß macht). Der folgende Generator funktioniert mit einigen Einschränkungen ziemlich gut:
Es wird Datentypen flach , dass Sie allein gelassen möchten (wie
bytearray
,bytes
undstr
Objekte). Der Code beruht auch auf der Tatsache, dass das Anfordern eines Iterators von einem nicht iterierbaren Code a auslöstTypeError
.Bearbeiten:
Ich bin mit der vorherigen Implementierung nicht einverstanden. Das Problem ist, dass Sie nicht in der Lage sein sollten, etwas zu reduzieren, das nicht iterierbar ist. Es ist verwirrend und vermittelt den falschen Eindruck des Arguments.
Der folgende Generator ist fast der gleiche wie der erste, hat jedoch nicht das Problem, ein nicht iterierbares Objekt zu reduzieren. Es schlägt fehl, wie man es erwarten würde, wenn ein unangemessenes Argument dafür gegeben wird.
Das Testen des Generators funktioniert einwandfrei mit der bereitgestellten Liste. Der neue Code löst jedoch ein aus,
TypeError
wenn ihm ein nicht iterierbares Objekt zugewiesen wird. Im Folgenden werden Beispiele für das neue Verhalten gezeigt.quelle
Obwohl eine elegante und sehr pythonische Antwort ausgewählt wurde, würde ich meine Lösung nur zur Überprüfung vorstellen:
Bitte sagen Sie, wie gut oder schlecht dieser Code ist.
quelle
isinstance(i, (tuple, list))
. Das Initialisieren leerer Variablen ist für mich ein Flag, um nach alternativenreturn type(l)(ret)
Sie erhalten auch den gleichen Containertyp zurück, der übergeben wurde. :)Ich bevorzuge einfache Antworten. Keine Generatoren. Keine Rekursion oder Rekursionsgrenzen. Nur Iteration:
Dies funktioniert mit zwei Listen: einer inneren for-Schleife und einer äußeren while-Schleife.
Die innere for-Schleife durchläuft die Liste. Wenn ein Listenelement gefunden wird, verwendet es (1) list.extend (), um diesen Teil einer Verschachtelungsebene zu reduzieren, und (2) schaltet keepChecking auf True. Keepchecking wird verwendet, um die äußere while-Schleife zu steuern. Wenn die äußere Schleife auf true gesetzt wird, wird die innere Schleife für einen weiteren Durchgang ausgelöst.
Diese Durchläufe werden so lange ausgeführt, bis keine verschachtelten Listen mehr gefunden werden. Wenn schließlich ein Pass auftritt, bei dem keiner gefunden wird, wird keepChecking nie auf true ausgelöst, was bedeutet, dass listIsNested false bleibt und die äußere while-Schleife beendet wird.
Die abgeflachte Liste wird dann zurückgegeben.
Testlauf
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
quelle
Hier ist eine einfache Funktion, die Listen beliebiger Tiefe abflacht. Keine Rekursion, um einen Stapelüberlauf zu vermeiden.
quelle
Ich bin überrascht, dass niemand daran gedacht hat. Verdammte Rekursion Ich bekomme nicht die rekursiven Antworten, die die fortgeschrittenen Leute hier gemacht haben. Jedenfalls ist hier mein Versuch dazu. Einschränkung ist, dass es sehr spezifisch für den Anwendungsfall des OP ist
Ausgabe:
quelle
Ich habe hier nicht alle bereits verfügbaren Antworten durchgesehen, aber hier ist ein Einzeiler, den ich mir ausgedacht habe und der von Lisps Art der Erst- und Restlistenverarbeitung übernommen wurde
Hier ist ein einfacher und ein nicht so einfacher Fall -
quelle
def foo():
ist eine separate Zeile. Auch das ist sehr unlesbar.Wenn Sie versuchen, eine solche Frage zu beantworten, müssen Sie wirklich die Einschränkungen des Codes angeben, den Sie als Lösung vorschlagen. Wenn es nur um Leistungen ginge, würde es mir nichts ausmachen, aber die meisten als Lösung vorgeschlagenen Codes (einschließlich der akzeptierten Antwort) können keine Liste mit einer Tiefe von mehr als 1000 abflachen.
Wenn ich die meisten Codes sage sage, meine ich alle Codes, die irgendeine Form der Rekursion verwenden (oder eine rekursive Standardbibliotheksfunktion aufrufen). Alle diese Codes schlagen fehl, da der (Aufruf-) Stapel für jeden rekursiven Aufruf um eine Einheit wächst und der (Standard-) Python-Aufrufstapel eine Größe von 1000 hat.
Wenn Sie mit dem Aufrufstapel nicht allzu vertraut sind, hilft möglicherweise Folgendes: Andernfalls können Sie einfach zur Implementierung scrollen .
Aufrufstapelgröße und rekursive Programmierung (Dungeon-Analogie)
Den Schatz finden und gehen
Stellen Sie sich vor, Sie betreten einen riesigen Kerker mit nummerierten Räumen und suchen nach einem Schatz. Sie kennen den Ort nicht, haben aber einige Hinweise, wie Sie den Schatz finden können. Jede Anzeige ist ein Rätsel (Schwierigkeitsgrad variiert, aber Sie können nicht vorhersagen, wie schwer sie sein werden). Sie beschließen, ein wenig über eine Strategie nachzudenken, um Zeit zu sparen, und machen zwei Beobachtungen:
Wenn Sie den Dungeon betreten, sehen Sie hier ein kleines Notizbuch . Sie beschließen, damit jeden Raum aufzuschreiben, den Sie nach dem Lösen eines Rätsels verlassen (wenn Sie einen neuen Raum betreten). Auf diese Weise können Sie zum Eingang zurückkehren. Das ist eine geniale Idee, Sie werden nicht einmal einen Cent für die Umsetzung Ihrer Strategie ausgeben .
Sie betreten den Dungeon und lösen mit großem Erfolg die ersten 1001 Rätsel, aber hier kommt etwas, das Sie nicht geplant hatten. Sie haben keinen Platz mehr in dem Notizbuch, das Sie ausgeliehen haben. Sie beschließen , Ihre Suche abzubrechen, da Sie es vorziehen, den Schatz nicht zu haben, als für immer im Dungeon verloren zu sein (das sieht in der Tat klug aus).
Ausführen eines rekursiven Programms
Im Grunde ist es genau das Gleiche wie den Schatz zu finden. Der Dungeon ist der Speicher des Computers . Ihr Ziel ist es nun nicht, einen Schatz zu finden, sondern eine Funktion zu berechnen (finden Sie f (x) für ein gegebenes x ). Die Angaben sind einfach Unterprogramme, die Ihnen beim Lösen von f (x) helfen . Ihre Strategie ist dieselbe wie die Call-Stack- Strategie, das Notebook ist der Stack, die Räume sind die Rücksprungadressen der Funktionen:
Das Problem, auf das Sie im Dungeon gestoßen sind, ist hier dasselbe. Der Aufrufstapel hat eine endliche Größe (hier 1000). Wenn Sie also zu viele Funktionen eingeben, ohne zurückzukehren, füllen Sie den Aufrufstapel und haben einen Fehler, der aussieht wie
"Lieber Abenteurer, es tut mir sehr leid, aber dein Notizbuch ist voll": das ruft sich einmal auf - immer und immer wieder -) du wirst immer wieder eingeben, bis die Berechnung abgeschlossen ist (bis der Schatz gefunden ist) und von zurückkehren bis Sie zu dem Ort zurückkehren, an dem Sie zuerst angerufen haben. Der Aufrufstapel wird bis zum Ende, an dem er nacheinander von allen Rücksprungadressen befreit wird, niemals von irgendetwas befreit.RecursionError: maximum recursion depth exceeded
. Beachten Sie, dass Sie keine Rekursion benötigen, um den Aufrufstapel zu füllen. Es ist jedoch sehr unwahrscheinlich, dass ein nicht rekursiver Programmaufruf 1000 funktioniert, ohne jemals zurückzukehren. Es ist auch wichtig zu verstehen, dass nach der Rückkehr von einer Funktion der Aufrufstapel von der verwendeten Adresse befreit wird (daher der Name "Stapel", die Rücksprungadresse wird vor der Eingabe einer Funktion eingegeben und bei der Rückkehr herausgezogen). Im Sonderfall einer einfachen Rekursion (eine Funktionf
f
f
f
Wie vermeide ich dieses Problem?
Das ist eigentlich ziemlich einfach: "Verwenden Sie keine Rekursion, wenn Sie nicht wissen, wie tief sie gehen kann". Dies ist nicht immer der Fall, da in einigen Fällen die Tail Call-Rekursion optimiert werden kann (TCO) . In Python ist dies jedoch nicht der Fall, und selbst eine "gut geschriebene" rekursive Funktion optimiert die Stapelverwendung nicht . Zu dieser Frage gibt es einen interessanten Beitrag von Guido: Eliminierung der Schwanzrekursion .
Es gibt eine Technik, mit der Sie jede rekursive Funktion iterativ machen können. Diese Technik können wir als Ihr eigenes Notizbuch bezeichnen . In unserem speziellen Fall untersuchen wir beispielsweise einfach eine Liste. Das Betreten eines Raums entspricht dem Eingeben einer Unterliste. Die Frage, die Sie sich stellen sollten, lautet: Wie kann ich von einer Liste zu ihrer übergeordneten Liste zurückkehren? Die Antwort ist nicht so komplex. Wiederholen Sie Folgendes, bis das
stack
leer ist:address
undindex
in a,stack
wenn Sie eine neue Unterliste eingeben (beachten Sie, dass eine Listenadresse + ein Index auch eine Adresse ist, daher verwenden wir genau die gleiche Technik, die vom Aufrufstapel verwendet wird).yield
es angezeigt (oder in eine Liste aufgenommen).stack
kehren Sieaddress
index
mit return (und ) zur übergeordneten Liste zurück .Beachten Sie auch, dass dies einer DFS in einem Baum entspricht, in dem einige Knoten Unterlisten
A = [1, 2]
und andere einfache Elemente sind:0, 1, 2, 3, 4
(fürL = [0, [1,2], 3, 4]
). Der Baum sieht so aus:Die Vorbestellung für die DFS-Durchquerung lautet: L, 0, A, 1, 2, 3, 4. Denken Sie daran, dass Sie zur Implementierung einer iterativen DFS auch einen Stapel "benötigen". Die Implementierung, die ich zuvor vorgeschlagen habe, führt zu folgenden Zuständen (für die
stack
und dieflat_list
):In diesem Beispiel beträgt die maximale Größe des Stapels 2, da die Eingabeliste (und damit der Baum) die Tiefe 2 haben.
Implementierung
Für die Implementierung können Sie in Python ein wenig vereinfachen, indem Sie Iteratoren anstelle einfacher Listen verwenden. Verweise auf die (Unter-) Iteratoren werden zum Speichern von Unterlisten-Rücksprungadressen verwendet (anstatt sowohl die Listenadresse als auch den Index zu haben). Dies ist kein großer Unterschied, aber ich denke, dies ist besser lesbar (und auch etwas schneller):
Beachten Sie auch, dass
is_list_like
ich in I haveisinstance(item, list)
, das geändert werden könnte, um mehr Eingabetypen zu verarbeiten, hier nur die einfachste Version haben wollte, in der (iterable) nur eine Liste ist. Das können Sie aber auch tun:Dies betrachtet Zeichenfolgen als "einfache Elemente" und wird daher
flatten_iter([["test", "a"], "b])
zurückgegeben["test", "a", "b"]
und nicht["t", "e", "s", "t", "a", "b"]
. Beachten Sie, dass in diesem Falliter(item)
jedes Element zweimal aufgerufen wird. Stellen Sie sich vor, es sei eine Übung für den Leser, dies sauberer zu machen.Tests und Anmerkungen zu anderen Implementierungen
Denken Sie am Ende daran, dass Sie eine unendlich verschachtelte Liste nicht mit drucken können
L
,print(L)
da intern rekursive Aufrufe von__repr__
(RecursionError: maximum recursion depth exceeded while getting the repr of an object
) verwendet werden. Aus dem gleichen Grundflatten
schlagen Lösungen für das Einbeziehenstr
mit derselben Fehlermeldung fehl.Wenn Sie Ihre Lösung testen müssen, können Sie mit dieser Funktion eine einfache verschachtelte Liste erstellen:
Welches gibt:
build_deep_list(5)
>>>[4, [3, [2, [1, [0]]]]]
.quelle
Hier ist die
compiler.ast.flatten
Implementierung in 2.7.5:Es gibt bessere und schnellere Methoden (Wenn Sie hier angekommen sind, haben Sie sie bereits gesehen)
Beachten Sie auch:
quelle
total hacky aber ich denke es würde funktionieren (abhängig von deinem data_type)
quelle
Verwenden Sie einfach eine
funcy
Bibliothek:pip install funcy
quelle
Hier ist ein weiterer py2-Ansatz. Ich bin mir nicht sicher, ob er der schnellste, eleganteste oder sicherste ist.
Es kann jeden bestimmten (oder abgeleiteten) Typ ignorieren, den Sie möchten. Es gibt einen Iterator zurück, sodass Sie ihn in einen bestimmten Container wie Liste, Tupel, Diktat konvertieren oder einfach verbrauchen können, um den Speicherbedarf zum Guten oder Schlechten zu verringern Es kann anfängliche nicht iterierbare Objekte wie int ...
Beachten Sie, dass der Großteil des schweren Hebens in C ausgeführt wird, da meines Wissens so itertools implementiert sind. AFAIK ist also zwar rekursiv, AFAIK jedoch nicht an die Python-Rekursionstiefe gebunden, da die Funktionsaufrufe in C ausgeführt werden bedeutet nicht, dass Sie an Speicher gebunden sind, insbesondere in OS X, wo die Stapelgröße ab heute eine harte Grenze hat (OS X Mavericks) ...
Es gibt einen etwas schnelleren Ansatz, aber eine weniger portable Methode. Verwenden Sie diese Methode nur, wenn Sie davon ausgehen können, dass die Basiselemente der Eingabe explizit bestimmt werden können. Andernfalls erhalten Sie eine unendliche Rekursion, und OS X mit seiner begrenzten Stapelgröße wird dies tun Wirf ziemlich schnell einen Segmentierungsfehler ...
Hier verwenden wir Mengen, um nach dem Typ zu suchen, sodass O (1) gegen O (Anzahl der Typen) benötigt wird, um zu prüfen, ob ein Element ignoriert werden soll oder nicht, obwohl natürlich jeder Wert mit dem abgeleiteten Typ der angegebenen ignorierten Typen fehlschlägt , deshalb wird es verwendet
str
,unicode
also mit Vorsicht verwenden ...Tests:
quelle
Ohne Bibliothek zu benutzen:
quelle
Verwenden von
itertools.chain
:Oder ohne Verkettung:
quelle
Ich habe rekursiv verwendet, um verschachtelte Listen mit beliebiger Tiefe zu lösen
Nachdem ich die Funktion combin_nlist definiert habe, ist es einfach, diese Funktion zum Abflachen zu verwenden. Oder Sie können es in einer Funktion kombinieren. Ich mag meine Lösung, weil sie auf jede verschachtelte Liste angewendet werden kann.
Ergebnis
quelle
current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
Am einfachsten ist es, die Morph- Bibliothek mit zu verwenden
pip install morph
.Der Code lautet:
quelle
Ich bin mir bewusst, dass es bereits viele großartige Antworten gibt, aber ich wollte eine Antwort hinzufügen, die die funktionale Programmiermethode zur Lösung der Frage verwendet. In dieser Antwort verwende ich die doppelte Rekursion:
Ausgabe:
quelle
Ich bin mir nicht sicher, ob dies notwendigerweise schneller oder effektiver ist, aber das mache ich:
Die
flatten
Funktion hier verwandelt die Liste in eine Zeichenfolge, entfernt alle eckigen Klammern , bringt eckige Klammern wieder an den Enden an und wandelt sie wieder in eine Liste um.Wenn Sie jedoch wüssten, dass Ihre Liste eckige Klammern in Zeichenfolgen enthält,
[[1, 2], "[3, 4] and [5]"]
müssten Sie etwas anderes tun.quelle
Dies ist eine einfache Implementierung von flatten auf python2
quelle
Dadurch wird eine Liste oder ein Wörterbuch (oder eine Liste von Listen oder Wörterbüchern von Wörterbüchern usw.) abgeflacht. Es wird davon ausgegangen, dass die Werte Zeichenfolgen sind, und es wird eine Zeichenfolge erstellt, die jedes Element mit einem Trennzeichen verknüpft. Wenn Sie möchten, können Sie das Ergebnis anschließend mit dem Trennzeichen in ein Listenobjekt aufteilen. Es verwendet die Rekursion, wenn der nächste Wert eine Liste oder eine Zeichenfolge ist. Verwenden Sie das Schlüsselargument, um festzustellen, ob Sie die Schlüssel oder die Werte (setzen Sie den Schlüssel auf false) aus dem Wörterbuchobjekt möchten.
Ausbeuten:
quelle
Wenn Sie Rekursion mögen, könnte dies eine für Sie interessante Lösung sein:
Ich habe dies tatsächlich aus einem Übungsschema-Code übernommen, den ich vor einiger Zeit geschrieben hatte.
Genießen!
quelle
Ich bin neu in Python und komme aus einem lisp Hintergrund. Folgendes habe ich mir ausgedacht (siehe die Variablennamen für lulz):
Scheint zu funktionieren. Prüfung:
kehrt zurück:
quelle