É uma boa prática substituir a divisão pela multiplicação, quando possível?

73

Sempre que eu precisar de divisão, por exemplo, verificação de condição, gostaria de refatorar a expressão de divisão em multiplicação, por exemplo:

Versão original:

if(newValue / oldValue >= SOME_CONSTANT)

Nova versão:

if(newValue >= oldValue * SOME_CONSTANT)

Porque acho que pode evitar:

  1. Divisão por zero

  2. Estouro quando oldValueé muito pequeno

Isso está certo? Existe algum problema para esse hábito?

ocomfd
fonte
41
Tenha cuidado para que, com números negativos, as duas versões verifiquem coisas totalmente diferentes. Você tem certeza disso oldValue >= 0?
user2313067
37
Dependendo do idioma (mas principalmente do C), seja qual for a otimização que você possa pensar, o compilador geralmente pode fazer melhor, -OR- , tem senso suficiente para não fazer nada.
precisa saber é o seguinte
63
Nunca é "uma boa prática" substituir sempre o código X pelo código Y quando X e Y não são semanticamente equivalentes. Mas é sempre uma boa idéia olhar para X e Y, ligar o cérebro, pensar sobre quais são os requisitos e depois decidir qual das duas alternativas é mais correta. E depois disso, você também deve pensar em quais testes são necessários para verificar se você acertou as diferenças semânticas.
Doc Brown
12
@ MarkBenningfield: Não é o que for, o compilador não pode otimizar a divisão por zero. A "otimização" que você está pensando é "otimização de velocidade". O OP está pensando em outro tipo de otimização - prevenção de bugs.
slebetman
25
O ponto 2 é falso. A versão original pode estourar para valores pequenos, mas a nova versão pode estourar para valores grandes, portanto, nem é mais seguro no caso geral.
precisa saber é o seguinte

Respostas:

74

Dois casos comuns a serem considerados:

Aritmética de número inteiro

Obviamente, se você estiver usando aritmética inteira (que trunca), obterá um resultado diferente. Aqui está um pequeno exemplo em 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.");
    }
}

Resultado:

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

Aritmética de ponto flutuante

Além do fato de que a divisão pode gerar um resultado diferente quando divide por zero (gera uma exceção, enquanto a multiplicação não), também pode resultar em erros de arredondamento ligeiramente diferentes e em um resultado diferente. Exemplo simples em 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.");
    }
}

Resultado:

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

Caso você não acredite em mim, aqui está um violino que você pode executar e ver por si mesmo.

Outros idiomas podem ser diferentes; lembre-se, no entanto, que o C #, como muitas linguagens, implementa uma biblioteca de ponto flutuante padrão IEEE (IEEE 754) , portanto, você deve obter os mesmos resultados em outros tempos de execução padronizados.

Conclusão

Se você está trabalhando no greenfield , provavelmente está bem.

Se você estiver trabalhando no código legado, e o aplicativo for um aplicativo financeiro ou outro sensível que executa aritmética e é necessário para fornecer resultados consistentes, tenha muito cuidado ao mudar as operações. Se necessário, verifique se você possui testes de unidade que detectam alterações sutis na aritmética.

Se você está apenas fazendo coisas como contar elementos em uma matriz ou outras funções computacionais gerais, provavelmente estará bem. Não tenho certeza se o método de multiplicação deixa seu código mais claro.

Se você estiver implementando um algoritmo em uma especificação, eu não mudaria nada, não apenas por causa do problema de erros de arredondamento, mas para que os desenvolvedores possam revisar o código e mapear cada expressão de volta à especificação para garantir que não haja implementação falhas.

John Wu
fonte
41
Segundo o bit financeiro. Esse tipo de mudança está pedindo que os contadores o perseguam com forcados. Lembro-me de 5.000 linhas em que tive que me esforçar mais para manter os forquilhas afastados do que para encontrar a resposta "certa" - o que, na verdade, estava geralmente um pouco errado. Estar fora de 0,01% não importava, respostas absolutamente consistentes eram obrigatórias. Assim, fui forçado a fazer o cálculo de maneira a causar um erro sistemático de arredondamento.
Loren Pechtel
8
Pense em comprar balas de 5 centavos (não existe mais.) Compre 20 peças, a resposta "correta" não era imposto porque não havia imposto sobre 20 compras de uma peça.
Loren Pechtel
24
@LorenPechtel, isso ocorre porque a maioria dos sistemas tributários inclui uma regra (por razões óbvias) de que o imposto é cobrado por transação, e o imposto é devido em incrementos não menores que a menor moeda do reino, e os valores fracionários são arredondados a favor do contribuinte. Essas regras são "corretas" porque são legais e consistentes. Os contadores com forcados provavelmente sabem quais são as regras de uma maneira que os programadores de computador não sabem (a menos que também sejam contadores experientes). Um erro de 0,01% provavelmente causará um erro de balanceamento e é ilegal ter um erro de balanceamento.
Steve Steve
9
Como nunca ouvi o termo greenfield antes, procurei. A Wikipedia diz que é "um projeto que não possui restrições impostas por trabalhos anteriores".
Henrik Ripa
9
@ Steve: Meu chefe recentemente comparou "greenfield" a "brownfield". Eu observei que certos projetos são mais parecidos com "blackfield" ... :-D
DevSolar 31/01
25

Gostei da sua pergunta, pois potencialmente abrange muitas idéias. No geral, eu suspeito que a resposta é que depende , provavelmente dos tipos envolvidos e da possível faixa de valores em seu caso específico.

Meu instinto inicial é refletir sobre o estilo , ie. sua nova versão é menos clara para o leitor do seu código. Eu imagino que teria que pensar por um segundo ou dois (ou talvez mais) para determinar a intenção de sua nova versão, enquanto sua versão antiga é imediatamente clara. A legibilidade é um atributo importante do código, portanto, há um custo em sua nova versão.

Você está certo de que a nova versão evita uma divisão por zero. Certamente você não precisa adicionar uma guarda (na linha de if (oldValue != 0)). Mas isso faz sentido? Sua versão antiga reflete uma proporção entre dois números. Se o divisor é zero, sua proporção é indefinida. Isso pode ser mais significativo na sua situação, ie. você não deve produzir um resultado neste caso.

A proteção contra estouro é discutível. Se você sabe que newValueé sempre maior que oldValue, então talvez você possa argumentar. No entanto, pode haver casos em (oldValue * SOME_CONSTANT)que também transbordará. Portanto, não vejo muito ganho aqui.

Pode haver um argumento de que você obtém melhor desempenho porque a multiplicação pode ser mais rápida que a divisão (em alguns processadores). No entanto, teria que haver muitos cálculos como esses para obter um ganho significativo, ou seja. cuidado com a otimização prematura.

Refletindo sobre tudo o que foi exposto acima, em geral, acho que não há muito a ser ganho com sua nova versão em comparação com a versão antiga, principalmente devido à redução de clareza. No entanto, pode haver casos específicos em que há algum benefício.

Dave
fonte
16
Ah, a multiplicação arbitrária sendo mais eficiente que a divisão arbitrária não é realmente dependente do processador, para máquinas do mundo real.
Deduplicator
11
Há também a questão da aritmética de número inteiro versus ponto flutuante. Se a proporção for fracionária, a divisão precisará ser executada em ponto flutuante, exigindo uma conversão. Perder o elenco causará erros não intencionais. Se a fração for uma razão entre dois números inteiros pequenos, reorganizá-los permitirá que a comparação seja conduzida em aritmética inteira. (Em que ponto seus argumentos serão aplicadas.)
rwong
@rwong Nem sempre. Vários idiomas por aí fazem divisão inteira ao largar a parte decimal, portanto, nenhuma conversão é necessária.
T. Sar - Restabelece Monica
@ T.Sar A técnica que você descreve e a semântica descrita na resposta são diferentes. Semântica é se o programador pretende que a resposta seja um valor de ponto flutuante ou fracionário; a técnica que você descreve é ​​a divisão por multiplicação recíproca, que às vezes é uma aproximação perfeita (substituição) de uma divisão inteira. A última técnica é normalmente aplicada quando o divisor é conhecido antecipadamente, porque a derivação do número inteiro recíproco (deslocado 2 ** 32) pode ser feita em tempo de compilação. Fazer isso em tempo de execução não seria benéfico porque é mais caro para a CPU.
rwong
22

Não.

Eu provavelmente chamaria isso de otimização prematura , em um sentido amplo, independentemente de você estar otimizando para o desempenho , como a frase geralmente se refere, ou qualquer outra coisa que possa ser otimizada, como contagem de bordas , linhas de código ou ainda mais amplamente, coisas como "design".

A implementação desse tipo de otimização como procedimento operacional padrão coloca em risco a semântica do seu código e potencialmente oculta as bordas. Os casos extremos que você deseja eliminar silenciosamente podem precisar ser explicitamente abordados de qualquer maneira . E é infinitamente mais fácil depurar problemas em bordas barulhentas (aquelas que lançam exceções) sobre aquelas que falham silenciosamente.

E, em alguns casos, é até vantajoso "des otimizar" por questões de legibilidade, clareza ou explícita. Na maioria dos casos, seus usuários não notarão que você salvou algumas linhas de código ou ciclos de CPU para evitar o tratamento de casos extremos ou o tratamento de exceções. Inábil ou silenciosamente falhar código, por outro lado, vai afetar as pessoas - seus colegas de trabalho, no mínimo. (E também, portanto, o custo para construir e manter o software.)

O padrão é o que for mais "natural" e legível em relação ao domínio do aplicativo e ao problema específico. Mantenha-o simples, explícito e idiomático. Otimize conforme necessário para ganhos significativos ou para atingir um limite de usabilidade legítimo.

Observe também: os compiladores geralmente otimizam a divisão para você de qualquer maneira - quando é seguro fazê-lo.

svidgen
fonte
11
-1 Esta resposta não se encaixa a questão, que é sobre as armadilhas potenciais de divisão - nada a ver com a otimização
Ben Cottrell
13
@BenCottrell Ele se encaixa perfeitamente bem. A armadilha está em colocar valor em otimizações inúteis de desempenho, ao custo de manutenção. Da pergunta "existe algum problema para esse hábito?" - sim. Isso levará rapidamente a escrever sem sentido absoluto.
Michael Michael
9
@ Michael, a pergunta também não está perguntando sobre nenhuma dessas coisas - está especificamente perguntando sobre a exatidão de duas expressões diferentes, cada uma com semântica e comportamento diferentes, mas ambas pretendem atender ao mesmo requisito.
Ben Cottrell
5
@BenCottrell Talvez você possa me indicar em que parte da pergunta há alguma menção sobre correção?
Michael Michael
5
@BenCottrell Você deve ter apenas disse 'eu não posso' :)
Michael
13

Use o que for menos buggy e faça mais sentido lógico.

Geralmente , a divisão por uma variável é uma má ideia, pois, geralmente, o divisor pode ser zero.
A divisão por uma constante geralmente depende apenas do significado lógico.

Aqui estão alguns exemplos para mostrar que isso depende da situação:

Divisão boa:

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

Multiplicação inválida:

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

Multiplicação boa:

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

Divisão ruim:

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

Multiplicação boa:

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

Divisão ruim:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
fonte
2
Concordo que depende do contexto, mas seus dois primeiros pares de exemplos são extremamente pobres. Eu não preferiria um sobre o outro em ambos os casos.
Michael Michael
6
@ Michael: Uhm ... você acha (ptr2 - ptr1) * 3 >= ntão fácil de entender quanto a expressão ptr2 - ptr1 >= n / 3? Isso não faz seu cérebro tropeçar e voltar a tentar decifrar o significado de triplicar a diferença entre dois indicadores? Se é realmente óbvio para você e sua equipe, acho que tem mais poder; Eu devo apenas estar na minoria lenta.
Mehrdad
2
Uma variável chamada ne um número arbitrário 3 são confusos nos dois casos, mas, substituídos por nomes razoáveis, não, não acho nem um mais confuso quanto o outro.
Michael Michael
11
Esses exemplos não são realmente ruins. Definitivamente, não são 'extremamente pobres' - mesmo que você coloque nomes 'razoáveis', eles ainda fazem menos sentido quando você os troca pelos casos ruins. Se eu fosse novo em um projeto, preferiria ver os casos "bons" listados nesta resposta quando fui corrigir algum código de produção.
John-M
3

Fazer qualquer coisa “sempre que possível” raramente é uma boa ideia.

Sua prioridade número um deve ser a correção, seguida pela legibilidade e manutenção. Substituir cegamente a divisão pela multiplicação, sempre que possível, geralmente falha no departamento de correção, às vezes apenas em casos raros e, portanto, difíceis de encontrar.

Faça o que é correto e mais legível. Se você tiver evidências sólidas de que escrever um código da maneira mais legível causa um problema de desempenho, considere alterá-lo. Cuidados, matemática e revisões de código são seus amigos.

gnasher729
fonte
1

Em relação à legibilidade do código, acho que a multiplicação é realmente mais legível em alguns casos. Por exemplo, se houver algo que você deve verificar se newValueaumentou 5% ou mais acima oldValue, 1.05 * oldValueexiste um limite contra o qual testar newValuee é natural escrever

    if (newValue >= 1.05 * oldValue)

Mas tome cuidado com números negativos quando você refatorar as coisas dessa maneira (substituindo a divisão pela multiplicação ou substituindo a multiplicação pela divisão). As duas condições que você considerou são equivalentes se oldValuefor garantido que não sejam negativas; mas suponha que newValueseja realmente -13,5 e oldValue-10,1. Então

newValue/oldValue >= 1.05

avalia como verdadeiro , mas

newValue >= 1.05 * oldValue

avalia como falso .

David K
fonte
1

Observe a famosa divisão de papel por números inteiros invariantes usando a multiplicação .

O compilador está realmente fazendo a multiplicação, se o número inteiro for invariável! Não é uma divisão. Isso acontece mesmo para não potência de 2 valores. O poder de 2 divisões usa obviamente mudanças de bits e, portanto, é ainda mais rápido.

No entanto, para números inteiros não invariantes, é sua responsabilidade otimizar o código. Antes de otimizar, verifique se você está realmente otimizando um gargalo genuíno e se a correção não é sacrificada. Cuidado com o excesso de número inteiro.

Eu me preocupo com a micro-otimização, então provavelmente daria uma olhada nas possibilidades de otimização.

Pense também nas arquiteturas em que seu código é executado. Especialmente o ARM possui uma divisão extremamente lenta; você precisa chamar uma função para dividir, não há instrução de divisão no ARM.

Além disso, em arquiteturas de 32 bits, a divisão de 64 bits não é otimizada, como descobri .

juhist
fonte
1

Pegando no seu ponto 2, ele realmente impedirá o estouro por um valor muito pequeno oldValue. No entanto, se SOME_CONSTANTtambém for muito pequeno, seu método alternativo acabará com fluxo insuficiente, onde o valor não pode ser representado com precisão.

E, inversamente, o que acontece se oldValuefor muito grande? Você tem os mesmos problemas, exatamente o contrário.

Se você deseja evitar (ou minimizar) o risco de transbordamento / transbordamento, a melhor maneira é verificar se o valor newValueé o mais próximo oldValuepossível SOME_CONSTANT. Você pode então escolher a operação de divisão apropriada,

    if(newValue / oldValue >= SOME_CONSTANT)

ou

    if(newValue / SOME_CONSTANT >= oldValue)

e o resultado será mais preciso.

Para dividir por zero, na minha experiência, quase nunca é apropriado ser "resolvido" na matemática. Se você tem uma divisão por zero em suas verificações contínuas, quase certamente você tem uma situação que requer alguma análise e quaisquer cálculos baseados nesses dados não fazem sentido. Uma verificação explícita de dividir por zero é quase sempre a movimentação apropriada. (Observe que eu digo "quase" aqui, porque não pretendo ser infalível. Vou apenas observar que não me lembro de ter visto uma boa razão para isso em 20 anos escrevendo software incorporado e segui em frente .)

No entanto, se você tiver um risco real de transbordamento / transbordamento em seu aplicativo, essa provavelmente não é a solução certa. O mais provável é que você geralmente verifique a estabilidade numérica do seu algoritmo, ou talvez simplesmente mude para uma representação de maior precisão.

E se você não tem um risco comprovado de estourar / estourar, não se preocupa com nada. Isso significa que você literalmente precisa provar que precisa, com números, nos comentários ao lado do código, que explicam ao mantenedor por que é necessário. Como engenheiro principal, revendo o código de outras pessoas, se eu encontrasse alguém que se esforçasse mais com isso, pessoalmente não aceitaria nada menos. Isso é exatamente o oposto da otimização prematura, mas geralmente teria a mesma causa raiz - obsessão por detalhes que não faz diferença funcional.

Graham
fonte
0

Encapsule a aritmética condicional em métodos e propriedades significativos. A boa nomeação não apenas diz o que "A / B" significa , como também a verificação de parâmetros e a manipulação de erros também podem ser ocultados.

Importante, como esses métodos são compostos em uma lógica mais complexa, a complexidade extrínseca permanece muito gerenciável.

Eu diria que a substituição da multiplicação parece uma solução razoável porque o problema está mal definido.

radarbob
fonte
0

Eu acho que não seria uma boa ideia substituir multiplicações por divisões porque a ALU (Unidade Aritmética-Lógica) da CPU executa algoritmos, embora eles sejam implementados em hardware. Técnicas mais sofisticadas estão disponíveis nos processadores mais recentes. Geralmente, os processadores se esforçam para paralelizar as operações de pares de bits para minimizar os ciclos de clock necessários. Os algoritmos de multiplicação podem ser paralelizados de maneira bastante eficaz (embora sejam necessários mais transistores). Os algoritmos de divisão não podem ser paralelizados com a mesma eficiência. Os algoritmos de divisão mais eficientes são bastante complexos. Geralmente, eles exigem mais ciclos de clock por bit.

Ishan Shah
fonte