Python: Wie macht man aus einer Liste von Listen eine flache Liste?
Aus [[1, 2], [3, 4]] ein [1, 2, 3, 4] zu machen hat eine naheliegende
Antwort, eine verlockende die langsam wird, und eine rekursive die bei Strings
abstürzt, wenn man sie so schreibt wie es sich anbietet.
Die Antwort
flach = [x for teil in verschachtelt for x in teil]
nested = [[1, 2], [3, 4], [5, 6]]
[x for sub in nested for x in sub] : [1, 2, 3, 4, 5, 6]
Die Reihenfolge, die beim ersten Mal niemand trifft
Die for-Teile liest man von links nach rechts, äußerster zuerst — also
genau in der Reihenfolge, in der man sie als Anweisungen schreiben würde:
ergebnis = []
for teil in verschachtelt: # aeusserer zuerst
for x in teil: # innerer danach
ergebnis.append(x)
Verwirrend ist das, weil der Ausdruck ganz vorne (x) das Innerste ist.
Dreht man es um, wird der Grund offensichtlich:
[x for x in sub for sub in nested] -> NameError: name 'sub' is not defined
teil gibt es noch gar nicht, wenn der erste Teil ausgeführt wird. Es gibt nur
eine Reihenfolge, die funktionieren kann.
Die verzögerte Variante
from itertools import chain
flach = list(chain.from_iterable(verschachtelt))
list(chain.from_iterable(nested)) : [1, 2, 3, 4, 5, 6]
it is lazy : chain
Zu
chain.from_iterable
greife ich, wenn das Ergebnis direkt weiterverarbeitet wird, denn die flache
Liste entsteht dabei gar nicht erst:
next() twice : 1, 2
sum without materialising : 21
Es gibt außerdem chain(*verschachtelt). Das tut dasselbe, entpackt aber
vorher die gesamte äußere Liste in Argumente — verliert also die Verzögerung
und funktioniert nicht bei einer unendlichen äußeren Folge.
Die verlockende, die langsam wird
sum(verschachtelt, [])
Es funktioniert, und es ist quadratisch. Bei jedem Schritt entsteht eine neue Liste mit allem bisher Gesehenen, das Zusammenfügen von n Teillisten kopiert also ungefähr n²/2 Elemente.
Gemessen mit 1000 Teillisten:
sum(data, []) : 0.0127 s
comprehension : 0.0005 s
chain.from_iterable : 0.0004 s
sum() is 24x slower than the comprehension
Und jetzt mit der vierfachen Eingabe:
4000 sublists (4x the input), 5 runs each:
sum(data, []) : 0.0459 s
comprehension : 0.0005 s
ratio : 87x
Die Comprehension hat sich kaum bewegt. Der Abstand ist von 24x auf 87x gewachsen. Quadratisches Verhalten sieht man bei den kleinen Eingaben, mit denen man testet, nicht — und bei den echten übersieht man es nicht mehr.
CPython findet das deutlich genug, um die String-Variante rundheraus abzulehnen:
sum(['ab','cd'], '') -> TypeError: sum() can't sum strings [use ''.join(seq) instead]
Die Fehlermeldung nennt gleich die Lösung, was angenehm ist. Für Listen gibt es keine entsprechende Sperre, dieser Fall läuft einfach langsam.
Nur eine Ebene
Alle drei Formen oben machen genau eine Ebene flach:
deep = [1, [2, [3, [4]]]]
comprehension -> TypeError: 'int' object is not iterable
Die Ganzzahl 1 ist nicht iterierbar, die innere Schleife kann damit nichts
anfangen. Für beliebige Tiefe brauchst du Rekursion:
def flach_machen(element):
for teil in element:
if isinstance(teil, (list, tuple)):
yield from flach_machen(teil)
else:
yield teil
recursive flatten : [1, 2, 3, 4]
Die Variante, die abstürzt
Hier dieselbe Funktion mit einer scheinbar allgemeineren Prüfung — alles Iterierbare wird flach gemacht:
if hasattr(teil, "__iter__"):
yield from naiv_flach_machen(teil)
Auf ["ab", ["cd"]]:
checking __iter__ -> RecursionError: maximum recursion depth exceeded
Ein String ist iterierbar, "ab" wird also in "a" und "b" zerlegt. Und
"a" ist ebenfalls iterierbar — ein String aus einem Zeichen liefert beim
Iterieren genau denselben String aus einem Zeichen. Die Rekursion erreicht nie
einen Abbruchfall.
Stattdessen isinstance(teil, (list, tuple)) zu prüfen ist keine
Geschmacksfrage. Es ist der Unterschied zwischen “funktioniert” und einem
Traceback:
checking isinstance(x, (list, tuple)) : ['ab', 'cd']
Die allgemeine Lehre daraus: “Ist es iterierbar” ist in Python fast nie die
Frage, die man meint, weil str, bytes und dict allesamt mit Ja antworten
— nur nicht so, wie man es gemeint hat.
Zwei Abwandlungen
Ungleich lange und leere Teillisten brauchen keine Sonderbehandlung:
[[1], [], [2, 3, 4], []] -> [1, 2, 3, 4]
Und dieselbe Form macht ein Dictionary aus Listen flach, wahlweise zu den Werten oder zu Paaren:
values : [1, 2, 3]
pairs : [('a', 1), ('a', 2), ('b', 3)]
Hinweis zu Netcup (Werbung)
Der deutsche Hoster Netcup bietet unter anderem günstige und zugleich leistungsstarke Webhosting Pakete, KVM-basierte Root Server und dezidierte Server an. Mit unseren Gutscheincodes kannst du noch mehr Geld sparen (6€ bei deiner ersten Bestellung, 30% Rabatt auf alle KVM-basierten Root Server, ...).