Glätten eines unregelmäßigen Liste von Listen
Ja, ich weiß, dieses Thema wurde abgedeckt, bevor (hier, hier, hier, hier), aber soweit ich weiß, alle Lösungen, bis auf eine, nicht auf eine Liste wie diese:
L = [[[1, 2, 3], [4, 5]], 6]
Wo die gewünschte Ausgabe
[1, 2, 3, 4, 5, 6]
Oder vielleicht noch besser, einen iterator. Die einzige Lösung, die ich sah, das funktioniert für eine beliebige Schachtelung ist gefunden in dieser 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 dieses Modell das beste ist? Hab ich was übersehen? Irgendwelche Probleme?
Die Tatsache, dass es so viele Antworten und so viel Aktion auf diese Frage wirklich vermuten, dass dies eine eingebaute Funktion, irgendwo, richtig? Es ist vor allem schade, dass der compiler.ast wurde entfernt von Python 3.0
Ich würde sagen, dass das, was Python wirklich braucht, ist ungebrochen Rekursion, anstatt ein weiteres builtin.
völlig einverstanden, ist die Tatsache, dass Menschen, die mit offensichtlich schlechten APIs/übermäßig komplizierte Datenstrukturen (nur eine Anmerkung:
Ich würde sagen, dass das, was Python wirklich braucht, ist ungebrochen Rekursion, anstatt ein weiteres builtin.
völlig einverstanden, ist die Tatsache, dass Menschen, die mit offensichtlich schlechten APIs/übermäßig komplizierte Datenstrukturen (nur eine Anmerkung:
list
s soll homogen sein) bedeutet nicht, dass es eine Python ist Schuld und wir müssen ein builtin für eine solche AufgabeInformationsquelleAutor telliott99 | 2010-01-28
Schreibe einen Kommentar Antworten abbrechen
Du musst angemeldet sein, um einen Kommentar abzugeben.
Generator-Funktionen kann Ihr Beispiel ein wenig leichter zu Lesen und wahrscheinlich erhöhen Sie die Leistungsfähigkeit.
Python 2
Benutzte ich die Durchsuchbar ABC Hinzugefügt 2.6.
Python 3
In Python 3, die
basestring
ist nicht mehr, aber Sie können verwenden ein Tupel vonstr
undbytes
den gleichen Effekt zu erhalten gibt.Den
yield from
- operator gibt ein Element aus einem generator, der ein zu einer Zeit. Diese syntax für die übertragung an einen subgenerator wurde Hinzugefügt, 3.3l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9))
im Handumdrehen, als ich diesenlist(flatten(l))
. Alle anderen, würden die arbeiten beginnen und dauern ewig!Auch dies reduziert die Wörterbücher. Vielleicht möchten Sie verwenden
collections.Sequence
stattcollections.Iteratable
?Das funktioniert nicht mit Dingen, die nicht Listen zunächst, z.B.
for i in flatten(42): print (i)
. Dies könnte behoben werden, indem das verschieben derisinstance
-test und die else-Klausel außerhalb derfor el
-Schleife. (Dann könnten Sie werfen nichts, und es würde eine vereinfachte Liste raus)Warum müssen Sie die Verbindung überprüfen
if isinstance(el, collections.Iterable) and not isinstance(el, basestring)
? Warum nicht einfachif not isinstance(el, list)
?In der Tat ist die Rekursion nie benötigt. In diesem speziellen Fall mit Rekursion ist nicht die beste Lösung, wie es zum Absturz auf tief verschachtelte Listen (Tiefe > 1000). Aber wenn Sie nicht Streben an, dass etwas sicher ist, dann, ja, rekursive Funktion sind besser, da Sie so leichter zu Lesen/schreiben.
InformationsquelleAutor Cristian
Meine Lösung:
Ein wenig kürzer, aber so ziemlich das gleiche.
try: iter(x)
um zu testen, ob es durchsuchbar... Aber ich glaube nicht, dass ein import stdlib-Moduls ist ein Nachteil, der es Wert zu vermeiden.Lohnt sich zu beachten, dass diese Lösung funktioniert nur, wenn alle Elemente vom Typ
int
Könnte es präziser,
def flatten(x): return [a for i in x for a in flatten(i)] if isinstance(x, collections.Iterable) else [x]
- aber die Lesbarkeit möglicherweise subjektiv hier.das funktioniert nicht mit strings, da strings sind iterierbar zu. Ersetzen Sie die Bedingung mit
if isinstance(x, collections.Iterable) and not isinstance(x, basestring)
InformationsquelleAutor Josh Lee
Generator version von @unutbu nicht-rekursive Lösung auf Wunsch von @Andrew in einem Kommentar:
Leicht vereinfachte version von diesem generator:
Ich glaube, Sie brauchen, um zu testen, für strings -- zB hinzufügen "und nicht isinstance(l[0], basestring)" wie in Cristian Lösung. Andernfalls erhalten Sie eine unendliche Schleife um l[0:1] = l[0]
Dies ist ein gutes Beispiel der Herstellung eines generator, sondern als c-urchin erwähnt, der Algorithmus selbst schlägt fehl, wenn die Sequenz enthält strings.
InformationsquelleAutor Alex Martelli
Generator mit Rekursion und duck typing (aktualisiert für Python 3):
for i in flatten(item): yield i
Liste(flatten([['X'], 'Y'])) scheitert an 2.X Variante
siehe mein Kommentar oben yours
ja, es schlägt fehl, mit dem Zyklus.. ich denke, dass da ein string ist auch ein array von chars
InformationsquelleAutor dansalmo
Diese version von
flatten
vermeidet Pythons rekursions-Grenze (und somit funktioniert mit beliebig tief geschachtelte iterables). Es ist ein generator, die mit strings und beliebig iterables (sogar unendlich sind).Hier sind einige Beispiele, die demonstrieren, Ihre Verwendung:
Obwohl
flatten
verarbeiten kann unendliche Generatoren, kann es nicht verarbeiten unendliche Verschachtelung:sets
,dicts
,deques
,listiterators
,generators
, filehandles, und benutzerdefinierte Klassen mit__iter__
definiert ist, sind alle Instanzen voncollections.Iterable
, aber nichtcollections.Sequence
. Das Ergebnis der Abflachung einedict
ist ein bisschen zweifelhaft, aber ansonsten finde ichcollections.Iterable
einen besseren Standard alscollections.Sequence
. Es ist definitiv die mehr liberal.Ein problem bei der Verwendung
collections.Iterable
ist, dass diese unendliche Generatoren. Ich habe mich verändert meine Antwort in diesem Fall behandeln.Dies scheint nicht zu funktionieren für die 3. und die 4. Beispiele. Es wirft
StopIteration
. Auch, sieht aus wiewhile True: first = next(remainder)
ersetzt werden könnte durchfor first in remainder:
.InformationsquelleAutor unutbu
Hier meine funktionsfähige version von rekursiven glätten Sie die beiden Griffe Tupel und Listen, und Sie können Sie werfen in einer Mischung von positions-Argumente. Gibt ein generator erzeugt die gesamte Sequenz um, arg von arg:
Verwendung:
e
,a
,n
findenVersuchen
args
fürn
,intermediate
(oder die kürzeremid
oder bevorzugen Sie vielleichtelement
) 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,)))
Dies ist deutlich schneller als
compiler.ast.flatten
. Großer, kompakter code, funktioniert für jeden (denke ich) - Objekt-Typ.InformationsquelleAutor samplebias
Hier ist eine andere Antwort, die ist noch interessanter...
Grundsätzlich, es wandelt die verschachtelte Liste zu einem string, regex verwendet, um Streifen aus der verschachtelte syntax, und dann wandelt das Ergebnis zurück in eine (abgeflachte) Liste.
[['C=64', 'APPLE ]['], ['Amiga', 'Mac', 'ST']]
🙂 Auf der anderen Seite, eine Liste, die enthält sich, es werde tun, ein wenig besser als die anderen Antworten, eine Ausnahme auszulösen, anstatt nur looping, bis Sie laufen aus Speicher/recursing, bis Sie erschöpfen die Stapel...Die ursprüngliche Frage war über die Abflachung eine Liste von Ganzzahlen. Wenn du nur die Liste ändern Verständnis zu d=[x for x in c] sollte funktionieren für Ihre Probe.
Zuerst
[x for x in c]
ist nur eine langsame und ausführliche Weise, um eine Kopiec
, also warum würden Sie das tun? Zweitens, dein code ist eindeutig zu konvertieren'APPLE ]['
in'APPLE '
, weil es nicht in Griff zu zitieren, es nimmt halt irgendwelche Klammern Klammern Liste.Ha! Die Art, wie Ihr Kommentar hat formatiert auf meinem computer, ich war gar nicht bewusst, dass sollte Apple II, wie es schien, auf den alten Computern. In jedem Fall, meine Antwort auf Ihre beiden Fragen ist, dass diese übung--für mich--ist nur ein experiment, um zu finden eine kreative Lösung für die Abflachung einer Liste. Ich bin mir nicht sicher, ob ich das verallgemeinern würde es zu einer Abflachung jede Liste gibt.
Sie müssen nur
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/...InformationsquelleAutor clay
InformationsquelleAutor kev
Könnten Sie
deepflatten
von der 3rd-party-Paketiteration_utilities
:Es ist ein iterator, so dass Sie brauchen, zu Durchlaufen (zum Beispiel durch das einwickeln von es mit
list
oder in einer Schleife). Intern wird es verwendet einen iterativen Ansatz, anstatt einen rekursiven Ansatz, und es ist so geschrieben, als C-Erweiterung, so kann es schneller sein, als Reine python-Ansätze:Ich bin der Autor des
iteration_utilities
Bibliothek.more-itertools
,toolz
, ... die haben schon viel länger. Sie unterscheiden sich gerade ein bisschen in der verfügbaren Funktionalität/Geschwindigkeit/Optionen, aber Sie überschneiden sich in vielerlei Hinsicht.iteration_utilities
ist Recht neu und der einzige "Vorteil" ist, dass es schneller in einigen Fällen als die alternativen. Es ist also wirklich nicht verwunderlich, dass es nicht viel Aufmerksamkeit erhalten.InformationsquelleAutor MSeifert
War es Spaß zu versuchen, um eine Funktion erstellen, die könnte reduzieren unregelmäßigen Liste in Python, aber natürlich ist das, was Python ist für die (um-Programmierung Spaß). Der folgende generator funktioniert Recht gut mit einigen vorbehalten:
Wird es glätten Datentypen, die Sie wollen allein gelassen (wie
bytearray
,bytes
, undstr
Objekte). Auch der code basiert auf der Tatsache, dass der anfragende ein iterator von einem nicht-wiederholenden wirft eineTypeError
.Edit:
Stimme ich mit der vorherigen Implementierung. Das problem ist, dass Sie nicht in der Lage sein zu glätten, etwas, das ist nicht durchsuchbar. Es ist verwirrend und gibt den falschen Eindruck, von das argument.
Den folgenden generator ist fast die gleiche wie die erste, aber nicht das problem, zu versuchen zu glätten, eine nicht-wiederholenden Objekt. Es scheitert, wie man erwarten würde, wenn ein unangebrachtes argument ist ihm gegeben.
Testen der generator arbeitet gut mit der Liste, der geliefert wurde. Aber der neue code wird zu erhöhen eine
TypeError
wenn ein nicht-wiederholenden Objekt ist gegeben. Beispiel sind unten gezeigt an das neue Verhalten.InformationsquelleAutor Noctis Skytower
Zwar eine elegante und sehr pythonic Antwort ausgewählt wurde, möchte ich meine Lösung gerade für die rezension:
Mir bitte sagen, wie gut oder schlecht dieser code ist?
isinstance(i, (tuple, list))
. Initialisieren der leeren Variablen ist ein flag, das für mich zu sehen, um alternativen code-Strukturen, in der Regel Verstehens, Generatoren, Rekursion, etc..return type(l)(ret)
erhalten Sie die gleichen container-Typ zurück, wie die übergeben wurde, auch. 🙂Können Sie bitte erklären, was es bedeutet, in ein wenig detail.
Wenn Sie eine Liste, die Sie wahrscheinlich wollen eine Liste zurück. Wenn Sie ein Tupel, möchten Sie wahrscheinlich ein Tupel zurück. Wenn Sie ein Mischmasch der beiden, erhalten Sie, unabhängig von der äußeren umschließenden Sache war.
InformationsquelleAutor Xolve
Bevorzuge ich einfache Antworten. Keine Generatoren. Keine Rekursion oder Rekursion Grenzen. Nur iteration:
Diese arbeitet mit zwei Listen: eine innere Schleife und eine äußere while-Schleife.
Die innere for-Schleife durchläuft die Liste. Wenn es feststellt, dass ein element in der Liste (1) Liste verwendet.verlängern() zu glätten, die Teil einer Schachtelung und (2) schaltet keepChecking zu Wahren. keepchecking wird verwendet, um die Kontrolle der äußeren while-Schleife. Wenn die äußere Schleife wird auf true gesetzt, löst die innere Schleife für einen weiteren Durchlauf.
Derjenigen Pässe behalten geschieht, bis keine weitere verschachtelte Listen zu finden sind. Wenn ein Durchgang schließlich Auftritt, wo keine zu finden sind, keepChecking wird nie ausgelöst true, was bedeutet listIsNested bleibt falsch und die äußere while-Schleife beendet.
Die vereinfachte Liste wird dann zurückgegeben.
Testlauf
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
Du hast Recht, wenn deine Listen sind wirklich groß und/oder verschachtelt bis in große tiefen. Allerdings, wenn das nicht der Fall ist, dann ist die einfachere Lösung funktioniert genauso gut, und ohne die Tiefe Magie von einigen der anderen Antworten. Es ist ein Ort für mehrstufige, rekursive generator Verstehens, aber ich bin nicht davon überzeugt werden sollen, wo Sie zuerst suchen. (Ich denke, Sie wissen, wo ich die fallen in die "Schlimmer ist Besser" - Debatte.)
Oder anders gesagt, werden Sie nicht haben, um zu "versuchen zu Verstehen" meine Lösung. Wenn die Leistung nicht zu einem Engpass, was Ihnen am wichtigsten ist, wie ein Programmierer?
Einfachere Lösungen haben weniger Logik. Rekursion ist eine ziemlich grundlegende Programmierung konstruieren, dass jeder, der Auffassung, selbst ein Programmierer sollte sein völlig bequem mit. Generatoren sind sehr viel der Python Weg und (zusammen mit Verstehens) sind etwas, das jeder professionelle Python-Programmierer sollten grok sofort.
Ich bin über Rekursion. Wenn ich schrieb meine Antwort, python noch brach Rekursion bei 1000 Zyklen. Haben Sie dies geändert? Für eine professionelle python-Programmierer, der ich nicht bin. Außerdem Stelle ich mir vor, viele Menschen Programmieren in python nicht so tun, Vollzeit.
InformationsquelleAutor clay
Hier ist eine einfache Funktion, flacht Listen von beliebigen Tiefe. Keine Rekursion, um zu vermeiden, stack overflow.
InformationsquelleAutor Wilfred Hughes
Hier ist die
compiler.ast.flatten
Umsetzung in 2.7.5:Gibt es bessere, schnellere Methoden (Wenn Sie bisher hier erreicht haben, haben Sie gesehen, wie Sie bereits)
Beachten Sie auch:
InformationsquelleAutor pradyunsg
Ich bin überrascht, niemand hat das gedacht. Verdammt Rekursion habe ich nicht bekommen, die rekursiv Antworten, die fortschrittliche Menschen hier gemacht. egal, hier ist mein Versuch, auf diese. Nachteil ist, es ist sehr spezifisch für die OP ' s use-case -
Ausgabe:
InformationsquelleAutor Zion
Ich nicht gehen durch all die bereits vorhandenen Antworten hier, aber hier ist ein one-liner, die ich kam mit, in Anlehnung an lisp ist übrigens der erste-und der rest der Liste Verarbeitung
hier ist ein einfaches und ein nicht-so-einfachen Fall -
def foo():
ist eine separate Zeile. Auch dies ist sehr unleserlich.Ich habe de-eine-Linie-freundlich-der code, und hat einige weitere Umgestaltung. (edit anhängig ist peer-review-als ich dies Schreibe) Diese Besondere Methode schien sehr gut lesbar zu mir, obwohl der original-code haben, benötigen einige Umgestaltung.
InformationsquelleAutor Shreyas
völlig hacky, aber ich denke, es würde funktionieren (je nach data_type)
InformationsquelleAutor Joran Beasley
Hier ist ein weiterer py2 Ansatz, ich bin nicht sicher, ob die Schnellste oder die eleganteste, noch die sicherste ...
Kann es ignorieren, die spezifische (oder abgeleitet) Typ, den Sie möchten, es gibt einen iterator, so können Sie wandeln es zu jedem bestimmten container wie list, tuple, dict oder einfach verbrauchen, um weniger Speicherbedarf, für besser oder schlechter damit umgehen können ersten nicht-wiederholenden Objekte wie int ...
Hinweis: die meisten der schweren lifting erfolgt in C, da, soweit ich weiß, das ist, wie itertools umgesetzt werden, so, wenn Sie rekursiv ist, AFAIK, es ist nicht begrenzt durch python Rekursionstiefe, da die Funktionsaufrufe geschehen in C, aber dies bedeutet nicht, Sie sind begrenzt durch den Speicher, speziell in OS X, wo Ihr stack-Größe hat eine Feste Grenze, ab heute (OS X Mavericks) ...
es ist eine etwas schnellere Ansatz, aber weniger portable Methode nur verwenden, wenn Sie davon ausgehen können, dass die Basis-Elemente der Eingabe werden kann, ausdrücklich etwas anderes bestimmt ist, erhalten Sie eine Endlosschleife, und OS X mit seinen begrenzten stack-Größe, werfen Sie einen segmentation fault ziemlich schnell ...
hier sind wir mit Sätzen zu überprüfen, die für die Art so dauert es O(1) vs O(Anzahl von Arten), um zu prüfen, ob nicht ein element sollte ignoriert werden, obwohl natürlich jeder beliebige Wert mit abgeleiteten Typ der angegebenen ignoriert Arten wird scheitern, deshalb ist seine Verwendung
str
,unicode
so verwenden Sie es mit Vorsicht ...tests:
InformationsquelleAutor Samy Vilar
Mit
itertools.chain
:Oder ohne Verkettung:
InformationsquelleAutor Saksham Varma
Ich verwendet rekursiv zu lösen verschachtelte Liste mit beliebiger Tiefe
So, nachdem ich die Funktion definieren combine_nlist, es ist einfach, um diese Funktion zu nutzen tun Planschleifen. Oder kombinieren Sie es in einer Funktion. Ich mag meine Lösung, weil es kann angewendet werden auf jede verschachtelte Liste.
Ergebnis
current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded
hmmm ich versuchen Sie zu flaten Liste mit mehr als 1000 Ebenen?
Natürlich, das ist der ganze Punkt der Diskussion über rekursive vs. iterative Lösungen. Wenn Sie im Voraus wissen, dass die Anzahl der Schichten < als 1000 dann die einfachste Lösung wird funktionieren. Wenn Sie sagen, "Tiefe" dazu gehört eine Liste mit Tiefe > 1000.
InformationsquelleAutor Oldyoung
Der einfachste Weg ist die Verwendung des morph Bibliothek mit
pip install morph
.Der code ist:
InformationsquelleAutor YPCrumble
Ich bin mir bewusst dass es schon viele geniale Antworten, aber ich wollte eine Antwort, die verwendet die funktionale Programmierung-Methode der Lösung der Frage. In dieser Antwort, die ich machen Verwendung von Doppel-Rekursion :
Ausgabe:
InformationsquelleAutor Leo wahyd
Ich bin mir nicht sicher, ob dies unbedingt schneller oder effektiver, aber das ist was ich tun:
Den
flatten
Funktion stellt die Liste in einen string nimmt alle der eckigen Klammern, befestigt eckigen Klammern zurück auf die enden, und wandelt es wieder in eine Liste.Obwohl, wenn Sie wüssten, Sie müssten die eckigen Klammern in Ihre Liste der Streicher, wie
[[1, 2], "[3, 4] and [5]"]
, Sie hätte etwas anderes zu tun.InformationsquelleAutor diligar
Beim Versuch, solche Fragen zu beantworten, die Sie wirklich brauchen, um die Einschränkungen des Codes, den Sie vorschlagen, eine Lösung. Wenn es nur über die Leistungen, die ich würde nicht dagegen zu viel, aber die meisten der codes vorgeschlagen, als Lösung (einschließlich die akzeptierte Antwort) nicht zu glätten jede Liste hat eine Tiefe, die größer als 1000.
Wenn ich sage die meisten der codes ich meine alle codes, die jede form der Rekursion (oder rufen Sie eine standard-Bibliothek-Funktion, die rekursiv). Alle diese codes scheitern, weil für jeden rekursiven Aufruf, der (anrufen), stack wachsen, die durch eine Einheit, und die (Standard -) python-Aufrufliste hat eine Größe von 1000.
Wenn Sie nicht allzu vertraut mit den call-stack, dann vielleicht Folgendes helfen (sonst kann man nur einen Bildlauf zu der Umsetzung).
Call-stack-Größe und rekursive Programmierung (dungeon Analogie)
Finden Sie den Schatz und beenden
Stellen Sie sich vor Sie betreten ein riesiges dungeon mit nummerierten Zimmern, auf der Suche nach einem Schatz. Sie kennen nicht den Ort, aber Sie haben einige Indikationen auf, wie um den Schatz zu finden. Jede Indikation ist ein Rätsel (Schwierigkeitsgrad variiert, aber Sie können nicht Vorhersagen, wie hart Sie sein werden). Sie entscheiden, zu denken, ein wenig über eine Strategie, um Zeit zu sparen, Sie machen zwei Beobachtungen:
Beim betreten des Dungeons, Sie feststellen, eine kleine notebook hier. Sie entscheiden, es zu benutzen, um aufzuschreiben, jeden Raum, den Sie verlassen nach der Lösung eines Rätsels (beim betreten eines neuen Raums), auf diese Weise werden Sie in der Lage, um wieder zurück zum Eingang. Das ist eine geniale Idee, Sie nicht einmal einen cent ausgeben Umsetzung Ihrer Strategie.
Geben Sie den dungeon, die Lösung mit großem Erfolg die ersten 1001 Rätsel, aber hier kommt etwas, Sie hatte nicht geplant, Sie haben keinen Platz mehr im notebook, die Sie sich geliehen haben. Sie entscheiden aufgeben Ihrer Suche, wie Sie es vorziehen, nicht dass der Schatz als verloren, für immer im inneren des dungeon (das sieht smart in der Tat).
Ausführung eines rekursiven Programms
Im Grunde ist es genau das gleiche wie der Suche nach dem Schatz. Der Kerker ist die Arbeitsspeicher des Computers, Ihr Ziel ist jetzt nicht, den Schatz zu finden, sondern berechnen eine Funktion (finden f(x) für einen bestimmten x). Die Indikationen sind einfach sub-Routinen, die Ihnen helfen die Lösung f(x). Ihre Strategie ist die gleiche wie die call-stack Strategie, das notebook ist auf dem stack, die Zimmer sind die Funktionen der' Rückkehr-Adressen:
Das problem, das Sie auftreten in der dungeon wird hier gleich der Aufruf-stack hat eine endliche Größe (hier 1000) und daher, wenn Sie zu viele Funktionen ohne Rückgabe zurück dann füllst du den call-stack und Fehler, die Aussehen wie
"sehr Geehrte Abenteurer, ich bin sehr Leid, aber Ihr notebook ist voll":RecursionError: maximum recursion depth exceeded
. Beachten Sie, dass Sie nicht brauchen, Rekursion zu füllen, den call-stack, aber es ist sehr unwahrscheinlich, dass eine nicht-rekursive Aufruf 1000 Funktionen, ohne jemals wieder zurückkehren. Es ist wichtig zu verstehen, auch, dass, sobald Sie von einer Funktion zurückzugeben, wird der call-stack ist befreit von der Adresse verwendet (daher auch der name "Stapel", die Adresse zurück geschoben werden, bevor die Eingabe einer Funktion und holte bei der Rückkehr). Im speziellen Fall einer einfachen Rekursion (eine Funktion, dief
rufen, sich einmal-über-und über -) geben Sief
über und über, bis die Berechnung beendet ist (bis der Schatz gefunden wird) - und Rückreisef
bis Sie zurück zu der Stelle, wo Sie genanntf
in den ersten Platz. Der call-stack wird nie befreit werden von allem, bis zum Ende, wo Sie befreit sich aus alle return-Adressen eine nach der anderen., Wie man dieses Problem vermeiden?
Dass ist eigentlich ziemlich einfach: "don' T verwenden Sie Rekursion, wenn Sie nicht wissen, wie tief es gehen kann". Das ist nicht immer wahr, wie in einigen Fällen, Tail Call recursion Optimiert werden können (TCO -). Aber in python ist dies nicht der Fall, und auch "gut geschrieben" rekursive Funktion nicht optimieren stack verwenden. Es ist ein interessanter Beitrag von Guido über diese Frage: Tail Recursion Elimination.
Es ist eine Technik, die Sie verwenden können, um jede rekursive Funktion iterativ, diese Technik wir nennen konnte bringen Sie Ihr eigenes notebook. Zum Beispiel, in unserem speziellen Fall, wir sind einfach erkunden, eine Liste, einen Raum betreten, ist äquivalent zu der Eingabe eine Unterliste, die Frage, die Sie sich stellen sollten, ist wie kann ich aus einer Liste zu Ihrer übergeordneten Liste? Die Antwort ist nicht so Komplex sind, wiederholen Sie die folgenden, bis die
stack
leer ist:address
undindex
imstack
bei der Eingabe einer neuen Unterliste (beachten Sie, dass eine Liste mit Adresse+index ist auch eine Adresse, also wir benutzen Sie einfach den exakt gleichen Technik, die verwendet wird, durch den Aufruf-stack);yield
es (oder fügen Sie Sie in eine Liste);stack
zurückaddress
(undindex
).Beachten Sie auch, dass dies äquivalent zu einem DFS-Baum, wo einige Knoten sind Teillisten
A = [1, 2]
und einige einfache Elemente:0, 1, 2, 3, 4
(fürL = [0, [1,2], 3, 4]
). Der Baum sieht wie folgt aus:Den DFS-Traversierung pre-order: L, 0, A, 1, 2, 3, 4. Denken Sie daran, um eine iterative DFS Sie auch "brauchen" einen Stapel. Die Umsetzung schlug ich vor Ergebnis, mit den folgenden Staaten (für die
stack
und dieflat_list
):In diesem Beispiel die maximale stack-Größe ist 2, weil die input-Liste (und somit auch der Baum) haben Tiefe 2.
Umsetzung
Für die Umsetzung in python können Sie vereinfachen ein wenig durch die Verwendung von Iteratoren anstelle von einfachen Listen. Verweise auf die (sub -) Iteratoren werden verwendet, um zu speichern Teillisten zurückgeben Adressen (anstatt der Listen-Adresse und den index). Das ist kein großer Unterschied, aber ich glaube, das ist besser lesbar (und auch ein bisschen schneller):
Beachten Sie auch, dass in
is_list_like
ich habeisinstance(item, list)
, was könnte geändert werden, um zu handhaben, input-Typen, hier wollte ich nur die einfachste version, wo (durchsuchbar) ist nur eine Liste. Aber das könnte man auch machen:Diese Auffassung, strings als "einfache Elemente" und daher
flatten_iter([["test", "a"], "b])
zurück["test", "a", "b"]
und nicht["t", "e", "s", "t", "a", "b"]
. Bemerkung, dass in diesem Falliter(item)
genannt wird, zweimal auf jedes Element, lasst uns so tun, es ist eine übung für den Leser dieser Reiniger.Prüfung und Bemerkungen, die auf anderen Implementierungen
Am Ende, denken Sie daran, dass Sie nicht drucken kann ein unendlich verschachtelte Liste
L
mitprint(L)
weil es intern verwenden rekursive Aufrufe__repr__
(RecursionError: maximum recursion depth exceeded while getting the repr of an object
). Aus dem gleichen Grund, Lösungenflatten
mitstr
fehl mit der gleichen Fehlermeldung.Wenn Sie brauchen, um zu testen Ihrer Lösung können Sie diese Funktion verwenden, um zu generieren, eine einfache verschachtelte Liste:
Gibt:
build_deep_list(5)
>>>[4, [3, [2, [1, [0]]]]]
.InformationsquelleAutor cglacet
Dies ist eine einfache Umsetzung von flatten auf python2
InformationsquelleAutor Statham
Einfach ein
funcy
Bibliothek:pip install funcy
InformationsquelleAutor ADR
Wenn Sie wie Rekursion, das könnte eine Lösung sein, die für Sie von Interesse:
Ich eigentlich angepasst, dieses aus einige Praxis-Schema-code, der ich geschrieben hatte, eine Weile zurück.
Genießen!
InformationsquelleAutor inspectorG4dget
Ich bin neu in python und kommen aus einem lisp-hintergrund. Dies ist, was ich kam mit (check-out die var-Namen für lulz):
Scheint zu funktionieren. Test:
gibt:
InformationsquelleAutor Michael Puckett
Sehe ich nicht so etwas geschrieben, um hier und habe gerade hier von einer geschlossenen Frage auf das gleiche Thema, aber warum nicht einfach etwas wie das hier tun(wenn Sie wissen, die Art der Liste, die Sie teilen möchten):
Würden Sie brauchen, zu wissen, die Art der Elemente, aber ich denke, dies kann verallgemeinert werden und in Bezug auf Geschwindigkeit, ich denke, es wäre schneller.
"warum nicht einfach etwas wie das hier tun", sagen Sie? Denn es ist sehr leicht zu brechen! Sehr schlechte Idee. Ein Beispiel, was passiert, wenn Ihre Elemente sind strings, ints nicht? Dann enthält eine Zeichenfolge ein '[' Sie sind zum scheitern verurteilt. Und was ist, wenn Ihre Elemente haben keine guten (oder sehr langen) string-Darstellung?
Nun, was, wenn das war, was der op nötig? und das Beispiel war eindeutig eine Liste von
ints
so "was ist wenn" nicht hier, hatte die OP anders angegeben, sind aber dann wieder er nicht so, dies ist eine der einfachsten und die meisten gültigen Antworten je nach dem, was gegeben wurde.Naja sorry, "was wäre wenn" anwenden, sorgfältigen überlegungen aller "was wäre wenn" ist das Blut und Eingeweide der Programmierung.
InformationsquelleAutor Bogdan
Ohne Bibliothek:
InformationsquelleAutor alfasin