Was ist schneller: Schleife gegen Einzeiler

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.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Was ist schneller: Schleife gegen Einzeiler

Beitragvon droptix » Samstag 30. Dezember 2006, 10:33

Beispiel:

Code: Alles auswählen

myList = [
    ("foo", "bar"),
    ("blah", "blubb")
]


Welche Version von den folgenden arbeitet eigentlich schneller?

Code: Alles auswählen

def inList(x, l):
    r = []
    for i in l:
        if i == x:
            r.append(i)
    return r

print inList(("foo", "bar"), myList)


oder

Code: Alles auswählen

def inList(x, l):
    return [i for i in l if i == x]

print inList(("foo", "bar"), myList)


Worin liegen die Unterschiede?
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Beitragvon Y0Gi » Samstag 30. Dezember 2006, 11:30

Als weitere Alternative werfe ich mal filter() ins Rennen.

Geschwindigkeits-(aber keine Speicherverbrauchs-)vergleiche kannst du über das timeit-Modul durchführen.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

filter()-Beispiel bitte

Beitragvon droptix » Samstag 30. Dezember 2006, 15:21

Y0Gi hat geschrieben:Als weitere Alternative werfe ich mal filter() ins Rennen.


Hättest du dafür mal ein äquivalentes Beispiel zu meinem oben?
BlackJack

Beitragvon BlackJack » Samstag 30. Dezember 2006, 16:10

Code: Alles auswählen

def in_list(x, l):
    return filter(lambda i: x == i, l)
Flano
User
Beiträge: 43
Registriert: Sonntag 5. September 2004, 14:13

Beitragvon Flano » Samstag 30. Dezember 2006, 18:41

Ich denke der Einzeiler ist schneller, da die Ergebnisse aus der
"for Schleife" nicht erst in eine Liste geschrieben werden.
Besser lesbar(für mich) ist allerdings die "Schleife" und das
ist für mich immer das wichtigere Kriterium. Sehr wahrscheinlich
wirst du beim ausführen von:

Code: Alles auswählen

print inList(('foo', 'bar'), myList) *10000000

bei den drei Versionen, mit der Stoppuhr, keinen Unterschied
feststellen.

Gruß Flano
BlackJack

Beitragvon BlackJack » Samstag 30. Dezember 2006, 19:01

Ich finde die List-Comprehension am einfachsten zu erfassen. In der Schleife muss man sich komplexeren Code anschauen und hat einen Namen mehr.
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Samstag 30. Dezember 2006, 19:49

Die List Comprehension ist intern genau gleich implementiert. Sie spuckt sogar den Bezeichner in den Namensraum aus, wie das auch die for-Schleife tut :D
TUFKAB – the user formerly known as blackbird
Flano
User
Beiträge: 43
Registriert: Sonntag 5. September 2004, 14:13

Beitragvon Flano » Samstag 30. Dezember 2006, 20:52

Sorry,

Code: Alles auswählen

print in_list(('foo', 'bar'), myList) *1000000

ist natürlich Blödsinn als Geschwindigkeitsnachweis, da das Ergebnis
der Funktion multipliziert wird und nicht zig mal die Funktion
ausgeführt wird.
Stattdessen:

Code: Alles auswählen

for a in range(1000000):
    print in_list(('foo', 'bar'), myList)

Ich hoffe jetzt macht es Sinn.

Gruß Flano
BlackJack

Beitragvon BlackJack » Samstag 30. Dezember 2006, 22:01

Die Liste ist ein wenig zu kurz. Der Code drumherum dürfte mehr Zeit brauchen als das was Du messen möchtest.

Die List-Comprehension dürfte etwas schneller sein als die Schleife, weil dort die `append()`-Methode jedesmal neu vom Objekt abgefragt werden muss, wo bei der List-Comprehension klar ist, welche Methode bzw. welcher Bytecode ausgeführt werden muss.

Ganz gut am Bytecode zu sehen:

Code: Alles auswählen

In [20]: import dis

In [21]: def a(x, l):
   ....:     r = []
   ....:     for i in l:
   ....:         if i == x:
   ....:             r.append(i)
   ....:     return r
   ....:

In [22]: def b(x, l):
   ....:     return [i for i in l if i == x]
   ....:

In [23]: dis.dis(a)
  2           0 BUILD_LIST               0
              3 STORE_FAST               3 (r)

  3           6 SETUP_LOOP              44 (to 53)
              9 LOAD_FAST                1 (l)
             12 GET_ITER
        >>   13 FOR_ITER                36 (to 52)
             16 STORE_FAST               2 (i)

  4          19 LOAD_FAST                2 (i)
             22 LOAD_FAST                0 (x)
             25 COMPARE_OP               2 (==)
             28 JUMP_IF_FALSE           17 (to 48)
             31 POP_TOP

  5          32 LOAD_FAST                3 (r)
             35 LOAD_ATTR                4 (append)
             38 LOAD_FAST                2 (i)
             41 CALL_FUNCTION            1
             44 POP_TOP
             45 JUMP_ABSOLUTE           13
        >>   48 POP_TOP
             49 JUMP_ABSOLUTE           13
        >>   52 POP_BLOCK

  6     >>   53 LOAD_FAST                3 (r)
             56 RETURN_VALUE

In [24]: dis.dis(b)
  2           0 BUILD_LIST               0
              3 DUP_TOP
              4 STORE_FAST               2 (_[1])
              7 LOAD_FAST                1 (l)
             10 GET_ITER
        >>   11 FOR_ITER                30 (to 44)
             14 STORE_FAST               3 (i)
             17 LOAD_FAST                3 (i)
             20 LOAD_FAST                0 (x)
             23 COMPARE_OP               2 (==)
             26 JUMP_IF_FALSE           11 (to 40)
             29 POP_TOP
             30 LOAD_FAST                2 (_[1])
             33 LOAD_FAST                3 (i)
             36 LIST_APPEND
             37 JUMP_ABSOLUTE           11
        >>   40 POP_TOP
             41 JUMP_ABSOLUTE           11
        >>   44 DELETE_FAST              2 (_[1])
             47 RETURN_VALUE
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

brauche es für eine große Liste

Beitragvon droptix » Sonntag 31. Dezember 2006, 15:52

Also mir geht es darum, einen Wert in einer sehr großen Liste zu ermitteln, die während des Programms sogar noch anwächst. Also eignet sich hier die List-Comprehension am besten. Damit ermittelt man zwar nicht direkt den gesuchten Wert, aber anhand der Länge der Liste (Null = leer = Wert nicht enthalten bzw. größer Null heißt "gefunden") dürfte sich die Frage klären lassen:

Code: Alles auswählen

myList = [
    ("foo", "bar"),
    ("blah", "blubb")
]

def inList(x, l):
    if len([i for i in l if i == x]) == 0:
        return False
    else:
        return True

print inList(("foo", "bar"), myList)


Danke!
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Beitragvon Y0Gi » Sonntag 31. Dezember 2006, 16:33

Müsste nicht anstelle der List Comprehension eine Generator Expression (außen runde statt eckige Klammern, verwendet Iterator) noch schneller oder zumindest bei großen Datenmengen speicherfreundlicher sein?
BlackJack

Re: brauche es für eine große Liste

Beitragvon BlackJack » Sonntag 31. Dezember 2006, 16:37

droptix hat geschrieben:Also mir geht es darum, einen Wert in einer sehr großen Liste zu ermitteln, die während des Programms sogar noch anwächst. Also eignet sich hier die List-Comprehension am besten. Damit ermittelt man zwar nicht direkt den gesuchten Wert, aber anhand der Länge der Liste (Null = leer = Wert nicht enthalten bzw. größer Null heißt "gefunden") dürfte sich die Frage klären lassen:


Das ist aber umständlich und unnötig langsam. Wenn Du nur wissen willst, ob ein Element mindestens einmal enthalten ist kannst Du den ``in``-Operator benutzen: ``if x in liste:``. Da wird a) keine zusätzliche Liste angelegt und b) bricht die Suche beim ersten Treffer ab, es muss also nicht unnötigerweise der Rest der Liste durchlaufen werden.

Wenn diese Operation oft durchgeführt werden muss, wäre ein `set()` geeigneter. Da ist die Laufzeit vom ``in``-Operator unabhängig von der Anzahl der Elemente weil dort, genau wie bei Dictionaries, intern eine Hashtabelle verwendet wird. Im `set()` kann jedes Element aber nur einmal enthalten sein und die Reihenfolge bleibt nicht erhalten. Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.
droptix
User
Beiträge: 521
Registriert: Donnerstag 13. Oktober 2005, 21:27

Re: brauche es für eine große Liste

Beitragvon droptix » Montag 1. Januar 2007, 18:07

BlackJack hat geschrieben:Das ist aber umständlich und unnötig langsam. Wenn Du nur wissen willst, ob ein Element mindestens einmal enthalten ist kannst Du den ``in``-Operator benutzen: ``if x in liste:``. Da wird a) keine zusätzliche Liste angelegt und b) bricht die Suche beim ersten Treffer ab, es muss also nicht unnötigerweise der Rest der Liste durchlaufen werden.


Mein Ziel ist es eigentlich, in einem Dictionary nach einem bestimmten Werte-Paar zu suchen. Leider kann ich dafür if a in b nicht verwenden. Das Dictionary bildet dabei eine Tabelle ab. Die erste Spalte enthält eine eindeutige ID (enstpricht dem Key im Dictionary):

Code: Alles auswählen

myDict = {
    1: ("foo", "bar"),
    2: ("blah", "blubb")
}

def inDict(v, d):
    for i in d:
        if d[i] == v:
            return True
    return False

print inDict(("foo", "bar"), myDict)


BlackJack hat geschrieben:Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.


Ich behelfe mir momentan wie folgt: Beim dynamischen Erstellen des Dictionaries wid zusätzlich eine Liste angefertigt, die so aussieht:

Code: Alles auswählen

cache = []
cache.append(("foo", "bar"))
cache.append(("blah", "blubb"))


Dadurch kann ich natürlich jetzt mittels if v in cache schnell nach dem Werte-Paar suchen und kriege recht schnell ein True/False. ABER: Dadurch belege ich unnötig viel Speicherplatz, weil das Werte-Paar quasi doppelt im Programm abgelegt wird. Das erhöht auch die Daten-Redundanz und bringt eigentlich nur Nachteile. Daher wäre es mir lieber, diret in myDict nach dem Werte-Paar zu suchen. Allerdings sehe ich keine Möglichkeit, außer es von Anfang bis Ende zu durchwandern.

Jedes Werte-Paar ist allerdings einmalig, daher könnte ich anstelle der Liste parallel ein Set verwalten. Trotzdem bleiben dadurch Daten-Redundanz und die anderen Nachteile.
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Beitragvon Luzandro » Montag 1. Januar 2007, 19:09

Code: Alles auswählen

("foo", "bar") in myDict.values()

?
BlackJack

Re: brauche es für eine große Liste

Beitragvon BlackJack » Montag 1. Januar 2007, 19:28

droptix hat geschrieben:Mein Ziel ist es eigentlich, in einem Dictionary nach einem bestimmten Werte-Paar zu suchen. Leider kann ich dafür if a in b nicht verwenden. Das Dictionary bildet dabei eine Tabelle ab. Die erste Spalte enthält eine eindeutige ID (enstpricht dem Key im Dictionary):

Code: Alles auswählen

myDict = {
    1: ("foo", "bar"),
    2: ("blah", "blubb")
}

def inDict(v, d):
    for i in d:
        if d[i] == v:
            return True
    return False

print inDict(("foo", "bar"), myDict)


Die Funktion kannst Du durch das hier ersetzen:

Code: Alles auswählen

print ('foo', 'bar') in my_dict.itervalues()


Greifst Du auf die Elemente eigentlich auch über die ID zu? Falls ja, auch in der Programmphase wo du diesen Werte-Test benötigst?

BlackJack hat geschrieben:Wenn das ein Problem ist, müsstest Du parallel eine Liste verwalten.


Ich behelfe mir momentan wie folgt: Beim dynamischen Erstellen des Dictionaries wid zusätzlich eine Liste angefertigt, die so aussieht:

Code: Alles auswählen

cache = []
cache.append(("foo", "bar"))
cache.append(("blah", "blubb"))


Dadurch kann ich natürlich jetzt mittels if v in cache schnell nach dem Werte-Paar suchen und kriege recht schnell ein True/False.


Nicht wirklich schnell, bzw. nicht viel schneller als das durchgehen des Dictionaries und bei weitem nicht so schnell wie es mit `set()`s geht, vor allem wenn es sich um viele Elemente handelt.

ABER: Dadurch belege ich unnötig viel Speicherplatz, weil das Werte-Paar quasi doppelt im Programm abgelegt wird. Das erhöht auch die Daten-Redundanz und bringt eigentlich nur Nachteile.


Das Wertepaar selbst wird nur einmal abgelegt. Liste, `set()` oder Dictionary enthalten nur eine Referenz.

Wer ist online?

Mitglieder in diesem Forum: Torsten_K