[Python-de] Quadratische Laufzeit oder?

[Albert Hermeling]

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 at python.org
> https://mail.python.org/mailman/listinfo/python-de
Albert