Cual es la manera más rápida para obtener el valor absoluto de un número

https://stackoverflow.com/questions/664852

21-08-2019
|

Pregunta

Que es la forma más rápida para implementar una operación que devuelve el valor absoluto de un número?

x=root(x²)

if !isPositive(x):
    x=x*(-1)

En realidad, esta pregunta puede ser traducido como, ¿qué tan rápido es un if (y por qué por favor).

De mi universidad, la programación de los profesores siempre me dijeron que para evitar ifs por que son extremadamente lentos, pero siempre me olvidó preguntar cómo es lento y por qué.¿Alguien de aquí sabe?

Solución

Los condicionales son más lentas que las operaciones aritméticas de fricción, pero mucho, mucho más rápido que algo tan tonto como el cálculo de la raíz cuadrada.

Las reglas generales de mis días de montaje:

Entero o op bit a bit: 1 ciclo
punto flotante add / sub / mul: 4 ciclos
coma flotante div: ~ 30 ciclos
punto flotante exponenciación: ~ 200 ciclos
coma flotante sqrt: ~ 60 ciclos, dependiendo de la aplicación
rama condicional: avg. 10 ciclos, mejor si bien pronosticado, mucho peor si mispredicted

Otros consejos

Hay un gran truco para calcular el valor absoluto de un número entero 2s-complemento sin necesidad de utilizar una sentencia if. Según la teoría, si el valor es negativo que desee alternar los bits y agregue, si no se desea pasar a través de los bits como está. Un XOR 1 pasa a alternar A y A XOR 0 pasa a dejar un intacta. Por lo que desea hacer algo como esto:

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

En principio, puede hacerlo en tan sólo tres instrucciones de montaje (sin una rama). Y que le gustaría pensar que la función abs () que se obtiene con math.h lo hace de manera óptima.

No hay ramas == mejor rendimiento. Contrariamente a @ respuesta de paxdiablo anteriormente, esto realmente importa en tuberías profundas donde los más sucursales que tiene en su código, lo más probable es que tenga su predictor de saltos se equivocan y tienen que hacer retroceder, etc. Si evita ramificación donde posibles, las cosas van a seguir moviéndose junto a todo gas en su núcleo:.)

Uf, sus profesores en realidad se lo ha dicho? La regla de la mayoría de la gente sigue es hacer que su código legible primero, y luego ajustar los problemas de rendimiento después de que han demostrado ser realmente problemas. 99,999% de las veces que nunca se va a ver un problema de rendimiento, porque que utilizó una copa de más si las declaraciones. Knuth dijo mejor , "optimización prematura es la raíz de todo mal".

El cálculo de la raíz cuadrada es probablemente una de las peores cosas que podría hacer, ya que es muy lento.Por lo general, hay una función de biblioteca para hacerlo;algo como las Matemáticas.Abs().Multiplicamos por -1 también es innecesaria;acabo de volver de -x.Así que una buena solución sería la siguiente.

(x >= 0) ? x : -x

El compilador probablemente optimizar esta a una sola instrucciones.Las condiciones pueden ser muy caros en los procesadores modernos, debido a la larga la ejecución de tuberías -los cálculos deben ser arrojadas a la basura si una rama se misspredicted y el procesador comenzó a ejecutar las instrucciones de un código equivocado de ruta.Pero debido a la mencionada optimización del compilador no necesita de atención en este caso.

Para completar, aquí es una manera de hacerlo por IEEE flota sobre los sistemas x86 en C ++:

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;

El if variante casi seguro que será cegador rápido en comparación con la raíz cuadrada, ya que normalmente se traduce en una instrucción de salto condicional a nivel de código máquina (tras la evaluación de la expresión, la cual puede ser compleja, pero no en este caso, ya que es una simple comprobación por menos de 0).

Tomando la raíz cuadrada de un número es probable que sea mucho más lento (el método de Newton, por ejemplo, podría utilizar muchos muchos <=> declaraciones a nivel de código máquina).

La fuente probable de confusión es el hecho de que <=> invariablemente conduce a cambiar el puntero de instrucción de una manera no secuencial. Esto puede ralentizar procesadores que las instrucciones de búsqueda anticipada en una tubería ya que tienen que volver a poblar la tubería cuando la dirección cambia de forma inesperada.

Sin embargo, el costo de esa sería minúscula comparada con la realización de una operación de raíz cuadrada en lugar de un simple registro de entrada y cambiar signo.

¿Cuál es la manera más rápida para obtener el valor absoluto de un número

Creo que la respuesta "correcta" no es en realidad aquí. La forma más rápida para obtener el número absoluto es probablemente usar el procesador Intel intrínseca. Ver https://software.intel.com/sites/landingpage/IntrinsicsGuide/ buscar '' vpabs (u otra intrínsecas que hace el trabajo de la CPU). Estoy bastante seguro de que va a vencer todas las otras soluciones aquí.

Si no te gusta lo intrínseco (o no se pueden utilizar o ...), es posible que desee comprobar si el compilador es lo suficientemente inteligente como para saber si una llamada a 'valor absoluto nativa' (std::abs en C ++ o Math.Abs(x) en C #) cambiará automágicamente a la intrínseca - básicamente, que implica mirar el código desensamblado (compilado). Si estás en un JIT, asegúrese de que las optimizaciones JIT no están deshabilitados.

Si eso tampoco te da las instrucciones optimizadas, puede utilizar el método descrito aquí: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs .

La operación de módulo se utiliza para encontrar un resto, que quiere decir valor absoluto. He modificado la cuestión, ya que debería ser si! Pos (x), entonces x = x * -1. (No faltaba)

Yo no preocuparse por la eficiencia de una sentencia if. En lugar de centrarse en la legibilidad del código. Si se identifica que hay un problema de eficiencia, a continuación, centrarse en el perfil de su código para encontrar verdaderos cuellos de botella.

Si desea mantener un ojo para la eficiencia al tiempo que el código, sólo debe preocuparse por la complejidad de orden O de sus algoritmos.

Si los estados son muy eficientes, que evalúa lo que sea expresión y luego simplemente cambia el contador de programa basado en esa condición. Las tiendas de contador de programa la dirección de la siguiente instrucción a ejecutar.

Mulitplication por -1 y comprobando si un valor es mayor que 0, tanto se puede reducir a una sola instrucción de montaje.

Encontrar la raíz de un número y cuadrar ese número primero es, sin duda más operaciones que el caso con una negación.

El tiempo necesario para hacer una raíz cuadrada es mucho mayor que el tiempo necesario para hacer una condicional. Si se le ha enseñado a evitar condicionales porque son lentos, a continuación, se le ha informado mal. Son un buen negocio más lento que las operaciones triviales como sumar o restar números enteros o desplazamiento de bits - que es por qué se desenrolla bucles pueden ser de beneficio sólo si se está haciendo este tipo de operaciones triviales. Pero en el gran esquema de las cosas son condicionales bueno y rápido, no está mal y lento. Para hacer algo tan complicado como llamar a una función o calcular una raíz cuadrada para evitar una sentencia condicional es una locura.

Además, en lugar de (x = x * -1) por qué no hacer (x = 0 - x)? Tal vez el compilador optimizar ellos el mismo, pero no es el segundo más simple de todos modos?

¿Está utilizando el montaje 8086? ; -)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

(flagrante robado )

Si simplemente comparando los valores absolutos de dos números (por ejemplo, no es necesario el valor absoluto de ya sea después de la comparación) a continuación, sólo cuadrar ambos valores para hacer tanto positivos (quitar el signo de cada valor), el más grande cuadrado será mayor que el cuadrado más pequeño.

Lo que es más rápido es muy dependiente de lo compilador y lo que usted está apuntando CPU. En la mayoría de las CPU y todos los compiladores x = (x> = 0)? x: -x; es la forma más rápida para obtener valor absoluto, pero, de hecho, a menudo funciones estándar ya ofrecen esta solución (por ejemplo FABS ()). Se compila en comparar seguido de instrucción condicional de asignación (cmov), no en salto condicional. Algunas plataformas carecen de esa instrucción sin embargo. Aunque, Intel (pero no Microsoft o GCC) compilador convertir automáticamente si () en la asignación condicional, e incluso podría intentar optimizar los ciclos (si es posible).

ramificación código en general es más lento que la asignación condicional, si CPU utiliza predicción estadística. Si () podría ser más lenta en promedio, si la operación se repite varias veces y el resultado de la condición está en constante cambio. CPU como Intel, comenzarían a calcular ambos ramas y se reduciría la inválido, en caso de grandes si () organismos o gran número de ciclos que podrían ser críticos.

SQR () y sqrt () en las CPU Intel modernos son solo una función de instrucción y no son lentos, pero son imprecisos, y los registros de carga llevaría tiempo también.

pregunta relacionada:? Por qué es una instrucción de salto CPU lenta

Lo más probable, profesor quería estudiante para hacer la investigación sobre este asunto, que es semi-provocativa pregunta \ tarea que hacer sólo el bien, si el estudiante aprendería pensar de manera independiente y buscar fuentes adicionales.

Me estoy haciendo un poco de programación gráficos retro en C para 8088/8086 y llamando abs() es mucho tiempo por lo que he reemplazado con:

/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
    i = ~i + 1;
}

La razón de que esto es más rápido, ya que es esencialmente negocia un CALL en el montaje para un JNE. Llamar a un método cambia un par de registros, empuja varios más, empuja argumentos en la pila, y se puede vaciar la cola de captación previa. Además de estas acciones necesitan ser revertido al final de la función y todo esto es muy caro a la CPU.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow