Generator vs List-Comprehension vs while-Schleife...

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Hallo,

eigentlich wollte ich mir heute morgen nur schnell selbst beweisen, dass eine Liste mit datetime.date-Objekten schneller erstellt ist als dieselben Objekte über einen Generator abgerufen sind.
Dazu habe ich eine Funktion, die eine Liste per List-Comprehension übergibt, gegen eine Funktion, die dieselben Objekte als Generator bereitstellt, verglichen.
Das Ergebnis hat mich dann doch überrascht! Wider meiner Erwartung ist der Generator nach verschiedenen Durchläufen im Durchschnitt ca. 2 x schneller!?
Weil ich das so nicht glauben konnte habe ich dann noch eine weitere Funktion, die eine Liste innerhalb einer while-Schleife erstellt und übergibt, in den Vergleich einbezogen.
Dieses Ergebnis entsprach dann doch eher meinen Erwartungen: Die Funktion mit der while-Schleife ist etwas schneller als der Generator, da sie auch nicht für jedes Listenelement extra aufgerufen werden muss.
Bleibt für mich nur die Frage: Weshalb ist ein List-Comprehension dermaßen träge? Nach meinem Verstehen wird hierbei eine Liste erstellt, indem eine Schleife durchlaufen wird. Weshalb benötigt diese Schleife so viel länger als eine while-Schleife?

Hier noch der Code:

Code: Alles auswählen

import time
import datetime

def generator(count):
    date = datetime.date.today()
    while count:
        date += datetime.timedelta(count - (count - 1))
        yield date
        count -= 1

def list_while(count):
    date = datetime.date.today()
    date_list = []
    while count:
        date += datetime.timedelta(count - (count - 1))
        date_list.append(date)
        count -= 1
    return date_list

def list_comp(count):
    return [datetime.date.today() + datetime.timedelta(i) \
        for i in range(count)]

def start(count):
    gen_time_start = time.time()
    gen_list = []
    gen = generator(count)
    for i in range(count):
        gen_list.append(gen.next())
    gen_time_stop = time.time()
    print('%d Daten per Generator         : %f sec.' % (count, 
        gen_time_stop - gen_time_start))

    lw_time_start = time.time()
    lw_list = list_while(count)
    lw_time_stop = time.time()
    print('%d Daten per Schleife          : %f sec.' % (count, 
        lw_time_stop - lw_time_start))

    lc_time_start = time.time()
    lc_list = list_comp(count)
    lc_time_stop = time.time()
    print('%d Daten per List-Comprehension: %f sec.' % (count, 
        lc_time_stop - lc_time_start))
Gibt es Eurer Meinung nach außer dem geringeren Speicherverbrauch noch weitere Gründe, die für einen Generator sprechen?

Hab' mich jetzt mal wieder selbst verunsichert, wäre für Eure Ansichten sehr dankbar!

Gruß
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Barabbas
User
Beiträge: 349
Registriert: Dienstag 4. März 2008, 14:47

Hallo "mutetella",

interessante Beobachtung, finde ich. Ich habe mal aus Interesse die Aufgabe etwas abgeändert und einfach hochzählen lassen. Natürlich sind dafür Generatoren etwas "overdone" und allgemein habe ich damit wohl ein blödes Beispiel erstellt - aber hier sind die LCs wieder deutlich im Vorteil:

Code: Alles auswählen

#!/usr/bin/env python
# coding:utf-8
import time

def generator(max):
    count=0
    while count<=max:
        yield count
        count += 1

def list_while(max):
    count=0
    l = []
    while count<=max:
        l.append(count)
        count += 1
    return count

def list_comp(max):
    return [i for i in range(max)]

def start(count):
    gen_time_start = time.time()
    gen_list = []
    for i in generator(count):
        gen_list.append(i)
    gen_time_stop = time.time()
    print('%d Daten per Generator         : %f sec.' % (count, 
        gen_time_stop - gen_time_start))

    lw_time_start = time.time()
    lw_list = list_while(count)
    lw_time_stop = time.time()
    print('%d Daten per Schleife          : %f sec.' % (count, 
        lw_time_stop - lw_time_start))

    lc_time_start = time.time()
    lc_list = list_comp(count)
    lc_time_stop = time.time()
    print('%d Daten per List-Comprehension: %f sec.' % (count, 
        lc_time_stop - lc_time_start))
        
start(500)
Ich würde also vermuten, dass es etwas mit der Komplexität der LCs zu tun hat? Bei mir sind die LCs ca. 3 mal schneller als der Generator und doppelt so schnell wie "list_while".

Schönen Gruß,

brb

//edit: Es heißt immer, dass das time-Modul recht ungeeignet sei, um Zeit zu stoppen - aber die Ergebnisse sind ja reproduzierbar, so dass ich nicht glaube, dass man an der Tendenz der Ergebnisse zweifeln muss - auch wenn sie vll. ungenau sind.

//edit2: Ich habe einen kleinen Fehler in deinem Skript gefunden. Die Funktion list_comp() muss wie folgt aussehen:

Code: Alles auswählen

def list_comp(count):
    date = datetime.date.today()
    return [date + datetime.timedelta(i) \
        for i in range(count)]
Ansonsten rufst du bei jedem Schleifendurchgang die Funktion today() auf - das machst du in den anderen Funktionen auch nicht.

Wenn man das korrigiert, ist die Reihenfolge wie in meinem Beispiel oben: LCs schneller als Schleife schneller als Generator.
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Barabbas hat geschrieben:Bei mir sind die LCs ca. 3 mal schneller als der Generator und doppelt so schnell wie "list_while".
Das Ergebnis mit Deinem geänderten Test fällt bei mir noch bei weitem auffälliger aus, sind LCs fast 10 mal schneller als der Generator... :?
Barabbas hat geschrieben:Ich würde also vermuten, dass es etwas mit der Komplexität der LCs zu tun hat?
Nur, warum? Schleife ist doch Schleife, oder? Wo liegt der Unterschied zwischen

Code: Alles auswählen

a = [i for i in range(100)]
und

Code: Alles auswählen

a = []
for i in range(100):
    a.append(i)
Sehr spannend... wie ich meine... :)

Gruß
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Barabbas
User
Beiträge: 349
Registriert: Dienstag 4. März 2008, 14:47

Hallo nochmal,
mutetella hat geschrieben:
Barabbas hat geschrieben:Ich würde also vermuten, dass es etwas mit der Komplexität der LCs zu tun hat?
Nur, warum? Schleife ist doch Schleife, oder? Wo liegt der Unterschied zwischen
Ich glaube, du hast meinen zweiten Edit übersehen:
Barabbas hat geschrieben: //edit2: Ich habe einen kleinen Fehler in deinem Skript gefunden. Die Funktion list_comp() muss wie folgt aussehen:

Code: Alles auswählen

def list_comp(count):
    date = datetime.date.today()
    return [date + datetime.timedelta(i) \
        for i in range(count)]
Ansonsten rufst du bei jedem Schleifendurchgang die Funktion today() auf - das machst du in den anderen Funktionen auch nicht.

Wenn man das korrigiert, ist die Reihenfolge wie in meinem Beispiel oben: LCs schneller als Schleife schneller als Generator.
Aber warum genau LCs soviel schneller sind, würde mich natürlich auch interessieren.

Besten Gruß,

brb
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Barabbas hat geschrieben:Ich habe einen kleinen Fehler in deinem Skript gefunden.
Ok... Vielen Dank! Ich Hirni!!! Der :twisted: lag mal wieder im Detail!

Gruß
mutetella


P.S.: Dennoch: Was, außer dem geringeren Speicherverbrauch, spricht Deiner Ansicht nach noch für Generatoren?
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Barabbas
User
Beiträge: 349
Registriert: Dienstag 4. März 2008, 14:47

Dazu habe ich hier etwas interessantes gefunden:
List comprehensions perform better here because you don’t need to load the append attribute off of the list (loop program, bytecode 28) and call it as a function (loop program, bytecode 38). Instead, in a comprehension, a specialized LIST_APPEND bytecode is generated for a fast append onto the result list (comprehension program, bytecode 33).
Anscheinend wird bei LCs also gezielt Overhead eingespart, indem die Liste mit einem speziellen "Befehl" ("bytecode") befüllt wird. Das geht aber so tief in die Interna, dass ich davon wirklich keinen Schimmer mehr habe. Aber die Profis werden uns da sicher einen Wink geben ;).
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Man kann sich ja immer den Bytecode ansehen um zu schauen was eigentlich gemacht wird und abschätzen wie groß der Overhead ist. Und ja, für LCs braucht man keinen Lookup des ``append`` Attributes.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Nun ja, soweit ich das verstehe, findet bei einem LC pro Listenelement kein extra Aufruf der append()-Methode statt. Und die Zeit, die diese append()-Aufrufe benötigen, spart man sich hier eben.

Vielen Dank für Dein "Stöbern". Sehr interessant!

Gruß
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Und wenn man das Programm so umschreibt, dass offensichtlich wird, was da passiert, wird's noch schneller (~10 mal so schnell wie list_while2():

Code: Alles auswählen

def list_for2(count):
    date = datetime.date.today()
    date_list = []
    t = datetime.timedelta(1)
    append = date_list.append
    for i in xrange(1, count):
        date += t
        append(date)
        #count -= 1
    return date_list
/besserwisserei
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

@b.esser-wisser
Wow....!!! Das haut mich um!!! Wegen solchen Dingen bin ich so fasziniert vom Programmieren!!!

Danke für den Hinweis! Bevor ich irgendwas anderes mache werde ich mein Programm auf solche Optimierungen "durchforsten"!

Voll coooool!!! :D :D

Gruß
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

mutetella hat geschrieben:Danke für den Hinweis! Bevor ich irgendwas anderes mache werde ich mein Programm auf solche Optimierungen "durchforsten"!
Lieber nicht. Wie heißt es so schön „Premature optimization is the root of all evil“. Will sagen: So lange du keine ernsthaften Performanceprobleme hast mach deinen Code nicht durch solche Micro-Optimierungen unleserlich und verschwende deine Zeit nicht damit.
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

Darii hat geschrieben:So lange du keine ernsthaften Performanceprobleme hast mach deinen Code nicht durch solche Micro-Optimierungen unleserlich und verschwende deine Zeit nicht damit.
Ich möchte Dir gerne Recht geben, hab' ich doch schon viel kostbare Zeit durch kaum wahrnehmbare Tuningarbeiten vergeudet... :(
Allerdings schaut das in diesem Fall anderst aus:

Bisher:

Code: Alles auswählen

100 Daten per Generator: 0.000855 sec.
100 Daten per Schleife: 0.000708 sec.
100 Daten per List-Comprehension: 0.000649 sec.
Nach b.esser-wisser Tipp:

Code: Alles auswählen

100 Daten per Generator: 0.000275 sec.
100 Daten per Schleife: 0.000155 sec.
100 Daten per List-Comprehension: 0.000107 sec.
Für sich allein betrachtet fällt das sicher noch in den kaum wahrnehmbaren Bereich. Aber wenn ich in meinem Kalenderprogramm schnell mal ein paar Monate weiterklicke, dann fällt das sicher ins Gewicht.

Ich hab' jetzt auch nicht vor, alles über den Haufen zu werfen... Aber sowas

Code: Alles auswählen

date = datetime.date.today()
date_list = []
t = datetime.timedelta(1)
append = date_list.append
for i in xrange(100):
    date += t
    append(date)
gegenüber sowas

Code: Alles auswählen

date = datetime.date.today()
date_list = []
for i in xrange(100):
    date += datetime.date.timedelta(1)
    date_list.append(date)
bringt defenitiv etwas...

Gruß
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
Dav1d
User
Beiträge: 1437
Registriert: Donnerstag 30. Juli 2009, 12:03
Kontaktdaten:

zu deinem letzten Beispiel, sowas kann und sollte man beim Programmieren schon erkennen und vermeiden und nicht erst wenn man explizit danach sucht
the more they change the more they stay the same
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Das einzige, was du da 'optimieren' solltest ist das 'datetime.timedelta(CONSTANT)' - du brauchst da nicht jedes mal ein neues, aber gleiches Objekt.
Ansonsten geht Lesbarkeit immer vor ("readability counts" und "beautiful is better than ugly" aus dem Python-Zen). Irgendwo hatte ich auch noch gelesen "If it's ugly, it's probably wrong" (in Python - in C++, php etc. mag das anders aussehen ;) ).

hth, Jörg
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

mutetella hat geschrieben:Für sich allein betrachtet fällt das sicher noch in den kaum wahrnehmbaren Bereich. Aber wenn ich in meinem Kalenderprogramm schnell mal ein paar Monate weiterklicke, dann fällt das sicher ins Gewicht.
Deswegen schrieb ich auch „So lange du keine ernsthaften Performanceprobleme hast“.
Antworten