La respuesta a esta pregunta solo se refiere a cuánto tiempo lleva la suma frente a la multiplicación para lenguajes y arquitecturas específicas. Para la diferencia teórica y asintótica entre las dos operaciones, tenga en cuenta que la suma es [matemática] O (n) [/ matemática], y lea más sobre la multiplicación aquí:
Dados dos enteros de n bits, ¿cuál es la complejidad asintótica mínima, en términos de n, para determinar el producto?
La cantidad de tiempo que toma depende en gran medida del idioma, la CPU que está utilizando, el estado de la tubería y otros factores, pero trataré de describir algunas generalizaciones con la suma frente a la multiplicación.
- Cuando las computadoras se desarrollaron por primera vez, ¿qué pensaba el público de ellas?
- ¿Qué es la informática?
- Cómo determinar el tamaño de un archivo de video
- ¿Es el personaje la unidad básica de la jerarquía de almacenamiento de datos?
- ¿Cuáles son las puertas lógicas más comunes en las computadoras?
do
En C, todo se reduce en la medida de lo posible en las instrucciones reales de la máquina, en las que estamos comparando la cantidad de tiempo que le toma al chip Intel real ejecutar add vs imul . De acuerdo con el Manual de referencia de optimización de Intel [1], la latencia de imul (la cantidad de tiempo que tarda la instrucción en entrar y emitir un resultado) puede tomar entre 3 y 15 veces más ciclos de CPU que la latencia de una instrucción de add , dependiendo del chip. Recuerde también que los valores que multiplicamos están limitados al tamaño de los registros reales de la CPU, en lugar de longitudes arbitrarias.
Pitón
En Python, ahora estamos comparando la cantidad de tiempo que lleva ejecutar una instrucción BINARY_ADD versus una operación BINARY_MULTIPLY en el BINARY_MULTIPLY de Python. Comparando la fuente de ambos [2], vemos que el código en el intérprete para la multiplicación es:
caso BINARY_MULTIPLY:
w = POP ();
v = TOP ();
x = PyNumber_Multiply (v, w);
Py_DECREF (v);
Py_DECREF (w);
SET_TOP (x);
if (x! = NULL) continuar;
descanso;
El código para la adición, sin embargo:
caso BINARY_ADD:
w = POP ();
v = TOP ();
if (PyInt_CheckExact (v) && PyInt_CheckExact (w)) {
/ * EN LÍNEA: int + int * /
registro largo a, b, i;
a = PyInt_AS_LONG (v);
b = PyInt_AS_LONG (w);
/ * emitir para evitar comportamientos indefinidos
en desbordamiento * /
i = (largo) ((sin signo largo) a + b);
si ((i ^ a) <0 && (i ^ b) <0)
goto slow_add;
x = PyInt_FromLong (i);
}
más si (PyString_CheckExact (v) &&
PyString_CheckExact (w)) {
x = cadena_concatenada (v, w, f, next_instr);
/ * string_concatenate consumió la referencia a v * /
goto skip_decref_vx;
}
más {
slow_add:
x = PyNumber_Add (v, w);
}
Py_DECREF (v);
skip_decref_vx:
Py_DECREF (w);
SET_TOP (x);
if (x! = NULL) continuar;
descanso;
Bien, eso probablemente no tiene sentido sin ningún contexto. Básicamente, la diferencia es que si los dos enteros que está agregando caben dentro de un long , entonces CPython cortocircuitará cualquier llamada de función y simplemente devolverá un nuevo objeto que representa PyInt_FromLong(a + b) . La cantidad de tiempo que lleva esto es más o menos la suma de a + b quizás la asignación del objeto número.
Para la multiplicación, y además de agregar dos enteros que desbordarán el long , CPython llamará a una función auxiliar PyNumber_Add o PyNumber_Multiply . No he profundizado mucho en el código, pero imagino que ambos son más lentos que ejecutar PyInt_FromLong , que probablemente solo devuelva un objeto singleton.
Entonces, ¿cuáles son los resultados finales, como en cuánto tiempo lleva la suma versus la multiplicación? Probé esto en mi Macbook:
>>> timeit.timeit ('a * b', 'a = 1000; b = 2000')
0.090944051742553711
>>> timeit.timeit ('a + b', 'a = 1000; b = 2000')
0.064960002899169922
Qué significa todo esto? Básicamente, en su mayor parte, la adición de CPython es algo más rápida que la multiplicación: cuánto más rápido depende de mucho, mucho más que comparar la multiplicación y la adición con C. Pero puede estar seguro de que los mantenedores de CPython tuvieron en cuenta para optimizar los casos más comunes de suma de enteros lo mejor que pudieron.
[1] http://www.intel.com/products/pr…
[2] http://www.python.org/download/r…
