python - ¿Las listas de comprensión y las funciones funcionales son más rápidas que "para bucles"?

performance for-loop

Question

En términos de rendimiento en Python, ¿es una lista de comprensión, o funciona como map (), filter () y reduce () más rápido que un ciclo for? ¿Por qué, técnicamente, "corren 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 for. Esta pregunta sería definitivamente relevante, porque si una lista de comprensión, por ejemplo, es más rápida, sería una opción mucho mejor para evitar retrasos (a pesar de la complejidad visual del código).

Answer 1

Añadiendo un giro a la respuesta de Alphii , en realidad el bucle for sería el segundo mejor y unas 6 veces más lento que el map

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 llamadas de sum lenta, así como la probablemente innecesaria int() en el último caso. Poner el bucle for y el mapa en los mismos términos lo hace bastante real, en realidad. Recuerde que las lambdas son conceptos funcionales y teóricamente no deberían tener efectos secundarios, pero, bueno, pueden tener efectos secundarios como agregar aa. 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
0:00:00.184898
0:00:00.031718
0:00:00.212699

Answer 2

Escribí un guión simple que prueba la velocidad y esto es lo que descubrí. En realidad, el ciclo 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

Answer 3

Preguntas específicamente sobre map (), filter () y reduce (), pero asumo que quieres saber sobre programación funcional en general. Habiendo probado esto yo mismo sobre el problema de calcular las distancias entre todos los puntos dentro de un conjunto de puntos, la programación funcional (usando la función de mapa de estrellas del módulo integrado de itertools) resultó ser un poco más lenta que los bucles for (tardando 1.25 veces más , de 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 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'')

Answer 4

Si revisas la información en python.org , puedes 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 debe leer el artículo anterior en detalles para comprender la causa de la diferencia de rendimiento.

También le sugiero encarecidamente que debe timeit su código utilizando timeit . Al final del día, puede haber una situación en la que, por ejemplo, deba salir del bucle for cuando se cumple una condición. Podría ser más rápido que encontrar el resultado llamando al map .

Answer 5

Las siguientes son pautas aproximadas y conjeturas basadas en la experiencia. Debe timeit o el perfil de su caso de uso concreto para obtener números duros, y esos números pueden estar en desacuerdo ocasionalmente con los siguientes.

Una lista de comprensión es usualmente un poco más rápida que el bucle for equivalent (que realmente construye una lista), muy probablemente porque no tiene que buscar la lista y su método de append en cada iteración. Sin embargo, una lista de comprensión todavía tiene un bucle de nivel de byte:

>>> 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 lista de comprensión en lugar de un bucle que no crea una lista, sin sentido acumular 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 que son inherentemente más rápidas que un viejo bucle.

En cuanto a las funciones de procesamiento de listas funcionales: Si bien están escritas en C y probablemente superan las funciones equivalentes escritas en Python, no son necesariamente la opción más rápida. Se espera cierta aceleración si la función está escrita en C también. Pero la mayoría de los casos que usan una lambda (u otra función de Python), la sobrecarga de configurar repetidamente los cuadros de pila de Python se consumen los ahorros. Simplemente haciendo el mismo trabajo en línea, sin llamadas de función (por ejemplo, una lista de comprensión en lugar de map o 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 for. Esta pregunta sería definitivamente relevante, porque si una lista de comprensión, por ejemplo, es 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 el código como este no es lo suficientemente rápido cuando está escrito en Python bueno no optimizado, ninguna cantidad de micro optimización de Python va a hacerlo lo suficientemente rápido y deberías empezar a pensar en bajar a C. Si bien 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.