Lambda-Vergleich Liste Verständnis Leistung

Question

Ich gab vor kurzem eine Frage eine Lambda-Funktion und in einer Antwort jemand erwähnt hatte Lambda Ungnade gefallen gehen, Listenkomprehensionen stattdessen zu verwenden. Ich bin relativ neu in Python. Ich lief einen einfachen Test:

import time

S=[x for x in range(1000000)]
T=[y**2 for y in range(300)]
#
#
time1 = time.time()
N=[x for x in S for y in T if x==y]
time2 = time.time()
print 'time diff [x for x in S for y in T if x==y]=', time2-time1
#print N
#
#
time1 = time.time()
N=filter(lambda x:x in S,T)
time2 = time.time()
print 'time diff filter(lambda x:x in S,T)=', time2-time1
#print N
#
#
#http://snipt.net/voyeg3r/python-intersect-lists/
time1 = time.time()
N = [val for val in S if val in T]
time2 = time.time()
print 'time diff [val for val in S if val in T]=', time2-time1
#print N
#
#
time1 = time.time()
N= list(set(S) & set(T))
time2 = time.time()
print 'time diff list(set(S) & set(T))=', time2-time1
#print N  #the results will be unordered as compared to the other ways!!!
#
#
time1 = time.time()
N=[]
for x in S:
    for y in T:
        if x==y:
            N.append(x)
time2 = time.time()
print 'time diff using traditional for loop', time2-time1
#print N

Sie alle drucken die gleiche N so kommentierte ich, dass print (mit Ausnahme der letzten Art und Weise es ungeordnete ist) stmt, aber die sich daraus ergebenden Zeitdifferenzen waren interessant über wiederholte Tests wie in diesem Beispiel zu sehen:

time diff [x for x in S for y in T if x==y]= 54.875
time diff filter(lambda x:x in S,T)= 0.391000032425
time diff [val for val in S if val in T]= 12.6089999676
time diff list(set(S) & set(T))= 0.125
time diff using traditional for loop 54.7970001698

So, während ich Listenkomprehensionen im Großen und Ganzen finde leichter zu lesen, scheint es zumindest in diesem Beispiel einige Performance-Probleme zu sein.

Also, zwei Fragen:

1. Warum ist Lambda usw. wird zur Seite geschoben?

2. Für die Liste Verständnis Hinsicht ist es eine effizientere Implementierung und wie würden Sie wissen, dass es ohne Prüfung effizienter ist? Ich meine, Lambda / map / Filter sollte weniger effizient sein wegen der zusätzlichen Funktionsaufrufe, aber es scheint, effizienter zu sein.

Paul

Answer 1

Ihre Tests geht es sehr verschiedene Dinge. Mit S 1M Elemente sind und wobei T 300:

[x for x in S for y in T if x==y]= 54.875

Diese Option macht 300M Gleichheitsvergleiche.

filter(lambda x:x in S,T)= 0.391000032425

Diese Option hat 300 linear durchsucht S.

[val for val in S if val in T]= 12.6089999676

Diese Option hat 1M linear durchsucht T.

list(set(S) & set(T))= 0.125

Diese Option hat zwei Kulisse und eine Schnittmenge.

---

Die Unterschiede in der Leistung zwischen diesen Optionen sind viel mehr im Zusammenhang mit den Algorithmen jeder verwendet, nicht als jede Differenz zwischen Listenkomprehensionen und lambda.

Answer 2

Wenn ich den Code zu beheben, so dass die Liste Verständnis und der Aufruf an filter werden die gleichen Arbeits Dinge tatsächlich tun eine ganze Menge ändern:

import time

S=[x for x in range(1000000)]
T=[y**2 for y in range(300)]
#
#
time1 = time.time()
N=[x for x in T if x in S]
time2 = time.time()
print 'time diff [x for x in T if x in S]=', time2-time1
#print N
#
#
time1 = time.time()
N=filter(lambda x:x in S,T)
time2 = time.time()
print 'time diff filter(lambda x:x in S,T)=', time2-time1
#print N

Dann ist der Ausgang ist mehr wie:

time diff [x for x in T if x in S]= 0.414485931396
time diff filter(lambda x:x in S,T)= 0.466315984726

So ist die Liste Verständnis hat eine Zeit, die in der Regel ziemlich nahe ist und in der Regel weniger als die Lambda-Ausdruck.

Der Grund, Lambda-Ausdrücke abgeschafft werden, ist, dass viele Leute denken, dass sie viel weniger lesbar als Listenkomprehensionen sind. Ich Art ungern zustimmen.

Answer 3

F: Warum Lambda usw. wird zur Seite geschoben

A: Liste Comprehensions und Generator Ausdrücke werden im Allgemeinen als eine schöne Mischung aus Leistung und Lesbarkeit sein. Der reine Funktions-Programmierstil, wo Sie map() verwenden, reduce() und filter() mit Funktionen (oft lambda Funktionen) nicht als klar angesehen. Auch hat Python eingebaute Funktionen hinzugefügt, die schön alle wichtigen Anwendungen für reduce() behandeln.

Angenommen, Sie eine Liste zusammenzufassen wollte. Es gibt zwei Möglichkeiten, es zu tun.

lst = range(10)
print reduce(lambda x, y: x + y, lst)

print sum(lst)

Melden Sie mich als Fan von sum() und kein Fan von reduce() dieses Problem zu lösen. Hier ist ein weiteres, ähnliches Problem:

lst = range(10)
print reduce(lambda x, y: bool(x or y), lst)

print any(lst)

Nicht nur die any() Lösung einfacher zu verstehen, aber es ist auch viel schneller; es hat Kurzauswertung, so dass es so bald Auswertung stoppt, da es keinen wahren Wert gefunden hat. Die reduce() hat durch die gesamte Liste anzukurbeln. Dieser Unterschied in der Leistung wäre stark, wenn die Liste eine Million Artikel lang ist, und das erste Element ausgewertet wahr. By the way, wurde any() in Python hinzugefügt 2,5; wenn Sie es nicht haben, hier ist eine Version für ältere Versionen von Python:

def any(iterable):
    for x in iterable:
        if x:
            return True
    return False

Angenommen, Sie eine Liste der Quadrate der geraden Zahlen von einigen Liste machen wollte.

lst = range(10)
print map(lambda x: x**2, filter(lambda x: x % 2 == 0, lst))

print [x**2 for x in lst if x % 2 == 0]

Nehmen wir nun an Sie, dass die Liste der Quadrate zusammenzufassen wollte.

lst = range(10)
print sum(map(lambda x: x**2, filter(lambda x: x % 2 == 0, lst)))

# list comprehension version of the above
print sum([x**2 for x in lst if x % 2 == 0])

# generator expression version; note the lack of '[' and ']'
print sum(x**2 for x in lst if x % 2 == 0)

Der Generator Ausdruck tatsächlich gibt nur ein iterable Objekt. sum() nimmt die iterable und zieht Werte von ihm, einer nach dem anderen, Summieren, wie es geht, bis alle Werte verbraucht werden. Dies ist der effizienteste Weg, dieses Problem in Python lösen. Im Gegensatz dazu die map() Lösung, und die äquivalente Lösung mit einer Liste Verständnis innerhalb des Anrufs sum(), muss zuerst eine Liste erstellen; Diese Liste wird dann einmal zu sum(), verwendet geleitet und verworfen. Die Zeit, um die Liste zu erstellen und es dann wieder zu löschen ist einfach verschwendet. (EDIT:. Und beachten Sie, dass die Version mit beiden map und filter bauen müssen zwei Listen, eine von filter gebaut und ein von map gebaut; beide Listen werden verworfen) (EDIT : Aber in Python 3.0 und neueren, map () und filter () sind nun beide „faul“ und einen Iterator statt einer Liste erzeugen, so dass dieser Punkt weniger wahr ist, als es früher auch Sie, in Python 2.x. konnten itertools.imap () und itertools.ifilter () für Iterator-basierte Karte und Filter verwenden. Aber ich weiterhin die Generator Ausdruck Lösungen über beliebige Karte / Filterlösungen.)

bevorzugen

Mit dem Komponieren map(), filter() und reduce() in Kombination mit lambda Funktionen können Sie viele mächtigen Dinge zu tun. Aber Python hat idiomatische Möglichkeiten, um die gleichen Probleme zu lösen, die gleichzeitig eine bessere Leistung und leichter zu lesen und zu verstehen.

Answer 4

Viele Menschen haben bereits darauf hingewiesen, dass Sie Äpfel mit Orangen vergleichen sind, etc, etc. Aber ich denke, niemand gezeigt, wie man ein wirklich einfaches Vergleich - Liste Verständnis vs Karte und Lambda mit wenig sonst in der Quere zu kommen - - und das könnte sein:

$ python -mtimeit -s'L=range(1000)' 'map(lambda x: x+1, L)'
1000 loops, best of 3: 328 usec per loop
$ python -mtimeit -s'L=range(1000)' '[x+1 for x in L]'
10000 loops, best of 3: 129 usec per loop

Hier können Sie sehr stark die Kosten für das Lambda sehen -. Etwa 200 Mikrosekunden, die im Fall einer hinreichend einfachen Bedienung wie dieser überschwemmt die Operation selbst

Die Zahlen sind sehr ähnlich mit Filter natürlich, da das Problem ist, nicht Filter oder Karte, sondern das Lambda selbst:

$ python -mtimeit -s'L=range(1000)' '[x for x in L if not x%7]'
10000 loops, best of 3: 162 usec per loop
$ python -mtimeit -s'L=range(1000)' 'filter(lambda x: not x%7, L)'
1000 loops, best of 3: 334 usec per loop

Ohne Zweifel ist die Tatsache, dass Lambda weniger klar sein kann, oder seine seltsame Verbindung mit Sparta (Spartans einen Lambda hatte, für „Lakedaimon“, auf ihre Schilde gemalt - dies legt nahe, dass Lambda ziemlich diktatorisch ist und blutig ;-) haben zumindest so viel zu tun mit seiner langsam aus der Mode fallen, wie er seine Leistung Kosten. Aber diese sind sehr real.

Answer 5

Zu allererst Test wie folgt aus:

import timeit

S=[x for x in range(10000)]
T=[y**2 for y in range(30)]

print "v1", timeit.Timer('[x for x in S for y in T if x==y]',
             'from __main__ import S,T').timeit(100)
print "v2", timeit.Timer('filter(lambda x:x in S,T)',
             'from __main__ import S,T').timeit(100)
print "v3", timeit.Timer('[val for val in T if val in S]',
             'from __main__ import S,T').timeit(100)
print "v4", timeit.Timer('list(set(S) & set(T))',
             'from __main__ import S,T').timeit(100)

Und grundsätzlich verschiedene Dinge, die Sie tun, jedes Mal, wenn Sie testen. Wenn Sie sich die Liste Verständnis zum Beispiel umschreiben als

[val for val in T if val in S]

Leistung auf einer Stufe mit dem 'Lambda / Filter' würde konstruieren.

Answer 6

Sets sind die richtige Lösung. Allerdings versuchen, S und T und sieht Swapping wie lange es dauert!

filter(lambda x:x in T,S)

$ python -m timeit -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' 'filter(lambda x:x in S,T)'
10 loops, best of 3: 485 msec per loop
$ python -m timeit -r1 -n1 -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' 'filter(lambda x:x in T,S)'
1 loops, best of 1: 19.6 sec per loop

Sie sehen also, dass die Reihenfolge der S und T sehr wichtig sind,

Ändern der Reihenfolge der Liste Verständnis des Filters anzupassen gibt

$ python -m timeit  -s'S=[x for x in range(1000000)];T=[y**2 for y in range(300)]' '[x for x in T if x in S]'
10 loops, best of 3: 441 msec per loop

Also, wenn tatsächlich die Liste Verständnis ist etwas schneller als das Lambda auf meinem Computer

Answer 7

Ihre Liste Verständnis und Lambda sind verschiedene Dinge tun würde [val for val in T if val in S] die Liste Verständnis das Lambda entspricht.

Die Effizienz ist nicht der Grund, warum Liste Verständnis bevorzugt werden (während sie tatsächlich etwas schneller in fast allen Fällen sind). Der Grund, warum sie bevorzugt sind, ist die Lesbarkeit.

Versuchen Sie es mit kleineren Schleifenkörpern und größeren Schleifen, wie T eine Menge zu machen, und S. auf meinem Rechner In diesem Fall durchläuft die Liste Verständnis ist fast doppelt so schnell.

Answer 8

Ihre Profilierung falsch gemacht. Werfen Sie einen Blick die timeit Modul und versuchen Sie es erneut.

lambda definiert anonyme Funktionen. Ihr Hauptproblem ist, dass viele Leute nicht wissen, die ganze Python-Bibliothek und nutzen sie Funktionen neu zu implementieren, die bereits im operator sind, functools etc Modul (und viel schneller).

Liste Comprehensions hat nichts mit lambda zu tun. Sie entsprechen den Standard filter und map Funktionen von funktionalen Sprachen. LCs bevorzugt, weil sie als Generatoren zu verwendet werden können, nicht die Lesbarkeit zu erwähnen.

Answer 9

Das ist ziemlich schnell:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

time1 = time.time()
N = [x for x in T if binary_search(S, x) >= 0]
time2 = time.time()
print 'time diff binary search=', time2-time1

Einfach. Weniger comparisions, weniger Zeit

Answer 10

Liste Comprehensions kann einen größeren Unterschied machen, wenn Sie Ihre gefilterten Ergebnisse zu verarbeiten. In Ihrem Fall bauen Sie nur eine Liste, aber wenn Sie haben, so etwas zu tun:

n = [f(i) for i in S if some_condition(i)]

Sie von LC-Optimierung über diese gewinnen würden:

n = map(f, filter(some_condition(i), S))

, nur weil diese eine Zwischenliste erstellen (oder Tupel oder eine Zeichenfolge, je nach der Art von S). Als Folge werden Sie auch eine andere Auswirkungen auf die von den einzelnen Verfahren verwendeten Speicher feststellen, wird das LC halten niedriger.

Das Lambda in der Materie selbst nicht.