Comparación de listas de comprensión y bucles explícitos (3 generadores de matriz más rápidos que 1 para bucle)

Hice la tarea y accidentalmente encontré una extraña inconsistencia en la velocidad del algoritmo. Aquí hay 2 versiones del código de la misma función pero con 1 diferencia: en la primera versión, uso 3 veces el generador de matrices para filtrar algunas matrices y en la segunda versión, uso 1 para el bucle con 3 si las declaraciones hacen el mismo trabajo de filtro.

Entonces, aquí está el código de la primera versión:

def kth_order_statistic(array, k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [x for x in array if x  pivot] if k  len(l) + len(m): return kth_order_statistic(r, k - len(l) - len(m)) else: return m[0] 

Y aquí el código de la 2da versión:

 def kth_order_statistic2(array, k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x  pivot: r.append(x) else: m.append(x) if k  len(l) + len(m): return kth_order_statistic2(r, k - len(l) - len(m)) else: return m[0] 

Salida de IPython para la primera versión:

 In [4]: %%timeit ...: A = range(100000) ...: shuffle(A) ...: k = randint(1, len(A)-1) ...: order_statisctic(A, k) ...: 10 loops, best of 3: 120 ms per loop 

Y para la 2da versión:

 In [5]: %%timeit ...: A = range(100000) ...: shuffle(A) ...: k = randint(1, len(A)-1) ...: kth_order_statistic2(A, k) ...: 10 loops, best of 3: 169 ms per loop 

Entonces, ¿por qué la primera versión es más rápida que la segunda? También hice la tercera versión que usaba la función de filtro () en lugar del generador de matriz y era más lenta que la segunda versión (tenía 218 ms por bucle)

Definamos las funciones que necesitaremos para responder a la pregunta y cronometrarlas:

 In [18]: def iter(): l = [x for x in range(100) if x > 10] ....: In [19]: %timeit iter() 100000 loops, best of 3: 7.92 µs per loop In [20]: def loop(): l = [] for x in range(100): if x > 10: l.append(x) ....: In [21]: %timeit loop() 10000 loops, best of 3: 20 µs per loop In [22]: def loop_fast(): l = [] for x in range(100): if x > 10: pass ....: In [23]: %timeit loop_fast() 100000 loops, best of 3: 4.69 µs per loop 

Podemos ver que los bucles for sin el comando de adición son tan rápidos como la lista de comprensión. De hecho, si observamos el código de bytes, podemos ver que en el caso de la lista de comprensión, python puede usar un comando de código de bytes integrado llamado LIST_APPEND en lugar de:

  • Cargar la lista: 40 LOAD_FAST
  • Carga el atributo: 43 LOAD_ATTRIBUTE
  • Llame a la función cargada: 49 CALL_FUNCTION
  • Descargar la lista (?): 52 POP_TOP

Como se puede ver en la salida de abajo, faltan los códigos de bytes anteriores con la lista de comprensión y con la función “loop_fast”. La comparación del tiempo en la función de los tres es claro que los responsables de la sincronización diferente de los tres métodos.

 In [27]: dis.dis(iter) 2 0 BUILD_LIST 0 3 LOAD_GLOBAL 0 (range) 6 LOAD_CONST 1 (1) 9 LOAD_CONST 2 (100) 12 CALL_FUNCTION 2 15 GET_ITER >> 16 FOR_ITER 24 (to 43) 19 STORE_FAST 0 (x) 22 LOAD_FAST 0 (x) 25 LOAD_CONST 2 (100) 28 COMPARE_OP 4 (>) 31 POP_JUMP_IF_FALSE 16 34 LOAD_FAST 0 (x) 37 LIST_APPEND 2 40 JUMP_ABSOLUTE 16 >> 43 STORE_FAST 1 (l) 46 LOAD_CONST 0 (None) 49 RETURN_VALUE In [28]: dis.dis(loop) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (1) 3 6 SETUP_LOOP 51 (to 60) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (1) 15 LOAD_CONST 2 (100) 18 CALL_FUNCTION 2 21 GET_ITER >> 22 FOR_ITER 34 (to 59) 25 STORE_FAST 1 (x) 4 28 LOAD_FAST 1 (x) 31 LOAD_CONST 3 (10) 34 COMPARE_OP 4 (>) 37 POP_JUMP_IF_FALSE 22 5 40 LOAD_FAST 0 (l) 43 LOAD_ATTR 1 (append) 46 LOAD_FAST 1 (x) 49 CALL_FUNCTION 1 52 POP_TOP 53 JUMP_ABSOLUTE 22 56 JUMP_ABSOLUTE 22 >> 59 POP_BLOCK >> 60 LOAD_CONST 0 (None) 63 RETURN_VALUE In [29]: dis.dis(loop_fast) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (1) 3 6 SETUP_LOOP 38 (to 47) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (1) 15 LOAD_CONST 2 (100) 18 CALL_FUNCTION 2 21 GET_ITER >> 22 FOR_ITER 21 (to 46) 25 STORE_FAST 1 (x) 4 28 LOAD_FAST 1 (x) 31 LOAD_CONST 3 (10) 34 COMPARE_OP 4 (>) 37 POP_JUMP_IF_FALSE 22 5 40 JUMP_ABSOLUTE 22 43 JUMP_ABSOLUTE 22 >> 46 POP_BLOCK >> 47 LOAD_CONST 0 (None) 50 RETURN_VALUE 

Usar simple for es más rápido que la list comprehesion . Es casi 2 veces más rápido. Compruebe los resultados a continuación:

Usando la list comprehension : 58 usec

 moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]" 10000 loops, best of 3: 58 usec per loop 

Utilizando for loop: 37.1 usec

 moin@moin-pc:~$ python -m timeit "for i in range(1000): i" 10000 loops, best of 3: 37.1 usec per loop 

Pero en su caso, for tomar más tiempo que la comprensión de la lista no porque TU for loop es lento. Pero debido a .append() está utilizando dentro del código.

Con append() en for loop`: 114 usec

 moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)" 10000 loops, best of 3: 114 usec per loop 

Lo que muestra claramente que es .append() que toma el doble del tiempo que toma el bucle .

Sin embargo, al storing the "list.append" in different variable : 69.3 usec

 moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)" 10000 loops, best of 3: 69.3 usec per loop 

Hay una gran mejora en el rendimiento en comparación con el último caso en las comparaciones anteriores, y el resultado es bastante comparable al de la list comprehension . Eso significa que, en lugar de llamar a my_list.append() cada vez, se puede mejorar el rendimiento almacenando la referencia de la función en otra variable, es decir, append_func = my_list.append y haciendo una llamada usando esa variable append_func(i) .

Lo que también demuestra que es más rápido llamar a la función de la clase almacenada en la variable en comparación con hacer la llamada de la función usando el objeto de la clase .

Gracias Stefan por traer el último caso en aviso.

Disipemos esa duda: la segunda versión es un poco más rápida: la comprensión de la lista es más rápida , sin embargo, dos matrices se repiten y la mayoría de los condicionales se descartan en una iteración.

 def kth_order_statistic1(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [x for x in array if x < pivot] m = [x for x in array if x == pivot] r = [x for x in array if x > pivot] if k <= len(l): return kth_order_statistic1(l, k) elif k > len(l) + len(m): return kth_order_statistic1(r, k - len(l) - len(m)) else: return m[0] def kth_order_statistic2(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x < pivot: l.append(x) elif x > pivot: r.append(x) else: m.append(x) if k <= len(l): return kth_order_statistic2(l, k) elif k > len(l) + len(m): return kth_order_statistic2(r, k - len(l) - len(m)) else: return m[0] def kth_order_statistic3(array,k): pivot = (array[0] + array[len(array) - 1]) // 2 l = [] m = [] r = [] for x in array: if x < pivot: l.append(x) for x in array: if x== pivot: m.append(x) for x in array: if x > pivot: r.append(x) if k <= len(l): return kth_order_statistic3(l, k) elif k > len(l) + len(m): return kth_order_statistic3(r, k - len(l) - len(m)) else: return m[0] import time import random if __name__ == '__main__': A = range(100000) random.shuffle(A) k = random.randint(1, len(A)-1) start_time = time.time() for x in range(1000) : kth_order_statistic1(A,k) print("--- %s seconds ---" % (time.time() - start_time)) start_time = time.time() for x in range(1000) : kth_order_statistic2(A,k) print("--- %s seconds ---" % (time.time() - start_time)) start_time = time.time() for x in range(1000) : kth_order_statistic3(A,k) print("--- %s seconds ---" % (time.time() - start_time)) 

 python : --- 25.8894710541 seconds --- --- 24.073086977 seconds --- --- 32.9823839664 seconds --- ipython --- 25.7450709343 seconds --- --- 22.7140650749 seconds --- --- 35.2958850861 seconds --- 

El tiempo puede variar de acuerdo con el sorteo aleatorio, pero las diferencias entre los tres son casi iguales.

La estructura algorítmica difiere y la estructura condicional debe incriminarse. la prueba para añadir en r y m puede ser descartada por la prueba anterior. Una comparación más estricta con respecto a un bucle for con append , y una comprensión de lista sería contra el seguimiento no óptimo

 for x in array: if x < pivot: l.append(x) for x in array: if x== pivot: m.append(x) for x in array: if x > pivot: r.append(x)