¿Son las listas por comprensión y las funciones funcionales más rápidas que los “bucles for”?

En términos de rendimiento en Python, es una lista-comprensión, o funciones como map(), filter()y reduce()más rápido que un bucle? ¿Por qué, técnicamente, se ejecutan en una velocidad C , mientras que el bucle for se ejecuta en la velocidad de la máquina virtual Python ?

Supongamos que en un juego que estoy desarrollando necesito dibujar mapas complejos y enormes usando bucles for. Esta pregunta sería definitivamente relevante, porque si una comprensión de listas, por ejemplo, es realmente más rápida, sería una opción mucho mejor para evitar retrasos (a pesar de la complejidad visual del código).

Las siguientes son pautas aproximadas y conjeturas fundamentadas basadas en la experiencia. Debería timeito perfilar su caso de uso concreto para obtener números concretos, y esos números ocasionalmente pueden no estar de acuerdo con lo siguiente.

La comprensión de una lista suele ser un poco más rápida que el forbucle exactamente equivalente (que en realidad crea una lista), probablemente porque no tiene que buscar la lista y su appendmétodo en cada iteración. Sin embargo, una lista de comprensión todavía hace un bucle a nivel de código de bytes:

>>> 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

Usar una comprensión de lista en lugar de un bucle que no crea una lista, acumular sin sentido una lista de valores sin sentido y luego tirar la lista a la basura, a menudo es más lento debido a la sobrecarga de crear y extender la lista. Las listas por comprensión no son mágicas, ya que son intrínsecamente más rápidas que un buen ciclo antiguo.

En cuanto a las funciones de procesamiento lista funcionales: Si bien éstas se han escrito en C y probablemente superan a funciones equivalentes escritos en Python, que son no necesariamente la opción más rápida. Se espera cierta aceleración si la función también está escrita en C. Pero en la mayoría de los casos que usan una lambda(u otra función de Python), la sobrecarga de configurar repetidamente los marcos de pila de Python, etc., consume cualquier ahorro. Simplemente hacer el mismo trabajo en línea, sin llamadas a funciones (por ejemplo, una lista de comprensión en lugar de mapo filter) suele ser un poco más rápido.

Supongamos que en un juego que estoy desarrollando necesito dibujar mapas complejos y enormes usando bucles for. Esta pregunta sería definitivamente relevante, porque si una comprensión de listas, por ejemplo, es realmente más rápida, sería una opción mucho mejor para evitar retrasos (a pesar de la complejidad visual del código).

Lo más probable es que, si un código como este no es lo suficientemente rápido cuando está escrito en un buen Python no "optimizado", ninguna cantidad de microoptimización a nivel de Python lo hará lo suficientemente rápido y debería comenzar a pensar en pasar a C. Las micro optimizaciones a menudo pueden acelerar considerablemente el código Python, hay un límite bajo (en términos absolutos) para esto. Además, incluso antes de llegar a ese límite, simplemente se vuelve más rentable (15% de aceleración frente a 300% de aceleración con el mismo esfuerzo) para morder la bala y escribir algo de C.

Si comprueba la información en python.org , puede ver este resumen:

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

Pero realmente debería leer el artículo anterior en detalle para comprender la causa de la diferencia de rendimiento.

También le sugiero encarecidamente que debe cronometrar su código utilizando timeit . Al final del día, puede haber una situación en la que, por ejemplo, es posible que deba salir del forciclo cuando se cumple una condición. Potencialmente, podría ser más rápido que averiguar el resultado llamando map.

Usted pregunta específicamente sobre map(), filter()y reduce(), pero suponga que desea saber acerca de la programación funcional en general. Habiendo probado esto yo mismo en el problema de calcular distancias entre todos los puntos dentro de un conjunto de puntos, la programación funcional (usando la starmapfunción del itertoolsmódulo incorporado ) resultó ser un poco más lenta que los bucles for (tomando 1.25 veces más tiempo, en hecho). Aquí está el código de muestra que utilicé:

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

¿Es la versión funcional más rápida que la de procedimiento?

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')

Escribí un guión simple que prueba la velocidad y esto es lo que descubrí. En realidad, for loop fue el más rápido en mi caso. Eso realmente me sorprendió, mira abajo (estaba calculando la suma de cuadrados).

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

He modificado @ código de Alisa y se utiliza cProfilepara mostrar por qué lista por comprensión es más rápido:

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()

Aquí están los resultados:

=========================
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}

EN MI HUMILDE OPINIÓN:

• reducey mapen general son bastante lentos. No solo eso, usar sumen los iteradores que mapregresaron es lento, en comparación con suming una lista
• for_loop usa append, que por supuesto es lento hasta cierto punto
• La comprensión de la lista no solo dedicó el menor tiempo a construir la lista, sino que también la hace summucho más rápida, en contraste conmap

Agregando un giro a la respuesta de Alphii , en realidad, el ciclo for sería el segundo mejor y aproximadamente 6 veces más lento quemap

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])

Los principales cambios han sido eliminar las sumllamadas lentas , así como las probablemente innecesarias int()en el último caso. Poner el bucle for y el mapa en los mismos términos lo convierte en un hecho bastante real. Recuerde que las lambdas son conceptos funcionales y teóricamente no deberían tener efectos secundarios, pero, bueno, pueden tener efectos secundarios como agregar a. Resultados en este caso con Python 3.6.1, Ubuntu 14.04, Intel (R) Core (TM) i7-4770 CPU @ 3.40GHz

0:00:00.257703 #Reduce
0:00:00.184898 #For loop
0:00:00.031718 #Map
0:00:00.212699 #List comprehension

Me las arreglé para modificar parte del código de @ alpiii y descubrí que la comprensión de la lista es un poco más rápida que el bucle for. Puede deberse a int()que no es justo entre la comprensión de la lista y el bucle for.

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