Sind Listenverständnisse und Funktionsfunktionen schneller als „for-Schleifen“?

155

In Bezug auf die Leistung in Python, ist eine Liste Verständnis oder Funktionen wie map(), filter()und reduce()schneller als eine for - Schleife? Warum werden sie technisch mit einer C-Geschwindigkeit ausgeführt , während die for-Schleife mit der Geschwindigkeit der virtuellen Python-Maschine ausgeführt wird ?

Angenommen, ich muss in einem Spiel, das ich entwickle, komplexe und riesige Karten mit for-Schleifen zeichnen. Diese Frage wäre definitiv relevant, denn wenn beispielsweise ein Listenverständnis tatsächlich schneller ist, wäre es eine viel bessere Option, um Verzögerungen zu vermeiden (trotz der visuellen Komplexität des Codes).

Ericson Willians
quelle

Antworten:

146

Das Folgende sind grobe Richtlinien und fundierte Vermutungen, die auf Erfahrung basieren. Du solltesttimeit oder profilieren Sie Ihren konkreten Anwendungsfall, um harte Zahlen zu erhalten, und diese Zahlen stimmen gelegentlich nicht mit den folgenden überein.

Ein Listenverständnis ist normalerweise ein kleines bisschen schneller als die genau äquivalente forSchleife (die tatsächlich eine Liste erstellt), höchstwahrscheinlich, weil die Liste und ihre appendMethode nicht bei jeder Iteration nachgeschlagen werden müssen. Ein Listenverständnis führt jedoch immer noch eine Schleife auf Bytecode-Ebene durch:

>>> dis.dis(<the code object for `[x for x in range(10)]`>)
 1           0 BUILD_LIST               0
             3 LOAD_FAST                0 (.0)
       >>    6 FOR_ITER                12 (to 21)
             9 STORE_FAST               1 (x)
            12 LOAD_FAST                1 (x)
            15 LIST_APPEND              2
            18 JUMP_ABSOLUTE            6
       >>   21 RETURN_VALUE

Die Verwendung eines Listenverständnisses anstelle einer Schleife, die keine Liste erstellt, eine Liste mit bedeutungslosen Werten unsinnig ansammelt und die Liste dann wegwirft, ist häufig langsamer, da das Erstellen und Erweitern der Liste aufwändig ist. Listenverständnisse sind keine Magie, die von Natur aus schneller ist als eine gute alte Schleife.

Funktionsverarbeitungslisten: Während diese in C geschrieben sind und wahrscheinlich die in Python geschriebenen äquivalenten Funktionen übertreffen, sind sie nicht unbedingt die schnellste Option. Eine gewisse Beschleunigung wird erwartet, wenn die Funktion auch in C geschrieben ist. In den meisten Fällen, in denen eine lambda(oder eine andere Python-Funktion) verwendet wird, führt der Aufwand für das wiederholte Einrichten von Python-Stack-Frames usw. zu Einsparungen. Die gleiche Arbeit inline ohne Funktionsaufrufe (z. B. ein Listenverständnis anstelle von mapoder filter) zu erledigen, ist oft etwas schneller.

Angenommen, ich muss in einem Spiel, das ich entwickle, komplexe und riesige Karten mit for-Schleifen zeichnen. Diese Frage wäre definitiv relevant, denn wenn beispielsweise ein Listenverständnis tatsächlich schneller ist, wäre es eine viel bessere Option, um Verzögerungen zu vermeiden (trotz der visuellen Komplexität des Codes).

Wenn Code wie dieser nicht bereits schnell genug ist, wenn er in gutem, nicht "optimiertem" Python geschrieben ist, wird er wahrscheinlich durch keine Mikrooptimierung auf Python-Ebene schnell genug, und Sie sollten darüber nachdenken, auf C zu fallen Mikrooptimierungen können Python-Code oft erheblich beschleunigen, es gibt eine niedrige (in absoluten Zahlen) Grenze dafür. Darüber hinaus wird es noch kostengünstiger (15% Beschleunigung gegenüber 300% Beschleunigung bei gleichem Aufwand), die Kugel zu beißen und etwas C zu schreiben, noch bevor Sie diese Obergrenze erreichen.


quelle
25

Wenn Sie die Informationen auf python.org überprüfen , können Sie diese Zusammenfassung sehen:

Version Time (seconds)
Basic loop 3.47
Eliminate dots 2.45
Local variable & no dots 1.79
Using map function 0.54

Sie sollten den obigen Artikel jedoch ausführlich lesen, um die Ursache für den Leistungsunterschied zu verstehen.

Ich empfehle außerdem dringend, dass Sie Ihren Code mithilfe von timeit zeitlich festlegen . Am Ende des Tages kann es vorkommen, dass Sie beispielsweise aus der forSchleife ausbrechen müssen, wenn eine Bedingung erfüllt ist. Es könnte möglicherweise schneller sein, als das Ergebnis durch einen Anruf herauszufinden map.

Anthony Kong
quelle
17
Obwohl diese Seite gut gelesen und teilweise verwandt ist, ist es nicht hilfreich, nur diese Zahlen zu zitieren, möglicherweise sogar irreführend.
1
Dies gibt keinen Hinweis darauf, was Sie planen. Die relative Leistung hängt stark davon ab, was sich in der Schleife / listcomp / map befindet.
user2357112 unterstützt Monica
@ Delnan Ich stimme zu. Ich habe meine Antwort geändert, um OP zu drängen, die Dokumentation zu lesen, um den Leistungsunterschied zu verstehen.
Anthony Kong
@ user2357112 Du musst die Wiki-Seite lesen, die ich für den Kontext verlinkt habe. Ich habe es als Referenz für OP gepostet.
Anthony Kong
13

Sie fragen gezielt nach map(), filter()und reduce(), aber ich nehme an, Sie über funktionale Programmierung im Allgemeinen wissen wollen. Nachdem ich dies selbst auf das Problem der Berechnung der Abstände zwischen allen Punkten innerhalb einer Reihe von Punkten getestet hatte, stellte sich heraus, dass die funktionale Programmierung (unter Verwendung der starmapFunktion des eingebauten itertoolsModuls) etwas langsamer war als die for-Schleifen (die 1,25-mal so lange dauerte) Tatsache). Hier ist der Beispielcode, den ich verwendet habe:

import itertools, time, math, random

class Point:
    def __init__(self,x,y):
        self.x, self.y = x, y

point_set = (Point(0, 0), Point(0, 1), Point(0, 2), Point(0, 3))
n_points = 100
pick_val = lambda : 10 * random.random() - 5
large_set = [Point(pick_val(), pick_val()) for _ in range(n_points)]
    # the distance function
f_dist = lambda x0, x1, y0, y1: math.sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)
    # go through each point, get its distance from all remaining points 
f_pos = lambda p1, p2: (p1.x, p2.x, p1.y, p2.y)

extract_dists = lambda x: itertools.starmap(f_dist, 
                          itertools.starmap(f_pos, 
                          itertools.combinations(x, 2)))

print('Distances:', list(extract_dists(point_set)))

t0_f = time.time()
list(extract_dists(large_set))
dt_f = time.time() - t0_f

Ist die funktionale Version schneller als die prozedurale Version?

def extract_dists_procedural(pts):
    n_pts = len(pts)
    l = []    
    for k_p1 in range(n_pts - 1):
        for k_p2 in range(k_p1, n_pts):
            l.append((pts[k_p1].x - pts[k_p2].x) ** 2 +
                     (pts[k_p1].y - pts[k_p2].y) ** 2)
    return l

t0_p = time.time()
list(extract_dists_procedural(large_set)) 
    # using list() on the assumption that
    # it eats up as much time as in the functional version

dt_p = time.time() - t0_p

f_vs_p = dt_p / dt_f
if f_vs_p >= 1.0:
    print('Time benefit of functional progamming:', f_vs_p, 
          'times as fast for', n_points, 'points')
else:
    print('Time penalty of functional programming:', 1 / f_vs_p, 
          'times as slow for', n_points, 'points')
andreipmbcn
quelle
2
Sieht nach einer ziemlich komplizierten Art aus, diese Frage zu beantworten. Können Sie es reduzieren, damit es sinnvoller ist?
Aaron Hall
2
@ AaronHall Ich finde die Antwort von andreipmbcn eigentlich ziemlich interessant, weil es ein nicht triviales Beispiel ist. Code, mit dem wir spielen können.
Anthony Kong
@AaronHall, soll ich den Textabsatz bearbeiten, damit er klarer und unkomplizierter klingt, oder soll ich den Code bearbeiten?
andreipmbcn
9

Ich habe ein einfaches Skript geschrieben, das die Geschwindigkeit testet, und das habe ich herausgefunden. Eigentlich war for loop in meinem Fall am schnellsten. Das hat mich wirklich überrascht, schau unten (berechnete die Summe der Quadrate).

from functools import reduce
import datetime


def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next**2, numbers, 0)


def square_sum2(numbers):
    a = 0
    for i in numbers:
        i = i**2
        a += i
    return a

def square_sum3(numbers):
    sqrt = lambda x: x**2
    return sum(map(sqrt, numbers))

def square_sum4(numbers):
    return(sum([int(i)**2 for i in numbers]))


time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
0:00:00.302000 #Reduce
0:00:00.144000 #For loop
0:00:00.318000 #Map
0:00:00.390000 #List comprehension
alphiii
quelle
Mit Python 3.6.1 sind die Unterschiede nicht so groß. Reduzieren und Map gehen auf 0,24 und Listenverständnis auf 0,29. Denn ist höher bei 0,18.
jjmerelo
Das Eliminieren des intIn square_sum4macht es auch ziemlich viel schneller und nur ein bisschen langsamer als die for-Schleife.
jjmerelo
5

Wenn Sie der Alphii-Antwort eine Wendung hinzufügen , ist die for-Schleife die zweitbeste und ungefähr sechsmal langsamer alsmap

from functools import reduce
import datetime


def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next**2, numbers, 0)


def square_sum2(numbers):
    a = 0
    for i in numbers:
        a += i**2
    return a

def square_sum3(numbers):
    a = 0
    map(lambda x: a+x**2, numbers)
    return a

def square_sum4(numbers):
    a = 0
    return [a+i**2 for i in numbers]

time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])

Die wichtigsten Änderungen bestanden darin, die langsamen sumAnrufe sowie die int()im letzten Fall wahrscheinlich unnötigen zu beseitigen . Wenn Sie die for-Schleife und die Map in die gleichen Begriffe setzen, ist dies tatsächlich eine Tatsache. Denken Sie daran, dass Lambdas funktionale Konzepte sind und theoretisch keine Nebenwirkungen haben sollten, aber sie können Nebenwirkungen wie das Hinzufügen zu haben a. Ergebnisse in diesem Fall mit Python 3.6.1, Ubuntu 14.04, Intel (R) Core (TM) i7-4770-CPU bei 3,40 GHz

0:00:00.257703 #Reduce
0:00:00.184898 #For loop
0:00:00.031718 #Map
0:00:00.212699 #List comprehension
jjmerelo
quelle
2
square_sum3 und square_sum4 sind falsch. Sie werden keine Summe geben. Die Antwort unten von @alisca chen ist tatsächlich richtig.
ShikharDua
5

Ich habe den Code von @ Alisa geändert und cProfilegezeigt, warum das Listenverständnis schneller ist:

from functools import reduce
import datetime

def reduce_(numbers):
    return reduce(lambda sum, next: sum + next * next, numbers, 0)

def for_loop(numbers):
    a = []
    for i in numbers:
        a.append(i*2)
    a = sum(a)
    return a

def map_(numbers):
    sqrt = lambda x: x*x
    return sum(map(sqrt, numbers))

def list_comp(numbers):
    return(sum([i*i for i in numbers]))

funcs = [
        reduce_,
        for_loop,
        map_,
        list_comp
        ]

if __name__ == "__main__":
    # [1, 2, 5, 3, 1, 2, 5, 3]
    import cProfile
    for f in funcs:
        print('=' * 25)
        print("Profiling:", f.__name__)
        print('=' * 25)
        pr = cProfile.Profile()
        for i in range(10**6):
            pr.runcall(f, [1, 2, 5, 3, 1, 2, 5, 3])
        pr.create_stats()
        pr.print_stats()

Hier sind die Ergebnisse:

=========================
Profiling: reduce_
=========================
         11000000 function calls in 1.501 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.162    0.000    1.473    0.000 profiling.py:4(reduce_)
  8000000    0.461    0.000    0.461    0.000 profiling.py:5(<lambda>)
  1000000    0.850    0.000    1.311    0.000 {built-in method _functools.reduce}
  1000000    0.028    0.000    0.028    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: for_loop
=========================
         11000000 function calls in 1.372 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.879    0.000    1.344    0.000 profiling.py:7(for_loop)
  1000000    0.145    0.000    0.145    0.000 {built-in method builtins.sum}
  8000000    0.320    0.000    0.320    0.000 {method 'append' of 'list' objects}
  1000000    0.027    0.000    0.027    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: map_
=========================
         11000000 function calls in 1.470 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.264    0.000    1.442    0.000 profiling.py:14(map_)
  8000000    0.387    0.000    0.387    0.000 profiling.py:15(<lambda>)
  1000000    0.791    0.000    1.178    0.000 {built-in method builtins.sum}
  1000000    0.028    0.000    0.028    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=========================
Profiling: list_comp
=========================
         4000000 function calls in 0.737 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.318    0.000    0.709    0.000 profiling.py:18(list_comp)
  1000000    0.261    0.000    0.261    0.000 profiling.py:19(<listcomp>)
  1000000    0.131    0.000    0.131    0.000 {built-in method builtins.sum}
  1000000    0.027    0.000    0.027    0.000 {method 'disable' of '_lsprof.Profiler' objects}

MEINER BESCHEIDENEN MEINUNG NACH:

  • reduceund mapsind im Allgemeinen ziemlich langsam. Darüber hinaus ist die Verwendung sumder zurückgegebenen Iteratoren im mapVergleich zu sumeiner Liste langsam
  • for_loop verwendet append, was natürlich bis zu einem gewissen Grad langsam ist
  • Das Listenverständnis hat nicht nur die geringste Zeit für die Erstellung der Liste aufgewendet, sondern ist sumim Gegensatz zu auch viel schnellermap
tjysdsg
quelle
3

Ich habe es geschafft, einen Teil des Codes von @ alpiii zu ändern und festgestellt, dass das Listenverständnis etwas schneller ist als für die Schleife. Es kann durch verursacht werden int(), es ist nicht fair zwischen Listenverständnis und for-Schleife.

from functools import reduce
import datetime

def time_it(func, numbers, *args):
    start_t = datetime.datetime.now()
    for i in range(numbers):
        func(args[0])
    print (datetime.datetime.now()-start_t)

def square_sum1(numbers):
    return reduce(lambda sum, next: sum+next*next, numbers, 0)

def square_sum2(numbers):
    a = []
    for i in numbers:
        a.append(i*2)
    a = sum(a)
    return a

def square_sum3(numbers):
    sqrt = lambda x: x*x
    return sum(map(sqrt, numbers))

def square_sum4(numbers):
    return(sum([i*i for i in numbers]))

time_it(square_sum1, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum2, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum3, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
time_it(square_sum4, 100000, [1, 2, 5, 3, 1, 2, 5, 3])
0:00:00.101122 #Reduce

0:00:00.089216 #For loop

0:00:00.101532 #Map

0:00:00.068916 #List comprehension
Alisca Chen
quelle