tief verschachtelte Liste "entschachteln"

[Nocta]

Hey, ich habe aus Interesse mal einen rekursiven Algorithmus entwickelt, um eine tief verschachtelte Liste zu "entschachteln".

Code: Alles auswählen

def tiefe(iterable):
    res = []
    for element in iterable:
        if hasattr(element, "__iter__"):
            res += tiefe(element)
        else:
            res.append(element)
    return res

Als Test-Liste habe ich das hier genommen:

Code: Alles auswählen

a = [5, 2, 3, [4, 6, 1, [4, 5, [3, 2, [3, [5, 3, 2, 3], [4, 32], 4, [2, 3, [1, 2], 5, [5, 7, [3, 8, 2, [9, 1, 2, 6, 99, 4]]]]]
, 6], 3, [54, 2, 3]]], [99, 1, [3, 4]], [2], 98]

Das schien mir schon relativ effizient zu sein, aber dann hab ich mir gedacht, dass Listen ja ziemlich ineffizient sind und habe versucht, das über Generatoren zu lösen:

Code: Alles auswählen

def tiefe2(iterable):
    for element in iterable:
        if hasattr(element, "__iter__"):
            for i in tiefe2(element):
                    yield i
        else:
            yield element

Das war erwartungsgemäß schneller:
Bei 1.000.000 Durchläufen braucht tiefe() ca. 50 Sekunden und tiefe2() ca. 0.35 Sekunden
Ein "kleiner" Unterschied von ca. 1:143
Aber beim Aufsummieren mittels sum() gewinnt die Liste wieder deutlich (mehrere Sekunden).
Mit einer dritten Implementation speziell zum Addieren aller Werte der Liste kann ich noch mal einige Sekunden rausschlagen:

Code: Alles auswählen

def deep_sum(iterable):
    res = 0
    for element in iterable:
        if hasattr(element, "__iter__"):
            res += deep_sum(element)
        else:
            res += element
    return res

Naja meine Fragen:
Wie könnte man das am effizientesten lösen? Gibt es bessere Algorithmen oder besser geeignete Datenstrukturen?
Mit dem Generator kann ich die Liste zwar sehr schnell entschachteln, aber im Endeffekt verliere ich Zeit, da die Datenstruktur wohl nicht so schnell arbeitet wie list.

Die Rekursion sollte ja eigentlich nicht so viel ausmachen oder? Bei dieser Liste zum Beispiel sind es nur 16 Selbstaufrufe und nicht gleich 10000 oder so
Aber vielleicht geht es irgendwie effizienter, wenn man Ebene für ebene durchgeht, anstatt immer "hoch und runter". Aber darüber muss ich erst noch mal nachdenken ...

PS: Was ist denn der übliche Weg dafür? Gibt es schon etwas fertiges in Python?
Danke schon mal für eure Antworten

[DasIch]

__iter__ muss nicht zwangsläufig vorhanden sein um über ein Objekt zu iterieren. Auf __iter__ zu prüfen um Strings auszusortieren mag zwar auf CPython funktionieren aber auf anderen Implementation klappt dass nicht unbedingt.

[Pekh]

Das ist halt das Grundproblem: Eine Datenstruktur ist nie für alle Problemstellungen optimal. Die Kunst ist es, für die gegebene Problemstellung die günstigste Datenstruktur auszuwählen.

[derdon]

Theoretisch lässt sich jedes Problem sowohl mit als auch ohne Rekursion lösen. Es gibt Sprachen wie Lisp-Dialekte, die nur Rekursion und keine iterativen Ansätze kennen.

Dein Problem lässt sich mittels rekursiven Funktionen am elegantesten lösen, da "readability counts" gilt. Du bist übrigens nicht der erste mit diesem Problem: suche in diesem Forum und im Wiki nach "Listen glätten" oder bei Google nach "+python flatten list".

[Nocta]

__iter__ muss nicht zwangsläufig vorhanden sein um über ein Objekt zu iterieren.

Ich dachte das wäre der Sinn von __iter__. Was für Kriterien für Iterables gibt es denn noch?

Auf __iter__ zu prüfen um Strings auszusortieren mag zwar auf CPython funktionieren aber auf anderen Implementation klappt dass nicht unbedingt.

Hm Strings schließ ich damit gar nicht aus (hat übrigens __iter__).
Es geht nur darum, ob das aktuelle Element noch mal geglättet (besseres Wort, danke derdon).
Allerdings kommt es bei Strings logischerweise zu einer Endlosschleife, also insofern danke für den Hinweis


@Pekh: Ja, da magst du recht haben Aber in den meisten Fällen geht es ja denke ich darum, dass man die Datenstruktur schnell abarbeiten kann (sum() arbeitet die doch nur ab, oder?)
Ich wüsste jedenfalls nicht, was sonst der Sinn einer geglätteten Liste sein sollte. Aber definieren wir einfach als Problemstellung: Die Datenstruktur muss schnell durchlaufbar und schnell erstellbar sein.

@derdon: Mir ist klar, dass man jedes Problem auch iterativ lösen kann, ich habe eher indirekt gefragt, ob es einen großen Unterschied zur iterativen Lösung ausmacht
Na ja, ich werd dann mal wohl ein wenig googlen.

[Dauerbaustelle]

`isiterable`-Vorschlag (vom Code eines Projektes entnommen):

Code: Alles auswählen

def isiterable(iterable, include_strings=False, include_dicts=True):
    if isinstance(iterable, basestring):
        return include_strings
    if isinstance(iterable, dict):
        return include_dicts
    try:
        iter(iterable)
        return True
    except TypeError:
        return False

`iter(...)` ist schneller als `hasattr(..., '__iter__')` und greift in allen Fällen, in denen das Objekt iterable ist, also auch solche, die kein `__iter__` definiert haben.

[Dauerbaustelle]

Was für Kriterien für Iterables gibt es denn noch?

`__len__` + `__getitem__`.

[Nocta]

Danke für den Vorschlag, aber laut timeit dauert das Ausführen mit isiterable() ca. doppelt so lange.

Ist zwar trotzdem besser als hasattr(), aber von der Performance her nicht so

[BlackJack]

@Dauerbaustelle: `__len__()` muss nicht vorhanden sein `__getitem__()` mit entsprechender Implementierung reicht. Womit wir zu dem Code von `isiterable()` kommen: Der ist nicht 100% denn `iter()` reicht nicht. Das macht im Grunde nämlich nicht wirklich etwas. Es kann durchaus Objekte geben, die `__getitem__()` haben, also klappt der `iter()`-Aufruf, aber beim ersten Versucht wirklich ein Element zu holen kann es dann immer noch krachen.

[lunar]

"isinstance(foo, collections.Iterable)" ... dafür gibt es ABCs doch.

[BlackJack]

Gibt's bei mir noch nicht (Python 2.5) und es wird sicher noch nicht flächendeckend von allen "iterables" verwendet, also ist der Test nicht besonders zuverlässig.

[Nocta]

Und als ich es getestet habe, war es noch langsamer als Dauerbaustelles Funktion.

[Panke]

Hast Du mal getestet, was es Dir in puncto Geschwindigkeit bringt, die Rekursion aufzugeben?