sumatoria - suma de numeros pares e impares en python

¿Por qué la resta es más rápida que la suma en Python?

Question

Estaba optimizando algunos códigos de Python y probé el siguiente experimento:

import time
start = time.clock()
x = 0
for i in range(10000000):
x += 1
end = time.clock()
print ''+='',end-start
start = time.clock()
x = 0
for i in range(10000000):
x -= -1
end = time.clock()
print ''-='',end-start

El segundo ciclo es confiablemente más rápido, desde un whisker hasta un 10%, dependiendo del sistema en el que lo ejecute. Intenté variar el orden de los bucles, el número de ejecuciones, etc., y parece que todavía funciona.

Desconocido,

for i in range(10000000, 0, -1):

(es decir, ejecutar el ciclo hacia atrás) es más rápido que

for i in range(10000000):

incluso cuando el contenido del ciclo es idéntico.

¿Qué ofrece, y hay una lección de programación más general aquí?

Answer 1

¿Hay una lección de programación más general aquí?

La lección de programación más general aquí es que la intuición es una guía deficiente al predecir el rendimiento en tiempo de ejecución del código de la computadora.

Uno puede razonar sobre la complejidad algorítmica, la hipótesis sobre las optimizaciones del compilador, estimar el rendimiento del caché, etc. Sin embargo, dado que estas cosas pueden interactuar de manera no trivial, la única manera de estar seguros de cuán rápido va a ser una determinada pieza de código es compararla en el entorno objetivo (como lo ha hecho legítimamente).

Answer 2

"El segundo ciclo es confiablemente más rápido ..."

Esa es tu explicación allí mismo. Vuelva a ordenar su secuencia de comandos para que la prueba de resta se cronometra primero, luego la adición, y de repente la adición se convierte en la operación más rápida de nuevo:

-= 3.05
+= 2.84

Obviamente, algo le sucede a la segunda mitad del guión que lo hace más rápido. Mi suposición es que la primera llamada a range() es más lenta porque python necesita asignar suficiente memoria para una lista tan larga, pero es capaz de reutilizar esa memoria para la segunda llamada a range() :

import time
start = time.clock()
x = range(10000000)
end = time.clock()
del x
print ''first range()'',end-start
start = time.clock()
x = range(10000000)
end = time.clock()
print ''second range()'',end-start

Unas pocas ejecuciones de este script muestran que el tiempo extra que se necesita para el primer range() representa casi toda la diferencia de tiempo entre ''+ ='' y ''- ='' que se ve arriba:

first range() 0.4
second range() 0.23

Answer 3

Con Python 2.5, el mayor problema aquí es usar range, que asignará una lista tan grande para iterar sobre ella. Al usar xrange, lo que ocurra en segundo lugar es un poco más rápido para mí. (No estoy seguro si el rango se ha convertido en generador en Python 3)

Answer 4

Creo que la "lección de programación general" es que es realmente difícil de predecir, solo mirando el código fuente, qué secuencia de enunciados será la más rápida. Los programadores en todos los niveles con frecuencia se ven atrapados por este tipo de optimización "intuitiva". Lo que crees que sabes puede no ser necesariamente cierto.

Simplemente no hay sustituto para medir realmente el rendimiento de su programa. Felicitaciones por hacerlo; responder por qué, sin duda, es necesario profundizar en la implementación de Python, en este caso.

Con lenguajes compilados en bytes como Java, Python y .NET, ni siquiera es suficiente para medir el rendimiento en una sola máquina. Las diferencias entre las versiones de VM, las implementaciones de traducción de códigos nativas, las optimizaciones específicas de la CPU, etc. harán que este tipo de preguntas sea aún más difícil de responder.

Answer 5

El ciclo de ejecución hacia atrás es más rápido porque a la computadora le resulta más fácil comparar si un número es igual a 0.

Answer 6

Eso sería notable, así que he evaluado a fondo su código y también configuré el experimento como lo encontraría más correcto (todas las declaraciones y llamadas a funciones fuera del ciclo). Ambas versiones he corrido cinco veces.

• Ejecutar su código valida sus afirmaciones: - = toma constantemente menos tiempo; 3.6% en promedio
• Ejecutar mi código, sin embargo, contradice el resultado de su experimento: + = toma en promedio (no siempre) 0.5% menos de tiempo.

Para mostrar todos los resultados, he puesto diagramas en línea:

• Su evaluación: http://bayimg.com/kadAeaAcN
• Mi evaluación: http://bayimg.com/KadaAaAcN

Entonces, llegué a la conclusión de que su experimento tiene un sesgo, y es significativo.

Finalmente aquí está mi código:

import time
addtimes = [0.] * 100
subtracttimes = [0.] * 100
range100 = range(100)
range10000000 = range(10000000)
j = 0
i = 0
x = 0
start = 0.
for j in range100:
start = time.clock()
x = 0
for i in range10000000:
x += 1
addtimes[j] = time.clock() - start
for j in range100:
start = time.clock()
x = 0
for i in range10000000:
x -= -1
subtracttimes[j] = time.clock() - start
print ''+='', sum(addtimes)
print ''-='', sum(subtracttimes)

Answer 7

Puedo reproducir esto en mi Q6600 (Python 2.6.2); aumentando el rango a 100000000:

(''+='', 11.370000000000001)
(''-='', 10.769999999999998)

Primero, algunas observaciones:

• Esto es 5% para una operación trivial. Eso es significativo.
• La velocidad de los códigos de operación nativos de suma y resta es irrelevante. Está en el piso de ruido, completamente eclipsado por la evaluación de bytecode. Eso es hablar de una o dos instrucciones nativas de miles.
• El bytecode genera exactamente el mismo número de instrucciones; la única diferencia es INPLACE_ADD contra INPLACE_SUBTRACT y +1 contra -1.

Mirando la fuente de Python, puedo adivinar. Esto se maneja en ceval.c, en PyEval_EvalFrameEx . INPLACE_ADD tiene un bloque de código extra significativo para manejar la concatenación de cadenas. Ese bloque no existe en INPLACE_SUBTRACT , ya que no puedes restar cadenas. Eso significa que INPLACE_ADD contiene más código nativo. Dependiendo (¡en gran medida!) De cómo el compilador genera el código, este código adicional puede estar en línea con el resto del código INPLACE_ADD, lo que significa que las adiciones pueden afectar al caché de instrucciones más que a la resta. Esto podría estar causando hits de caché L2 adicionales, lo que podría causar una diferencia de rendimiento significativa.

Esto depende mucho del sistema en el que se encuentre (diferentes procesadores tienen diferentes cantidades de arquitecturas de caché y caché), el compilador en uso, incluida la versión particular y las opciones de compilación (diferentes compiladores decidirán de forma diferente qué bits de código están en el crítico ruta de acceso, que determina cómo se agrupa el código de ensamblado), y así sucesivamente.

Además, la diferencia se invierte en Python 3.0.1 (+: 15.66, -: 16.71); sin duda, esta función crítica ha cambiado mucho.

Answer 8

Siempre es una buena idea hacer una pregunta para decir qué plataforma y qué versión de Python está usando. A veces no importa. Este NO es uno de esos momentos:

1. time.clock() es apropiado solo en Windows. Bote su propio código de medición y use -m timeit como se demuestra en la respuesta del pixelbeat.

2. El range() Python 2.X range() construye una lista. Si está utilizando Python 2.x, reemplace el range con xrange y vea qué sucede.

3. El int Python 3.X es long de Python2.X

Answer 9

Tu experimento es defectuoso La forma en que debe diseñarse este experimento es escribir 2 programas diferentes: 1 para la suma, 1 para la resta. Deben ser exactamente iguales y ejecutarse en las mismas condiciones con los datos que se archivan. Entonces necesita promediar las carreras (al menos varios miles), pero necesitaría un estadístico para decirle un número apropiado.

Si desea analizar diferentes métodos de suma, resta y bucle, una vez más, cada uno de ellos debe ser un programa separado.

Puede haber un error experimental debido al calor del procesador y a otras actividades de la CPU, por lo que ejecutaría las ejecuciones en una variedad de patrones ...

Answer 10

$ python -m timeit -s "x=0" "x+=1"
10000000 loops, best of 3: 0.151 usec per loop
$ python -m timeit -s "x=0" "x-=-1"
10000000 loops, best of 3: 0.154 usec per loop

Parece que tienes algún sesgo de medición