¿Las comprensiones de listas y las funciones funcionales son más rápidas que "for loops"?

En términos de rendimiento en Python, ¿es una lista de comprensión, o funciones similares map(), filter()y reduce()más rápida que un bucle for? ¿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 de Python ?

Supongamos que en un juego que estoy desarrollando necesito dibujar mapas complejos y enormes usando bucles. Esta pregunta sería definitivamente relevante, ya que si una comprensión de la lista, 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 educadas basadas en la experiencia. Debería timeito perfilar su caso de uso concreto para obtener números concretos, y esos números pueden estar ocasionalmente en desacuerdo con los siguientes.

La comprensión de una lista suele ser un poco más rápida que el forbucle precisamente equivalente (que en realidad construye una lista), muy probablemente porque no tiene que buscar la lista y su appendmétodo en cada iteración. Sin embargo, una comprensión de la lista todavía hace un bucle de 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 la lista en lugar de un bucle que no construye una lista, acumular sin sentido una lista de valores sin sentido y luego tirar la lista, a menudo es más lento debido a la sobrecarga de crear y extender la lista. Las comprensiones de listas no son mágicas, es inherentemente más rápido que un buen bucle antiguo.

En cuanto a las funciones de procesamiento de listas funcionales: si bien están escritas en C y probablemente superan a las funciones equivalentes escritas en Python, son no necesariamente la opción más rápida. Se espera algo de velocidad si la función también está escrita en C. Pero 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 comprensión de la lista en lugar de mapo filter) es a menudo un poco más rápido.

Supongamos que en un juego que estoy desarrollando necesito dibujar mapas complejos y enormes usando bucles. Esta pregunta sería definitivamente relevante, ya que si una comprensión de la lista, 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 se escribe en un buen Python no "optimizado", ninguna cantidad de micro optimización de nivel de Python lo hará lo suficientemente rápido y debe comenzar a pensar en caer a C. Las micro optimizaciones a menudo pueden acelerar el código de Python considerablemente, hay un límite bajo (en términos absolutos) para esto. Además, incluso antes de alcanzar ese techo, se vuelve simplemente 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 revisa 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 detalles para comprender la causa de la diferencia de rendimiento.

También le sugiero 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 descubrir el resultado llamando map.

Usted pregunta específicamente sobre map(), filter()y reduce(), pero supongo que quiere saber sobre 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, 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

¿La versión funcional es más rápida que la versión 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 script simple que prueba la velocidad y esto es lo que descubrí. En realidad, el bucle fue 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

Yo modifiqué @ 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, usando sumen los iteradores quemap regresó es lento, en comparación consum con una lista
• for_loop utiliza append, que por supuesto es lento hasta cierto punto
• la comprensión de la lista no solo pasó el menor tiempo construyendo la lista, sino que también es summucho más rápida, en contraste conmap

Agregando un giro a la respuesta de Alphii , en realidad el bucle 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 y el mapa for en los mismos términos lo convierte en un hecho bastante real. Recuerde que las lambdas son conceptos funcionales y, en teoría, no deberían tener efectos secundarios, pero, bueno, pueden tener efectos secundarios como sumar 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

Logré modificar algunos de los códigos de @ alpiii y descubrí que la comprensión de la Lista es un poco más rápida que para el bucle. Puede ser causado por int(), 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