Quadratische Laufzeit oder?
Guten Morgen, In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item Normalerweise wird nur die Iterator-Funktion gebraucht, also das hier: obj = Foo(range(0,100)) for item in obj: mach_was_mit_item(item) Aber manchmal will man die Komplette Liste haben, also das hier: obj = list(Foo(range(0,100))) Beim darüber nachdenken, kam mir der Gedanke das der Algorithmus dadurch eine quadratische Laufzeit also O(n^2) bekommt. Den es wird ja in next() von Foo "for for item in self.iter_" durchlaufen und durch das "list(Foo(range(0,100)))", startet der Python-Interpreter doch auch eine interne for Schleife, oder bin ich da auf den Holzweg? Auf irgendeiner Art, Weise muss Python doch jedes Element in der Liste einmal erreichen. Im Beispiel ist es hier range() im wirklichen "Leben" handelt es sich dabei aber um eine Byte-Struktur. Mit freundlichen Grüßen Albert Hermeling
Nö, da liegst du falsch. Wobei dein Beispiel irgendwie sehr unnötig verschachtelt ist und daher schwer zu entwirren, wenn man deinen eigentlich use case nicht kennt. Kannst du etwas genauer beschreiben, was du überhaupt vor hast? So ganz grob vorab: - Du übergibst __init__ einen Iterator. Über den kannst du nur einmal iterieren. Die Klasse suggeriert aber etwas anderes. Du kannst ja mal versuchen, "for item in obj" ein zweites mal aufzurufen. - __iter__ soll einen Interator zurückliefern. Das passiert in deinem Fall, aber dir ist scheinbar nicht klar warum. - next() liefert nicht das nächste Element, sondern - dank yield - einen Iterator, der über den ursprünglichen Iterator iteriert. Alles in allem ist dein reduziertes Beispiel eine Klasse, die das Iterieren über einen Iterator kapselt und das nicht so ganz sauber. Für mich ergibt das wenig Sinn. Für weitere Hilfe müßtest du uns also, wie schon gesagt, mehr Details dazu zukommen lassen, was du überhaupt erreichen willst. Grüße, Achim Am 28.09.2014 um 10:44 schrieb Albert Hermeling:
Guten Morgen,
In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine
class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item
Normalerweise wird nur die Iterator-Funktion gebraucht, also das hier:
obj = Foo(range(0,100)) for item in obj: mach_was_mit_item(item)
Aber manchmal will man die Komplette Liste haben, also das hier: obj = list(Foo(range(0,100)))
Beim darüber nachdenken, kam mir der Gedanke das der Algorithmus dadurch eine quadratische Laufzeit also O(n^2) bekommt. Den es wird ja in next() von Foo "for for item in self.iter_" durchlaufen und durch das "list(Foo(range(0,100)))", startet der Python-Interpreter doch auch eine interne for Schleife, oder bin ich da auf den Holzweg? Auf irgendeiner Art, Weise muss Python doch jedes Element in der Liste einmal erreichen. Im Beispiel ist es hier range() im wirklichen "Leben" handelt es sich dabei aber um eine Byte-Struktur.
Mit freundlichen Grüßen
Albert Hermeling
_______________________________________________ python-de maillist - python-de@python.org https://mail.python.org/mailman/listinfo/python-de
Albert Hermeling schrieb am 28.09.2014 um 10:44:
In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine
class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item
Ok, wahrscheinlich nur ein Beispiel, aber das oben ist nicht wirklich mehr als iter(iter_) (eigentlich sogar weniger.) Wenn dein Code komplizierter ist (wovon ich mal ausgehe), dann reicht trotzdem meistens eine einfache Generatorfunktion wie def mach_was_mit_bytes(daten): for zeichen in daten: ... # tu Dinge mit zeichen yield verarbeitetes_zeichen statt einer Klasse, die nur sinnlos diese Funktion nochmal als Method verpackt. Schau dir auch mal Generatorausdrücke an, englisch "generator expressions". Damit kannst du das Generatoren- und insbesondere Klassenschreiben oft vermeiden.
Normalerweise wird nur die Iterator-Funktion gebraucht, also das hier:
obj = Foo(range(0,100)) for item in obj: mach_was_mit_item(item)
Aber manchmal will man die Komplette Liste haben, also das hier: obj = list(Foo(range(0,100)))
Beim darüber nachdenken, kam mir der Gedanke das der Algorithmus dadurch eine quadratische Laufzeit also O(n^2) bekommt. Den es wird ja in next() von Foo "for for item in self.iter_" durchlaufen und durch das "list(Foo(range(0,100)))", startet der Python-Interpreter doch auch eine interne for Schleife, oder bin ich da auf den Holzweg?
Ja, eindeutig Holzweg. Pro Schritt der Listenerstellung wird nur ein Schritt des Iterators ausgeführt. Also O(n). Stefan
Am 28.09.2014 um 12:59 schrieb Stefan Behnel: Hallo, stimmt ich bin eindeutig auf den Holzweg gekommen. Hätte ich auch von alleine drauf kommen können, das es O(n) ist, aber manchmal... ja ja. Es wahr wohl noch zu früh am Morgen ;-). Was das Thema Klasse berieft macht es in der konkreten Anwendung schon Sinn. Die Klasse besteht nicht nur aus einer Iterrator Methode, sondern beinhaltet noch andere Methoden. Sie soll sich später mal so ähnlich wie eine Python Liste "anfühlen" und da man über eine Liste auch mehr als ein mal iterieren kann, ist es schon Sinnvoll das ein Iterator zurückgegeben wird. Wenn über sie in eine for Schleife iteriert wird. Das hier war nicht ganz Korrekt: obj = list(Foo(range(0,100))) weil ich nicht eine Liste hinschreiben wollte, habe ich range() genommen (Ich habe dabei wohl an das range von Py 2.7 gedacht). Eigentlich muss es in etwa so aussehen: "obj = list(Foo(b"abcedefg")) wobei mit b"" wirklich alle Bytes, von 0 - 255, gemeint sind. Ich habe hier im Beispiel ASCCI genommen damit es leichter lesbar ist.
Albert Hermeling schrieb am 28.09.2014 um 10:44:
In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine
class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item Ok, wahrscheinlich nur ein Beispiel, aber das oben ist nicht wirklich mehr als
iter(iter_)
(eigentlich sogar weniger.)
Wenn dein Code komplizierter ist (wovon ich mal ausgehe), dann reicht trotzdem meistens eine einfache Generatorfunktion wie
def mach_was_mit_bytes(daten): for zeichen in daten: ... # tu Dinge mit zeichen yield verarbeitetes_zeichen
statt einer Klasse, die nur sinnlos diese Funktion nochmal als Method verpackt.
Schau dir auch mal Generatorausdrücke an, englisch "generator expressions". Damit kannst du das Generatoren- und insbesondere Klassenschreiben oft vermeiden.
Normalerweise wird nur die Iterator-Funktion gebraucht, also das hier:
obj = Foo(range(0,100)) for item in obj: mach_was_mit_item(item)
Aber manchmal will man die Komplette Liste haben, also das hier: obj = list(Foo(range(0,100)))
Beim darüber nachdenken, kam mir der Gedanke das der Algorithmus dadurch eine quadratische Laufzeit also O(n^2) bekommt. Den es wird ja in next() von Foo "for for item in self.iter_" durchlaufen und durch das "list(Foo(range(0,100)))", startet der Python-Interpreter doch auch eine interne for Schleife, oder bin ich da auf den Holzweg? Ja, eindeutig Holzweg. Pro Schritt der Listenerstellung wird nur ein Schritt des Iterators ausgeführt. Also O(n).
Stefan
_______________________________________________ python-de maillist - python-de@python.org https://mail.python.org/mailman/listinfo/python-de Albert
Hallo Albert, On 2014-09-28 10:44, Albert Hermeling wrote:
In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine
class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item
Ich denke, der Code sollte nicht so sein, aber er funktioniert gewissermaßen trotzdem (_falls_ er das macht, was du willst ;-) ). `__iter__` muss einen Iterator zurückgeben. `__iter__` ruft `next`, das dank des enthaltenen `yield` tatsächlich einen Iterator zurückgibt. Über den wird dann iteriert. Du könntest die gleiche Funktionalität so ausdrücken: class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): for item in self.iter_: yield item Hier ist meines Erachtens leichter zu sehen, was Achim meinte. Wenn `self.iter_` tatsächlich ein Iterator ist, wird nur der erste Aufruf von `__iter__` Elemente liefern. Danach ist der Iterator `self.iter_` erschöpft; `for item in self.iter_` wird also nichts mehr zu "yielden" haben.
Normalerweise wird nur die Iterator-Funktion gebraucht, also das hier:
obj = Foo(range(0,100))
Wenn du die Klasse allerdings so benutzt, ist `self.iter_` eine Liste, und über diese kannst du mit `for item in self.iter_` mehrfach iterieren und Elemente bekommen. Probier deinen Code mal mit `xrange` statt `range` aus und führe diese Schleife von dir mehrfach aus:
for item in obj: mach_was_mit_item(item)
Aber manchmal will man die Komplette Liste haben, also das hier: obj = list(Foo(range(0,100)))
Mit deinem jetzigen Code weist du `obj` effektiv die Liste `range(0, 100)` zu. Wenn du mit `n` also die Anzahl der Elemente in der Liste (hier 100) meinst, läuft das auf O(n) hinaus. Viele Grüße Stefan
Hallo Albert, On 2014-09-28 10:44, Albert Hermeling wrote:
In einen kleinen Programm gibt es eine Klasse die einen Iterator bereitstellt. Hier ein Beispiel was ich meine
class Foo(): def __init__(self,iter_): self.iter_ = iter_ def __iter__(self,): return self.next() def next(self,): for item in self.iter_: yield item
ich weiß nicht, was du _eigentlich_ vorhattest ;-) , aber vielleicht hilft dir das `itertools`-Modul bei der Lösung: https://docs.python.org/2.7/library/itertools.html Unabhängig davon empfehle ich dir, mit deinem (und gegebenenfalls anderem) Code zu experimentieren, bis klar ist, wie das Iterator-Protokoll funktioniert. Siehe https://docs.python.org/2/library/stdtypes.html#iterator-types Viele Grüße Stefan
participants (4)
-
Achim Domma -
Albert Hermeling -
Stefan Behnel -
Stefan Schwarzer