algorithm - sacar - valor absoluto ejemplos
¿Cuál es la forma más rápida de obtener el valor absoluto de un número? (13)
¿Cuál es la forma más rápida de implementar una operación que devuelve el valor absoluto de un número?
x=root(x²)
o
if !isPositive(x):
x=x*(-1)
En realidad, esta pregunta se puede traducir como, qué tan rápido es un if (y por qué por favor).
Mis profesores de programación universitaria siempre me dijeron que lo evitara porque son extremadamente lentos, pero siempre olvidé preguntarme qué tan lento y por qué. ¿Alguien aquí lo sabe?
¿Cuál es la forma más rápida de obtener el valor absoluto de un número?
Creo que la respuesta "correcta" no está aquí en realidad. La manera más rápida de obtener el número absoluto es probablemente usar Intel Intrinsic. Consulte https://software.intel.com/sites/landingpage/IntrinsicsGuide/ y busque ''vpabs'' (u otro intrínseco que haga el trabajo para su CPU). Estoy bastante seguro de que superará a todas las otras soluciones aquí.
Si no le gustan los intrínsecos (o no puede usarlos o ...), es posible que desee comprobar si el compilador es lo suficientemente inteligente como para averiguar si una llamada a ''valor absoluto nativo'' ( std::abs en C ++ o Math.Abs(x) en C #) cambiará automágicamente a lo intrínseco, básicamente eso implica mirar el código desensamblado (compilado). Si está en un JIT, asegúrese de que las optimizaciones de JIT no estén deshabilitadas.
Si eso tampoco le da las instrucciones optimizadas, puede usar el método descrito aquí: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs .
¿Estás usando el ensamblaje 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
(Robo flagrante)
Calcular la raíz cuadrada es probablemente una de las peores cosas que podrías hacer porque es muy lenta. Usualmente hay una función de biblioteca para hacer esto; algo así como Math.Abs (). Multiplicar con -1 también es innecesario; solo devuelve -x. Entonces una buena solución sería la siguiente.
(x >= 0) ? x : -x
El compilador probablemente optimizará esto en una sola instrucción. Las condiciones pueden ser bastante costosas en los procesadores modernos debido a la larga ejecución de las tuberías: los cálculos deben descartarse si una derivación se omitió y el procesador comenzó a ejecutar las instrucciones desde la ruta de código incorrecta. Pero debido a la optimización del compilador mencionada, no es necesario que se preocupe en este caso.
El tiempo necesario para hacer una raíz cuadrada es mucho mayor que el tiempo necesario para hacer un condicional. Si te han enseñado a evitar condicionales porque son lentos, entonces has sido mal informado. Son mucho más lentas que las operaciones triviales, como sumar o restar enteros o cambios de bit, por lo que los bucles de desenrollado pueden ser beneficiosos solo si se realizan operaciones tan triviales. Pero en el gran esquema de las cosas, los condicionales son buenos y rápidos, no malos y lentos. Hacer algo tan complicado como llamar a una función o calcular una raíz cuadrada para evitar una declaración condicional es una locura.
Además, en lugar de (x = x * -1) ¿por qué no hacer (x = 0 - x)? Quizás el compilador los optimice de la misma manera, ¿pero no es el segundo más simple de todos modos?
Estoy haciendo algo de programación de gráficos retro en C para 8088/8086 y llamar a abs() consume mucho tiempo, así que lo he reemplazado por:
/* assuming ''i'' is int; this WILL NOT WORK on floating point */
if (i < 0) {
i = ~i + 1;
}
La razón por la que esto es más rápido es porque esencialmente intercambia una CALL en el ensamble de un JNE . Llamar a un método cambia un par de registros, empuja varios más, empuja los argumentos a la pila y puede vaciar la cola de captación previa. Además, estas acciones deben invertirse al final de la función y todo esto es muy costoso para la CPU.
Hay un gran truco para calcular el valor absoluto de un entero complementario de 2s sin usar una instrucción if. La teoría dice que si el valor es negativo, quiere alternar los bits y agregar uno; de lo contrario, quiere pasar los bits tal como están. Un XOR 1 pasa a activar A y A XOR 0 pasa a dejar intacto A. Entonces quieres 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 solo tres instrucciones de ensamblaje (sin una rama). Y le gustaría pensar que la función abs () que obtiene con math.h lo hace de manera óptima.
Sin ramas == mejor rendimiento. Contrariamente a la respuesta de @ paxdiablo anterior, esto realmente importa en las tuberías profundas donde cuantas más ramas tenga en su código, más probabilidades tendrá de que su pronosticador de rama se equivoque y tenga que retroceder, etc. Si evita la bifurcación donde posible, las cosas seguirán moviéndose a todo gas en tu núcleo :).
La operación de módulo se usa para encontrar un resto, significa valor absoluto. Modifiqué la pregunta porque debería ser si! Pos (x) luego x = x * -1. (no faltaba)
No me preocuparía la eficacia de una declaración if. En cambio, concéntrese en la legibilidad de su código. Si identifica que hay un problema de eficiencia, entonces concéntrese en perfilar su código para encontrar cuellos de botella reales.
Si desea estar atento a la eficacia mientras codifica, solo debería preocuparse por la gran complejidad de sus algoritmos.
Si las declaraciones son muy eficientes, evalúa cualquier expresión y luego simplemente cambia el contador del programa en función de esa condición. El contador del programa almacena la dirección de la próxima instrucción que se ejecutará.
La multiplicación por -1 y la comprobación de si un valor es mayor que 0 ambos pueden reducirse a una sola instrucción de ensamblaje.
Encontrar la raíz de un número y cuadrar ese número primero es definitivamente más operaciones que el si con una negación.
La variante if será casi deslumbrantemente rápida en comparación con la raíz cuadrada, ya que normalmente se traduce en una instrucción de salto condicional en el nivel de código de máquina (después de la evaluación de la expresión, que puede ser compleja, pero no en este caso ya que es comprobación simple por menos de 0).
Tomar la raíz cuadrada de un número es probable que sea mucho más lento (el método de Newton, por ejemplo, usaría muchos muchos enunciados if a nivel de código de máquina).
La posible fuente de confusión es el hecho de que invariablemente conduzca a cambiar el puntero de instrucción de una manera no secuencial. Esto puede ralentizar a los procesadores que preseleccionan las instrucciones en una canalización ya que tienen que volver a llenar la interconexión cuando la dirección cambia inesperadamente.
Sin embargo, el costo de eso sería minúsculo en comparación con la realización de una operación de raíz cuadrada en comparación con un simple check-and-negate.
Lo que es más rápido depende mucho del compilador y de la CPU a la que se dirige. En la mayoría de las CPU y todos los compiladores x = (x> = 0)? x: -x; es la forma más rápida de obtener un valor absoluto, pero de hecho, a menudo las funciones estándar ya ofrecen esta solución (por ejemplo, fabs ()). Se compila en comparación seguido de instrucción de asignación condicional (CMOV), no en salto condicional. Sin embargo, algunas plataformas carecen de esa instrucción. Aunque, el compilador Intel (pero no Microsoft o GCC) convertiría automáticamente if () en una asignación condicional, e incluso trataría de optimizar ciclos (si es posible).
El código de ramificación en general es más lento que la asignación condicional, si la CPU usa predicción estadística. if () podría ser más lento en promedio si la operación se repite varias veces y el resultado de la condición cambia constantemente. CPUs como Intel, comenzarían a calcular ambas ramas, y dejarían caer la inválida, en el caso de cuerpos if () grandes o una gran cantidad de ciclos que podrían ser críticos.
sqr () y sqrt () en las CPU Intel modernas son instrucciones integradas individuales y no son lentas, pero son imprecisas, y cargar registros también llevaría tiempo.
Pregunta relacionada: ¿Por qué es lenta la instrucción de una rama de CPU?
Lo más probable es que el profesor quisiera que el alumno investigue sobre este tema, es una pregunta semi provocadora que sería lo único bueno, si el alumno aprende a pensar de forma independiente y busca fuentes adicionales.
Los condicionales son más lentos que las operaciones aritméticas simples, pero mucho, mucho más rápido que algo tan tonto como calcular la raíz cuadrada.
Reglas generales de mis días de asamblea:
- Entero o bit a bit op: 1 ciclo
- Punto flotante add / sub / mul: 4 ciclos
- Floating-point div: ~ 30 ciclos
- Exponenciación de coma flotante: ~ 200 ciclos
- Sqrt punto flotante: ~ 60 ciclos dependiendo de la implementación
- Rama condicional: avg. 10 ciclos, mejor si está bien predicho, mucho peor si se predice mal
Para completar, esta es una forma de hacerlo para flotantes IEEE en sistemas x86 en C ++:
*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;
Si simplemente está comparando los valores absolutos de dos números (p. Ej., No necesita el valor absoluto de ninguno después de la comparación) simplemente cuadre ambos valores para que ambos sean positivos (elimine el signo de cada valor), el cuadrado más grande será mayor que el cuadrado más pequeño.
Uf, tus profesores realmente te dijeron eso? La regla que sigue la mayoría de la gente es hacer que su código sea legible primero, y luego ajustar cualquier problema de rendimiento después de que se demuestre que realmente son problemas. 99.999% de las veces nunca verá un problema de rendimiento porque usó demasiadas declaraciones if. Knuth lo dijo mejor , "la optimización prematura es la raíz de todo mal".