¿Es una buena práctica reemplazar la división con la multiplicación cuando sea posible?

73

Cada vez que necesito división, por ejemplo, comprobación de condición, me gustaría refactorizar la expresión de división en multiplicación, por ejemplo:

Versión original:

if(newValue / oldValue >= SOME_CONSTANT)

Nueva versión:

if(newValue >= oldValue * SOME_CONSTANT)

Porque creo que puede evitar:

  1. División por cero

  2. Desbordarse cuando oldValuees muy pequeño

¿Está bien? ¿Hay algún problema para este hábito?

ocomfd
fuente
41
Tenga cuidado de que con números negativos, las dos versiones verifiquen cosas totalmente diferentes. ¿Estás seguro de eso oldValue >= 0?
user2313067
37
Dependiendo del lenguaje (pero más notablemente con C), cualquiera que sea la optimización que se te ocurra, el compilador generalmente puede hacerlo mejor, -O- , tiene el sentido suficiente para no hacerlo en absoluto.
Mark Benningfield
63
Nunca es "una buena práctica" reemplazar siempre el código X por el código Y cuando X e Y no son semánticamente equivalentes. Pero siempre es una buena idea mirar X e Y, encender el cerebro, pensar cuáles son los requisitos y luego decidir cuál de las dos alternativas es más correcta. Y después de eso, también debe pensar qué pruebas son necesarias para verificar que tiene las diferencias semánticas correctas.
Doc Brown
12
@ MarkBenningfield: No importa lo que sea, el compilador no puede optimizar la división por cero. La "optimización" en la que está pensando es la "optimización de la velocidad". El OP está pensando en otro tipo de optimización: evitar errores.
slebetman
25
El punto 2 es falso. La versión original puede desbordarse para valores pequeños, pero la nueva versión puede desbordarse para valores grandes, por lo que ninguno de los dos es más seguro en el caso general.
JacquesB

Respuestas:

74

Dos casos comunes a considerar:

Aritmética de enteros

Obviamente, si está utilizando aritmética de enteros (que se trunca) obtendrá un resultado diferente. Aquí hay un pequeño ejemplo en C #:

public static void TestIntegerArithmetic()
{
    int newValue = 101;
    int oldValue = 10;
    int SOME_CONSTANT = 10;

    if(newValue / oldValue > SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue > oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Salida:

First comparison says it's not bigger.
Second comparison says it's bigger.

Aritmética de punto flotante

Además del hecho de que la división puede producir un resultado diferente cuando se divide por cero (genera una excepción, mientras que la multiplicación no), también puede generar errores de redondeo ligeramente diferentes y un resultado diferente. Ejemplo simple en C #:

public static void TestFloatingPoint()
{
    double newValue = 1;
    double oldValue = 3;
    double SOME_CONSTANT = 0.33333333333333335;

    if(newValue / oldValue >= SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue >= oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Salida:

First comparison says it's not bigger.
Second comparison says it's bigger.

En caso de que no me creas, aquí hay un Fiddle que puedes ejecutar y ver por ti mismo.

Otros idiomas pueden ser diferentes; Sin embargo, tenga en cuenta que C #, como muchos lenguajes, implementa una biblioteca de punto flotante estándar IEEE (IEEE 754) , por lo que debería obtener los mismos resultados en otros tiempos de ejecución estandarizados.

Conclusión

Si está trabajando en zonas verdes , probablemente esté bien.

Si está trabajando en código heredado, y la aplicación es una aplicación financiera u otra aplicación sensible que realiza operaciones aritméticas y debe proporcionar resultados consistentes, tenga mucho cuidado al cambiar las operaciones. Si es necesario, asegúrese de tener pruebas unitarias que detecten cualquier cambio sutil en la aritmética.

Si solo está haciendo cosas como contar elementos en una matriz u otras funciones computacionales generales, probablemente estará bien. Sin embargo, no estoy seguro de que el método de multiplicación aclare su código.

Si está implementando un algoritmo para una especificación, no cambiaría nada en absoluto, no solo por el problema de los errores de redondeo, sino para que los desarrolladores puedan revisar el código y asignar cada expresión a la especificación para garantizar que no haya implementación defectos

John Wu
fuente
41
Segundo el bit financiero. Este tipo de cambio está pidiendo que los contadores lo persigan con horquillas. Recuerdo 5.000 líneas en las que tuve que esforzarme más para mantener a raya las horquillas que para encontrar la respuesta "correcta", que en general era un poco incorrecta. Estar fuera de .01% no importó, las respuestas absolutamente consistentes eran obligatorias. Por lo tanto, me vi obligado a hacer el cálculo de manera que causó un error de redondeo sistemático.
Loren Pechtel
8
Piense en comprar dulces de 5 centavos (ya no existe ninguno). Compre 20 piezas, la respuesta "correcta" fue sin impuestos porque no había impuestos sobre 20 compras de una pieza.
Loren Pechtel
24
@LorenPechtel, eso se debe a que la mayoría de los sistemas de impuestos incluyen una regla (por razones obvias) de que el impuesto se aplica por transacción, y el impuesto se debe en incrementos no menores que la moneda más pequeña del reino, y los montos fraccionarios se redondean a favor del contribuyente. Esas reglas son "correctas" porque son legales y consistentes. Los contadores con horcas probablemente sepan cuáles son las reglas en realidad de una manera que los programadores de computadoras no sabrán (a menos que también sean contadores experimentados). Un error de 0.01% probablemente causará un error de equilibrio, y es ilegal tener un error de equilibrio.
Steve
9
Como nunca antes había escuchado el término greenfield , lo busqué. Wikipedia dice que es "un proyecto que carece de las restricciones impuestas por el trabajo anterior".
Henrik Ripa
9
@ Steve: Mi jefe recientemente comparó "greenfield" con "brownfield". Comenté que ciertos proyectos son más como "blackfield" ... :-D
DevSolar
25

Me gusta su pregunta, ya que potencialmente cubre muchas ideas. En general, sospecho que la respuesta es que depende , probablemente de los tipos involucrados y el posible rango de valores en su caso específico.

Mi instinto inicial es reflexionar sobre el estilo , es decir. su nueva versión es menos clara para el lector de su código. Me imagino que tendría que pensar por un segundo o dos (o tal vez más) para determinar la intención de su nueva versión, mientras que su versión anterior es inmediatamente clara. La legibilidad es un atributo importante del código, por lo que su nueva versión tiene un costo.

Tienes razón en que la nueva versión evita una división por cero. Ciertamente no es necesario agregar un protector (en la línea de if (oldValue != 0)). ¿Pero esto tiene sentido? Su versión anterior refleja una relación entre dos números. Si el divisor es cero, entonces su relación no está definida. Esto puede ser más significativo en su situación, es decir. no deberías producir un resultado en este caso.

La protección contra el desbordamiento es discutible. Si sabes que newValuesiempre es más grande que oldValue, entonces quizás puedas hacer ese argumento. Sin embargo, puede haber casos en los (oldValue * SOME_CONSTANT)que también se desborde. Entonces no veo mucha ganancia aquí.

Puede haber un argumento de que obtienes un mejor rendimiento porque la multiplicación puede ser más rápida que la división (en algunos procesadores). Sin embargo, tendría que haber muchos cálculos como estos para obtener una ganancia significativa, es decir. cuidado con la optimización prematura.

Reflexionando sobre todo lo anterior, en general no creo que haya mucho que ganar con su nueva versión en comparación con la versión anterior, en particular dada la reducción en la claridad. Sin embargo, puede haber casos específicos en los que haya algún beneficio.

Dave
fuente
16
Ehm, la multiplicación arbitraria que es más eficiente que la división arbitraria no depende realmente del procesador, para máquinas del mundo real.
Deduplicador
1
También está la cuestión de la aritmética de enteros frente a coma flotante. Si la relación es fraccional, la división debe realizarse en coma flotante, lo que requiere un lanzamiento. Perder el yeso causará un error no deseado. Si la fracción resulta ser una relación entre dos enteros pequeños, reorganizarlos permite que la comparación se realice en aritmética de enteros. (En ese momento se aplicarán sus argumentos.)
rwong
@rwong No siempre. Varios idiomas hacen división entera al soltar la parte decimal, por lo que no es necesario emitir.
T. Sar - Restablece a Mónica el
@ T.Sar La técnica que describe y la semántica descrita en la respuesta son diferentes. La semántica es si el programador pretende que la respuesta sea un punto flotante o un valor fraccional; la técnica que describe es la división por multiplicación recíproca, que a veces es una aproximación perfecta (sustitución) para una división entera. La última técnica se aplica típicamente cuando el divisor se conoce de antemano, porque la derivación del entero recíproco (desplazado por 2 ** 32) se puede hacer en tiempo de compilación. Hacer eso en tiempo de ejecución no sería beneficioso porque es más costoso para la CPU.
rwong
22

No.

Probablemente llamaría a eso optimización prematura , en un sentido amplio, independientemente de si está optimizando para el rendimiento , como generalmente se refiere a la frase, o cualquier otra cosa que pueda optimizarse, como conteo de bordes , líneas de código o aún más ampliamente, cosas como "diseño".

Implementar ese tipo de optimización como un procedimiento operativo estándar pone en riesgo la semántica de su código y potencialmente oculta los bordes. De todos modos, es posible que sea necesario abordar explícitamente los casos límite que considere adecuados para eliminar en silencio . Y, es infinitamente más fácil depurar problemas alrededor de bordes ruidosos (aquellos que arrojan excepciones) sobre aquellos que fallan silenciosamente.

Y, en algunos casos, es incluso ventajoso "des-optimizar" en aras de la legibilidad, la claridad o la explicidad. En la mayoría de los casos, sus usuarios no notarán que ha guardado algunas líneas de código o ciclos de CPU para evitar el manejo de casos extremos o el manejo de excepciones. Torpe o no en silencio código, por el contrario, va a afectar a la gente - sus compañeros de trabajo como mínimo. (Y también, por lo tanto, el costo de construir y mantener el software).

El valor predeterminado es el que sea más "natural" y legible con respecto al dominio de la aplicación y el problema específico. Mantenlo simple, explícito e idiomático. Optimice según sea necesario para obtener ganancias significativas o para lograr un umbral de usabilidad legítimo.

También tenga en cuenta: los compiladores a menudo optimizan la división para usted de todos modos, cuando es seguro hacerlo.

svidgen
fuente
11
-1 Esta respuesta realmente no se ajusta a la pregunta, que trata sobre los posibles peligros de la división, nada que ver con la optimización
Ben Cottrell
13
@BenCottrell Se adapta perfectamente bien. La trampa está en poner valor en optimizaciones de rendimiento sin sentido a costa de la mantenibilidad. De la pregunta "¿hay algún problema para este hábito?" - si. Rápidamente llevará a escribir galimatías absolutas.
Michael
9
@Michael, la pregunta tampoco es preguntar sobre ninguna de esas cosas, sino específicamente sobre la exactitud de dos expresiones diferentes, cada una de las cuales tiene una semántica y un comportamiento diferentes, pero ambas están destinadas a cumplir el mismo requisito.
Ben Cottrell
55
@BenCottrell ¿Quizás podría señalarme dónde en la pregunta hay alguna mención sobre la corrección?
Michael
55
@BenCottrell Deberías haber dicho 'No puedo' :)
Michael
13

Utilice el que tenga menos errores y tenga más sentido lógico.

Por lo general , la división por una variable es una mala idea de todos modos, ya que generalmente el divisor puede ser cero.
La división por una constante generalmente depende de cuál es el significado lógico.

Aquí hay algunos ejemplos para mostrar que depende de la situación:

División buena:

if ((ptr2 - ptr1) >= n / 3)  // good: check if length of subarray is at least n/3
    ...

Multiplicación mala:

if ((ptr2 - ptr1) * 3 >= n)  // bad: confusing!! what is the intention of this code?
    ...

Multiplicación buena:

if (j - i >= 2 * min_length)  // good: obviously checking for a minimum length
    ...

División mala:

if ((j - i) / 2 >= min_length)  // bad: confusing!! what is the intention of this code?
    ...

Multiplicación buena:

if (new_length >= old_length * 1.5)  // good: is the new size at least 50% bigger?
    ...

División mala:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
fuente
2
Estoy de acuerdo en que depende del contexto, pero sus dos primeros pares de ejemplos son extremadamente pobres. No preferiría uno sobre el otro en cualquier caso.
Michael
66
@ Michael: Uhm ... ¿te parece (ptr2 - ptr1) * 3 >= ntan fácil de entender como la expresión ptr2 - ptr1 >= n / 3? ¿No hace que su cerebro se tropiece y vuelva a intentar tratar de descifrar el significado de triplicar la diferencia entre dos punteros? Si es realmente obvio para usted y su equipo, supongo que tendrá más poder; Debo estar en la minoría lenta.
Mehrdad
2
Una variable llamada ny un número arbitrario 3 son confusos en ambos casos pero, reemplazados por nombres razonables, no, no encuentro ninguno más confuso que el otro.
Michael
1
Estos ejemplos no son realmente pobres ... definitivamente no son 'extremadamente pobres', incluso si usted usa 'nombres razonables', todavía tienen menos sentido cuando los cambia por los casos malos. Si fuera nuevo en un proyecto, preferiría ver los casos 'buenos' enumerados en esta respuesta cuando fui a arreglar algún código de producción.
John-M
3

Hacer algo "siempre que sea posible" rara vez es una buena idea.

Su prioridad número uno debe ser la corrección, seguida de legibilidad y facilidad de mantenimiento. Reemplazar ciegamente la división con la multiplicación siempre que sea posible a menudo fallará en el departamento de corrección, a veces solo en casos raros y, por lo tanto, difíciles de encontrar.

Haz lo correcto y lo más legible. Si tiene evidencia sólida de que escribir código de la manera más fácil de leer causa un problema de rendimiento, entonces puede considerar cambiarlo. El cuidado, las matemáticas y las revisiones de códigos son tus amigos.

gnasher729
fuente
1

Con respecto a la legibilidad del código, creo que la multiplicación es realmente más legible en algunos casos. Por ejemplo, si hay algo que debe verificar si newValueha aumentado un 5 por ciento o más por encima oldValue, entonces 1.05 * oldValuehay un umbral contra el cual evaluar newValue, y es natural escribir

    if (newValue >= 1.05 * oldValue)

Pero tenga cuidado con los números negativos cuando refactorice las cosas de esta manera (ya sea reemplazando la división con multiplicación o reemplazando la multiplicación con división). Las dos condiciones que consideró son equivalentes si oldValuese garantiza que no sean negativas; pero supongamos newValueque en realidad es -13.5 y oldValuees -10.1. Entonces

newValue/oldValue >= 1.05

se evalúa como verdadero , pero

newValue >= 1.05 * oldValue

se evalúa como falsa .

David K
fuente
1

Tenga en cuenta la famosa división de papel por enteros invariantes usando multiplicación .

El compilador en realidad está haciendo multiplicación, si el entero es invariante. No es una division. Esto sucede incluso para no poder de 2 valores. La potencia de 2 divisiones usa obviamente cambios de bit y, por lo tanto, son aún más rápidos.

Sin embargo, para enteros no invariantes, es su responsabilidad optimizar el código. Asegúrese antes de optimizar que realmente está optimizando un cuello de botella genuino, y que la corrección no se sacrifica. Cuidado con el desbordamiento de enteros.

Me importa la microoptimización, por lo que probablemente eche un vistazo a las posibilidades de optimización.

Piense también en las arquitecturas en las que se ejecuta su código. Especialmente ARM tiene una división extremadamente lenta; necesita llamar a una función para dividir, no hay instrucción de división en ARM.

Además, en arquitecturas de 32 bits, la división de 64 bits no está optimizada, como descubrí .

juhist
fuente
1

Retomando su punto 2, de hecho, evitará el desbordamiento de un muy pequeño oldValue. Sin embargo, si SOME_CONSTANTtambién es muy pequeño, su método alternativo terminará con un flujo inferior, donde el valor no puede representarse con precisión.

Y a la inversa, ¿qué sucede si oldValuees muy grande? Tienes los mismos problemas, todo lo contrario.

Si se quiere evitar (o minimizar) el riesgo de desbordamiento / subdesbordamiento, la mejor manera es comprobar si newValuees más cercano en magnitud a oldValueo SOME_CONSTANT. Luego puede elegir la operación de división adecuada, ya sea

    if(newValue / oldValue >= SOME_CONSTANT)

o

    if(newValue / SOME_CONSTANT >= oldValue)

y el resultado será más exacto.

Para dividir por cero, en mi experiencia, esto casi nunca es apropiado para ser "resuelto" en las matemáticas. Si tiene una división por cero en sus comprobaciones continuas, entonces es casi seguro que tiene una situación que requiere un análisis y cualquier cálculo basado en estos datos no tiene sentido. Una verificación explícita de dividir por cero es casi siempre el movimiento apropiado. (Tenga en cuenta que sí digo "casi" aquí, porque no pretendo ser infalible. Solo notaré que no recuerdo haber visto una buena razón para esto en 20 años de escribir software incorporado, y seguir adelante .)

Sin embargo, si tiene un riesgo real de desbordamiento / subflujo en su aplicación, probablemente esta no sea la solución correcta. Lo más probable es que, por lo general, deba verificar la estabilidad numérica de su algoritmo, o tal vez simplemente pasar a una representación de mayor precisión.

Y si no tiene un riesgo comprobado de desbordamiento / subflujo, entonces no se preocupa por nada. Eso significa que, literalmente, debe demostrar que lo necesita, con números, en los comentarios al lado del código que explican al mantenedor por qué es necesario. Como ingeniero principal que revisa el código de otras personas, si me encuentro con alguien que esté haciendo un esfuerzo adicional por esto, personalmente no aceptaría nada menos. Esto es algo opuesto a la optimización prematura, pero generalmente tendría la misma causa raíz: la obsesión por los detalles que no hace una diferencia funcional.

Graham
fuente
0

Encapsula la aritmética condicional en métodos y propiedades significativos. No sólo buena de nombres que decir lo "A / B" medios , la comprobación de parámetros y control de errores perfectamente pueden ocultar allí también.

Es importante destacar que, dado que estos métodos se componen de una lógica más compleja, la complejidad extrínseca sigue siendo muy manejable.

Yo diría que la sustitución de multiplicación parece una solución razonable porque el problema está mal definido.

radarbob
fuente
0

Creo que no podría ser una buena idea reemplazar las multiplicaciones con divisiones porque la ALU (Unidad Aritmética-Lógica) de la CPU ejecuta algoritmos, aunque están implementados en hardware. Técnicas más sofisticadas están disponibles en procesadores más nuevos. En general, los procesadores se esfuerzan por paralelizar las operaciones de pares de bits para minimizar los ciclos de reloj necesarios. Los algoritmos de multiplicación se pueden paralelizar de manera bastante efectiva (aunque se requieren más transistores). Los algoritmos de división no se pueden paralelizar tan eficientemente. Los algoritmos de división más eficientes son bastante complejos. En general, requieren más ciclos de reloj por bit.

Ishan Shah
fuente