¿Por qué el bucle sobre range () en Python es más rápido que usar un bucle while?

81

El otro día estaba haciendo una evaluación comparativa de Python y encontré algo interesante. A continuación se muestran dos bucles que hacen más o menos lo mismo. El ciclo 1 tarda aproximadamente el doble que el ciclo 2 en ejecutarse.

Bucle 1:

int i = 0
while i < 100000000:
  i += 1

Bucle 2:

for n in range(0,100000000):
  pass

¿Por qué el primer bucle es mucho más lento? Sé que es un ejemplo trivial, pero ha despertado mi interés. ¿Hay algo especial en la función range () que la hace más eficiente que incrementar una variable de la misma manera?

python performance benchmarking A. Dorton
fuente

Respuestas:

159

vea el desmontaje del código de bytes de Python, puede obtener una idea más concreta

usar while loop:

1           0 LOAD_CONST               0 (0)
            3 STORE_NAME               0 (i)

2           6 SETUP_LOOP              28 (to 37)
      >>    9 LOAD_NAME                0 (i)              # <-
           12 LOAD_CONST               1 (100000000)      # <-
           15 COMPARE_OP               0 (<)              # <-
           18 JUMP_IF_FALSE           14 (to 35)          # <-
           21 POP_TOP                                     # <-

3          22 LOAD_NAME                0 (i)              # <-
           25 LOAD_CONST               2 (1)              # <-
           28 INPLACE_ADD                                 # <-
           29 STORE_NAME               0 (i)              # <-
           32 JUMP_ABSOLUTE            9                  # <-
      >>   35 POP_TOP
           36 POP_BLOCK

El cuerpo del bucle tiene 10 op

rango de uso:

1           0 SETUP_LOOP              23 (to 26)
            3 LOAD_NAME                0 (range)
            6 LOAD_CONST               0 (0)
            9 LOAD_CONST               1 (100000000)
           12 CALL_FUNCTION            2
           15 GET_ITER
      >>   16 FOR_ITER                 6 (to 25)        # <-
           19 STORE_NAME               1 (n)            # <-

2          22 JUMP_ABSOLUTE           16                # <-
      >>   25 POP_BLOCK
      >>   26 LOAD_CONST               2 (None)
           29 RETURN_VALUE

El cuerpo del bucle tiene 3 op

El tiempo para ejecutar el código C es mucho más corto que el del intepretor y puede ignorarse.

kcwu
fuente
2
En realidad, el cuerpo del lazo en el primer desmontaje tiene 10 operaciones (el salto de la posición 32 a la 9). En la implementación actual de CPython, la interpretación de cada bytecode da como resultado con una probabilidad bastante alta un costoso error de predicción de rama indirecta en la CPU (el salto a la implementación del siguiente bytecode). Esto es una consecuencia de la implementación actual de CPython, los JIT que se implementan mediante el trago sin carga, PyPy y otros probablemente perderán esa sobrecarga. Los mejores de ellos también podrán realizar la especialización de tipos para acelerar un orden de magnitud.
Ants Aasma
5
utilice el módulo "dis". Defina su código en una función, luego llame a dis.disco (func .__ code__)
kcwu
¿Sería correcto decir entonces que en un nivel superior, un whilebucle tiene que hacer una comparación en cada iteración?
davidhood2
35

range()se implementa en C, mientras que i += 1se interpreta.

El uso xrange()podría hacerlo aún más rápido para grandes cantidades. Comenzar con Python 3.0 range()es el mismo que antes xrange().

Georg Schölly
fuente
15

Debe decirse que hay mucha creación y destrucción de objetos con el ciclo while.

i += 1

es lo mismo que:

i = i + 1

Pero debido a que las entradas de Python son inmutables, no modifica el objeto existente; más bien crea un objeto nuevo con un nuevo valor. Es básicamente:

i = new int(i + 1)   # Using C++ or Java-ish syntax

El recolector de basura también tendrá que hacer una gran cantidad de limpieza. "La creación de objetos es cara".

Pedro
fuente
4

Porque está ejecutando con más frecuencia código escrito en C en el intérprete. es decir, i + = 1 está en Python, por lo que es lento (comparativamente), mientras que range (0, ...) es una llamada de C, el ciclo for se ejecutará principalmente en C también.

John Montgomery
fuente
1

La mayoría de las llamadas a métodos integradas de Python se ejecutan como código C. El código que hay que interpretar es mucho más lento. En términos de eficiencia de la memoria y velocidad de ejecución, la diferencia es gigantesca. Los componentes internos de Python se han optimizado al extremo, y es mejor aprovechar esas optimizaciones.

Oh Dios mio
fuente
0

Creo que la respuesta aquí es un poco más sutil de lo que sugieren las otras respuestas, aunque la esencia es correcta: el ciclo for es más rápido porque ocurren más operaciones en C y menos en Python .

Más específicamente, en el caso del bucle for, suceden dos cosas en C que en el bucle while se manejan en Python:

  1. En el ciclo while, la comparación i < 100000000se ejecuta en Python, mientras que en el ciclo for, el trabajo se pasa al iterador de range(100000000), que internamente realiza la iteración (y, por lo tanto, la verificación de límites) en C.

  2. En el ciclo while, la actualización del ciclo i += 1ocurre en Python, mientras que en el ciclo for nuevamente, el iterador de range(100000000), escrito en C, hace el i+=1(o ++i).

Podemos ver que es una combinación de ambas cosas lo que hace que el bucle for sea más rápido al agregarlos manualmente para ver la diferencia.

import timeit

N = 100000000


def while_loop():
    i = 0
    while i < N:
        i += 1


def for_loop_pure():
    for i in range(N):
        pass


def for_loop_with_increment():
    for i in range(N):
        i += 1


def for_loop_with_test():
    for i in range(N):
        if i < N: pass


def for_loop_with_increment_and_test():
    for i in range(N):
        if i < N: pass
        i += 1


def main():
    print('while loop\t\t', timeit.timeit(while_loop, number=1))
    print('for pure\t\t', timeit.timeit(for_loop_pure, number=1))
    print('for inc\t\t\t', timeit.timeit(for_loop_with_increment, number=1))
    print('for test\t\t', timeit.timeit(for_loop_with_test, number=1))
    print('for inc+test\t', timeit.timeit(for_loop_with_increment_and_test, number=1))


if __name__ == '__main__':
    main()

Probé esto tanto con el número 100000000 como una constante literal como con una variable, Ncomo sería más típico.

# inline constant N
while loop      3.5131139
for pure        1.3211338000000001
for inc         3.5477727000000003
for test        2.5209639
for inc+test    4.697028999999999

# variable N
while loop      4.1298240999999996
for pure        1.3526357999999998
for inc         3.6060175
for test        3.1093069
for inc+test    5.4753364

Como puede ver, en ambos casos, el whiletiempo se acerca mucho a la diferencia de for inc+testy for pure. Tenga en cuenta también que en el caso en que usamos la Nvariable, whiletiene una desaceleración adicional para buscar repetidamente el valor de N, pero forno lo hace.

Es realmente una locura que modificaciones tan triviales puedan resultar en una aceleración de código 3x , pero eso es Python para usted. Y ni siquiera me hagas comenzar cuando puedes usar un builtin sobre un bucle en absoluto ...

mCoding
fuente