Eine unregelmäßige Liste von Listen abflachen

Question

Ja, ich weiß, dass dieses Thema schon einmal behandelt wurde ( aquí , aquí , aquí , aquí ), aber soweit ich weiß, scheitern alle Lösungen, außer einer, an einer solchen Liste:

L = [[[1, 2, 3], [4, 5]], 6]

Die gewünschte Leistung ist

[1, 2, 3, 4, 5, 6]

Oder vielleicht noch besser, ein Iterator. Die einzige Lösung, die ich gesehen habe, die für eine beliebige Verschachtelung funktioniert, 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 dies das beste Modell? Habe ich etwas übersehen? Gibt es Probleme?

Answer 1

Es hat Spaß gemacht, eine Funktion zu entwickeln, die eine unregelmäßige Liste in Python abflachen kann, aber dafür ist Python ja auch da (damit das Programmieren Spaß macht). Der folgende Generator funktioniert mit einigen Vorbehalten recht gut:

def flatten(iterable):
    try:
        for item in iterable:
            yield from flatten(item)
    except TypeError:
        yield iterable

Es wird Datentypen reduzieren, die Sie vielleicht lieber in Ruhe lassen möchten (wie bytearray , bytes et str Objekte). Außerdem stützt sich der Code auf die Tatsache, dass die Anforderung eines Iterators von einem nicht-iterbaren Objekt ein TypeError .

>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> def flatten(iterable):
    try:
        for item in iterable:
            yield from flatten(item)
    except TypeError:
        yield iterable

>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>>

---

Bearbeiten:

Ich bin mit der bisherigen Umsetzung nicht einverstanden. Das Problem ist, dass man nicht in der Lage sein sollte, etwas zu reduzieren, das keine Iterable ist. Das ist verwirrend und vermittelt einen falschen Eindruck von dem Argument.

>>> list(flatten(123))
[123]
>>>

Der folgende Generator ist fast identisch mit dem ersten, hat aber nicht das Problem, dass er versucht, ein nicht-iterbares Objekt zu glätten. Er scheitert erwartungsgemäß, wenn ihm ein ungeeignetes Argument gegeben wird.

def flatten(iterable):
    for item in iterable:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

Das Testen des Generators funktioniert mit der bereitgestellten Liste problemlos. Der neue Code löst jedoch eine TypeError wenn ihm ein nicht-iterbares Objekt übergeben wird. Im Folgenden werden Beispiele für das neue Verhalten gezeigt.

>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>> list(flatten(123))
Traceback (most recent call last):
  File "<pyshell#32>", line 1, in <module>
    list(flatten(123))
  File "<pyshell#27>", line 2, in flatten
    for item in iterable:
TypeError: 'int' object is not iterable
>>>

Answer 2

Wenn Sie versuchen, eine solche Frage zu beantworten, müssen Sie wirklich die Grenzen des Codes angeben, den Sie als Lösung vorschlagen. Wenn es nur um die Leistung ginge, hätte ich nichts dagegen, aber die meisten der als Lösung vorgeschlagenen Codes (einschließlich der akzeptierten Antwort) schaffen es nicht, eine Liste mit einer Tiefe von mehr als 1000 zu glätten.

Wenn ich sage die meisten der Codes Ich meine alle Codes, die irgendeine Form der Rekursion verwenden (oder eine rekursive Funktion der Standardbibliothek aufrufen). Alle diese Codes schlagen fehl, weil für jeden rekursiven Aufruf der (Aufruf-)Stapel 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, dann hilft Ihnen vielleicht das Folgende (ansonsten können Sie einfach zum Umsetzung ).

Größe des Aufrufstapels und rekursive Programmierung (Dungeon-Analogie)

Suche nach dem Schatz und Ausgang

Stellen Sie sich vor, Sie betreten ein riesiges Kerker mit nummerierten Räumen auf der Suche nach einem Schatz. Du kennst den Ort nicht, aber du hast einige Hinweise wie man den Schatz finden kann. Jeder Hinweis ist ein Rätsel (der 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, Sie machen zwei Beobachtungen:

1. Es ist schwierig (lang), den Schatz zu finden, da du (möglicherweise schwierige) Rätsel lösen musst, um dorthin zu gelangen.
2. Hat man den Schatz gefunden, kann man ganz einfach zum Eingang zurückkehren, indem man denselben Weg in die andere Richtung nimmt (allerdings braucht man ein bisschen Gedächtnis, um sich den Weg zu merken).

Wenn Sie den Kerker betreten, bemerken Sie eine kleine Notizbuch hier. Du beschließt, es zu benutzen, um jeden Raum, den du nach dem Lösen eines Rätsels verlässt (wenn du einen neuen Raum betrittst), aufzuschreiben, damit du zum Eingang zurückkehren kannst. Das ist eine geniale Idee, du wird keinen Cent ausgeben die Umsetzung Ihrer Strategie.

Du betrittst den Kerker und löst mit großem Erfolg die ersten 1001 Rätsel, aber jetzt kommt etwas, was du nicht geplant hattest: Du hast keinen Platz mehr in dem geliehenen Notizbuch. Du beschließt aufgeben deine Suche, da du lieber den Schatz nicht hast, als für immer im Kerker verloren zu sein (das sieht in der Tat clever aus).

Ausführen eines rekursiven Programms

Im Grunde ist es genau das Gleiche, wie den Schatz zu finden. Der Kerker ist der Arbeitsspeicher des Computers Ihr Ziel ist es jetzt nicht, einen Schatz zu finden, sondern eine Funktion zu berechnen (finden f(x) für eine bestimmte x ). Die Hinweise sind einfach Unterprogramme, die Ihnen bei der Lösung von f(x) . Ihre Strategie ist die gleiche wie die der Aufrufstapel Strategie ist das Notizbuch der Stapel, die Räume sind die Rücksprungadressen der Funktionen:

x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected 
print(' '.join(y))

Das Problem, auf das du im Dungeon gestoßen bist, ist hier dasselbe, der Aufrufstapel hat eine endliche Größe (hier 1000) und wenn du zu viele Funktionen eingibst, ohne zurückzukehren, dann füllst du den Aufrufstapel und bekommst einen Fehler, der so aussieht "Lieber Abenteurer, es tut mir sehr leid, aber dein Notizbuch ist voll" : RecursionError: maximum recursion depth exceeded . Beachten Sie, dass Sie keine Rekursion benötigen, um den Aufrufstapel zu füllen, aber es ist sehr unwahrscheinlich, dass ein nicht rekursives Programm 1000 Funktionen aufruft, ohne jemals zurückzukehren. Es ist auch wichtig zu verstehen, dass nach der Rückkehr aus einer Funktion der Aufrufstapel von der verwendeten Adresse befreit wird (daher der Name "Stack", die Rücksprungadresse wird vor dem Eintritt in eine Funktion hineingeschoben und bei der Rückkehr herausgezogen). Im speziellen Fall einer einfachen Rekursion (eine Funktion f der sich einmal selbst anruft - immer und immer wieder -) werden Sie in f immer und immer wieder, bis die Berechnung beendet ist (bis der Schatz gefunden ist) und kehren von f bis Sie zu dem Ort zurückkehren, an dem Sie angerufen haben f an erster Stelle. Der Aufrufstapel wird nie von irgendetwas befreit, bis zum Ende, wo er von allen Rücksprungadressen nacheinander befreit wird.

Wie lässt sich dieses Problem vermeiden?

Das ist eigentlich ganz einfach: "Verwende keine Rekursion, wenn du nicht weißt, wie tief sie gehen kann". Das stimmt nicht immer, denn in einigen Fällen, Tail Call Rekursion kann optimiert werden (TCO) . Aber in Python ist dies nicht der Fall, und selbst "gut geschriebene" rekursive Funktionen werden no die Nutzung des Stapels zu optimieren. Es gibt einen interessanten Beitrag von Guido über diese Frage: Beseitigung der Rekursion am Ende .

Es gibt eine Technik, mit der man jede rekursive Funktion iterativ machen kann, diese Technik könnte man nennen Bringen Sie Ihr eigenes Notizbuch mit . In unserem speziellen Fall zum Beispiel erkunden wir einfach eine Liste, das Betreten eines Raumes ist gleichbedeutend mit dem Betreten einer Unterliste, die Frage, die Sie sich stellen sollten, ist Wie kann ich von einer Liste zu ihrer übergeordneten Liste zurückkehren? Die Antwort ist nicht so kompliziert, wiederholen Sie die folgenden Schritte, bis die stack leer ist:

1. die aktuelle Liste pushen address y index in einem stack bei der Eingabe einer neuen Unterliste (beachten Sie, dass eine Listenadresse+Index auch eine Adresse ist, daher verwenden wir genau die gleiche Technik, die auch der Aufrufstapel verwendet);
2. jedes Mal, wenn ein Gegenstand gefunden wird, yield (oder fügen Sie sie in eine Liste ein);
3. Sobald eine Liste vollständig erforscht ist, kehren Sie zur übergeordneten Liste zurück, indem Sie die stack return address (und index ) .

Beachten Sie auch, dass dies einem DFS in einem Baum entspricht, bei dem einige Knoten Unterlisten sind A = [1, 2] und einige sind einfache Gegenstände: 0, 1, 2, 3, 4 (für L = [0, [1,2], 3, 4] ). Der Baum sieht wie folgt aus:

                    L
                    |
           -------------------
           |     |     |     |
           0   --A--   3     4
               |   |
               1   2

Der DFS-Traversal-Vorauftrag lautet: L, 0, A, 1, 2, 3, 4. Denken Sie daran, dass Sie für die Implementierung eines iterativen DFS auch einen Stack "brauchen". Die Implementierung, die ich zuvor vorgeschlagen habe, führt zu folgenden Zuständen (für die stack und die flat_list ):

init.:  stack=[(L, 0)]
**0**:  stack=[(L, 0)],         flat_list=[0]
**A**:  stack=[(L, 1), (A, 0)], flat_list=[0]
**1**:  stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**:  stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**:  stack=[(L, 2)],         flat_list=[0, 1, 2, 3]
**3**:  stack=[(L, 3)],         flat_list=[0, 1, 2, 3, 4]
return: stack=[],               flat_list=[0, 1, 2, 3, 4]

In diesem Beispiel ist die maximale Größe des Stapels 2, weil die Eingabeliste (und damit der Baum) die Tiefe 2 hat.

Umsetzung

In Python kann man die Implementierung ein wenig vereinfachen, indem man Iteratoren anstelle von einfachen Listen verwendet. Referenzen auf die (Unter-)Iteratoren werden verwendet, um zu speichern Unterlisten Rücksendeadressen (anstatt sowohl die Listenadresse als auch den Index zu haben). Dies ist kein großer Unterschied, aber ich denke, dass dies besser lesbar ist (und auch ein bisschen schneller):

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

Beachten Sie auch, dass in is_list_like Ich habe isinstance(item, list) , die geändert werden könnte, um mehr Eingabetypen zu verarbeiten, hier wollte ich nur die einfachste Version haben, bei der (iterable) nur eine Liste ist. Aber das könnte man auch machen:

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

Dabei werden Zeichenketten als "einfache Gegenstände" betrachtet und daher flatten_iter([["test", "a"], "b]) wird zurückgegeben ["test", "a", "b"] und nicht ["t", "e", "s", "t", "a", "b"] . Beachten Sie, dass in diesem Fall, iter(item) zweimal für jedes Element aufgerufen wird, tun wir so, als ob es eine Übung für den Leser wäre, dies sauberer zu machen.

Tests und Anmerkungen zu anderen Umsetzungen

Denken Sie schließlich daran, dass Sie eine unendlich verschachtelte Liste nicht ausdrucken können L mit print(L) weil es intern rekursive Aufrufe an __repr__ ( RecursionError: maximum recursion depth exceeded while getting the repr of an object ). Aus demselben Grund sind die Lösungen für flatten mit str schlägt mit der gleichen Fehlermeldung fehl.

Wenn Sie Ihre Lösung testen möchten, können Sie diese Funktion verwenden, um eine einfache verschachtelte Liste zu erstellen:

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

Das ergibt: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]] .

Answer 3

Hier ist eine einfache Funktion, die Listen von beliebiger Tiefe abflacht. Keine Rekursion, um Stapelüberlauf zu vermeiden.

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]

    """
    nested_list = deepcopy(nested_list)

    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

Answer 4

Obwohl eine elegante und sehr pythonische Lösung gewählt wurde, möchte ich meine Lösung nur zur Überprüfung vorstellen:

def flat(l):
    ret = []
    for i in l:
        if isinstance(i, list) or isinstance(i, tuple):
            ret.extend(flat(i))
        else:
            ret.append(i)
    return ret

Bitte sagen Sie uns, wie gut oder schlecht dieser Code ist?

Answer 5

Ich bevorzuge einfache Antworten. Keine Generatoren. Keine Rekursion oder Rekursionsgrenzen. Nur Iteration:

def flatten(TheList):
    listIsNested = True

    while listIsNested:                 #outer loop
        keepChecking = False
        Temp = []

        for element in TheList:         #inner loop
            if isinstance(element,list):
                Temp.extend(element)
                keepChecking = True
            else:
                Temp.append(element)

        listIsNested = keepChecking     #determine if outer loop exits
        TheList = Temp[:]

    return TheList

Dies funktioniert mit zwei Listen: einer inneren for-Schleife und einer äußeren while-Schleife.

Die innere for-Schleife iteriert durch die Liste. Wenn sie ein Listenelement findet, (1) verwendet sie list.extend(), um diesen Teil um eine Verschachtelungsebene zu reduzieren, und (2) setzt keepChecking auf True. keepchecking wird zur Steuerung der äußeren while-Schleife verwendet. Wenn die äußere Schleife auf True gesetzt wird, löst sie die innere Schleife für einen weiteren Durchlauf aus.

Diese Durchläufe werden so lange durchgeführt, bis keine verschachtelten Listen mehr gefunden werden. Wenn schließlich ein Durchlauf erfolgt, bei dem keine weiteren verschachtelten Listen gefunden werden, wird keepChecking nie auf true gesetzt, d. h. listIsNested bleibt false und die äußere while-Schleife wird beendet.

Die reduzierte Liste wird dann zurückgegeben.

Testlauf

flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]