maneira mais rápida de verificar a condição l + 1 https://stackoverflow.com/questions/1017480

Question

O que é a maneira mais rápida de verificar a condição

l + 1 < r

para int l,r em Java?

l e r não são constantes e sei que l <= r. A comparação é uma condição de parada para um loop while em uma implementação de busca binária. É claro que estou aferição meu código, tanto em um teste separado (pesquisar uma grande variedade) e no código que o utiliza.

O que eu estou procurando, eu imagino, é uma espécie de uma operação de bits que seria mais rápido do que a condição atual. Mas eu não sei.

Answer 1

Eu acho que é provavelmente tão rápido como ele vai ficar. Isso vai reduzir a muito simples bytecode, e o JIT (just-in-time do compilador) vai provavelmente reduzir isso para uma implementação nativa muito simples.

(independente:. Interessante ver a 'quant dev' usar Java btw não acontece que muitas vezes)

Answer 2

Este tipo de micro-otimização é quase sempre uma má idéia; o seu desempenho para um pequeno pedaço tal será totalmente dependente da forma como o compilador hotspot otimiza seu código, e os efeitos de cache sutis que têm a ver com o código circundante.

Answer 3

Bem, a comparação subjacente deve:

adicionar 1 a l, comparar o resultado com r

ou

subtrair um de R e comparar o resultado para l

Todo o hardware moderno terá o mesmo desempenho bruto para operação (em que a adição e subtração de qualquer tipo de dados nativo tem desempenho idêntico em termos de ciclos de efeitos secundários completos e dutos).

A única maneira que isso terá qualquer efeito seja se:

um de L ou R são constantes conhecidas em tempo de compilação. por exemplo.

l + 1 < 5
5 + 1 < r

neste caso, um compilador otimizado pobre pode não perceber, pode converter o primeiro em l < 4

e todas compiladores de Java são necessários para detectar que o segundo caso é 6 < r

A outra é, se os tipos de dados de L e R são diferentes.

A operação de:

1. ponto flutuante adição / subtração, então comparação com um int
   versos
2. integrante adição / subtração, em seguida, a comparação com um duplo pode ser diferente.

É justo dizer que as chances de este ser um problema sério em sua aplicação são insignificantes uma vez que o custo do ciclo de qualquer um destes é pequena em comparação com o hit gasoduto de quaisquer mispredictions agências associado à decisão.

Além disso, um JIT decente pode fazer todos os tipos de otimizações em relação ao código circundante que superam os micro otimização realizada.

Answer 4

Tenha um lr1 variável que equivale sempre (l - r + 1). Sempre que você aumentar ou l decréscimo, fazer o mesmo com lr1. Da mesma forma para r.

Em seguida, o teste torna-se (lr1 < 0), e as instruções para modificar lr1 são executados não mais frequentemente do que o necessário.

Eu me sinto um pouco bobo dando-lhe uma micro-otimização, que na maioria dos casos é penny-wise, libra-foolish. Como se você está comparando cordas, ele vai inundar totalmente esse teste.

ADICIONADO: Desde que você está fazendo busca binária, gostaria de mencionar legal de Jon Bentley desenrolando de busca binária. Primeiro você pad tabela A até uma potência de 2, como 1024. Então você escrever algo como isto:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

e, finalmente, testar se (X == A[i]). Ou, se você não quer preenchê-lo, deixe as declarações if ser algo como
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 5

O que todos esses caras disse. O compilador vai otimizar isso fora para você. Escrevê-lo assim que olha e lê corretamente para você e seguir em frente.

Answer 6

Sua melhor aposta é a de ajustar a JVM em vez do código -. Dado que este é o seu gargalo

Tente iniciar a JVM com o -server -XX:+AggressiveOpts argumentos.

Answer 7

Como cerca de mover o seu fora teste de igualdade do loop while, para que verifique .equals (), apenas após a rescisão. btw eu não poderia encontrar alguma maneira pouco girando para testar se l + 1