Simplificada algoritmo para calcular o espaço restante em um buffer circular?

Question

Eu era saber se há uma maneira mais simples (single) para calcular o espaço restante em um buffer circular que isso?

int remaining = (end > start)
                ? end-start
                : bufferSize - start + end;

Answer 1

Se você está preocupado com condicionais mal previstos abrandar gasoduto da sua CPU, você poderia usar o seguinte:

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize);

Mas isso é provável que seja otimização prematura (a menos que você realmente identificou este como um hotspot). Vara com sua técnica atual, que é muito mais legível.

Answer 2

Hmmm ....

int remaining = (end - start + bufferSize) % bufferSize;

13 fichas, que eu ganho?

Answer 3

De acordo com o padrão C ++, secção 5.6, parágrafo 4:

O binário / operador proporciona o quociente e o operador binário% origina o resto da divisão da primeira expressão pelo segundo. Se o segundo operando de / ou% é zero o comportamento é indefinido; caso contrário (a / b) * b + a% b é igual a um. Se ambos os operandos são não-negativo, então o restante é não-negativo; se não, o sinal de que o restante é definido pela implementação.

Uma nota de rodapé sugere que o arredondamento é preferido o quociente para zero, o que deixaria o restante negativo.

Portanto, as abordagens (end - start) % bufferSize não funcionam de forma confiável. C ++ não tem aritmética modular (exceto no sentido oferecidos por tipos integrais não assinados).

A abordagem recomendada pela j_random_hacker é diferente, e parece ser bom, mas eu não sei que é qualquer melhoria real na simplicidade ou a velocidade. A conversão de um booleano para um int é engenhosa, mas requer análise mental, e que mexer poderia ser mais caro do que o uso de:?., Dependendo do compilador e da máquina

Eu acho que você tem a versão mais simples e melhor ali, e eu não mudaria isso.

Answer 4

Se o tamanho do buffer circular é uma potência de dois, você pode fazer ainda melhor por ter start e end representam posições em um fluxo virtual em vez de índices no armazenamento do buffer circular. Assumindo que start e end não são assinados, o acima torna-se:

int remaining= bufferSize - (end - start);

Na verdade, recebendo elementos fora do buffer é um pouco mais complicado, mas a sobrecarga geralmente é pequeno o suficiente com uma potência de 2 buffer circular tamanho (apenas mascarando com bufferSize - 1) para fazer toda a outra lógica do seu buffer circular muito mais simples e limpador. Além disso, você começa a usar todos os elementos desde que você não se preocupar com end==start!

Answer 5

perder a condicional:

int remaining = (end + bufferSize - start - 1) % bufferSize + 1

Edit: O -1 e +1 são para o caso quando end == start. Nesse caso, este método vai assumir o buffer está vazio. Dependendo da implementação específica do seu buffer, você pode precisar de ajustar estes para evitar uma situação off-by-1.

Answer 6

segmento idoso eu sei, mas pensei que isso poderia ser útil.

Não tenho certeza o quão rápido isso implementa em C ++, mas em RTL que fazer isso se o tamanho é n ^ 2

remaining = (end[n] ^ start[n])
            ? start[n-1:0] - end[n-1:0]
            : end[n-1:0] - start[n-1:0];

ou

remaining = if (end[n] ^ start[n]) {
              start[n-1:0] - end[n-1:0]
            } else { 
              end[n-1:0] - start[n-1:0] 
            };