Contagem decrescente em para-lacetes
https://stackoverflow.com/questions/804777
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu acredito (a partir de uma leitura de pesquisa) que a contagem regressiva em para-lacetes é realmente mais eficiente e mais rápido em tempo de execução. Meu código de software completo é C ++
Actualmente, eu tenho este:
for (i=0; i<domain; ++i) {
meu 'eu' é int não assinado resgister, também 'domínio' é sem assinatura int
na for-loop i é utilizada para passar por uma matriz, por exemplo.
array[i] = do stuff
converter este a contagem decrescente mexe-se a esperada saída / correto da minha rotina.
Eu posso imaginar a resposta a ser bastante trivial, mas não posso colocar minha cabeça em volta dela.
UPDATE: 'fazer coisas' não depende de prévia ou posteriormente iteração. Os cálculos no interior da for-loop são independentes para a iteração de i. (Espero que sentido faz).
UPDATE: Para conseguir um aumento de velocidade de tempo de execução com o meu para-loop, posso contar para baixo e se assim for remover a parte não assinado quando delcaring minha int, ou o que outro método
?Por favor, ajuda.
Solução
Eu estou supondo que o seu para trás para olhares loop como este:
for (i = domain - 1; i >= 0; --i) {
Nesse caso, porque i é não assinado , ele irá sempre ser maior ou igual a zero. Quando você diminuir uma variável não assinado que é igual a zero, ele vai envolver em torno de um número muito grande. A solução é ou fazer i assinado, ou alterar a condição no loop for assim:
for (i = domain - 1; i >= 0 && i < domain; --i) {
Ou contar de domain para 1 ao invés de domain - 1 para 0:
for (i = domain; i >= 1; --i) {
array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}
Outras dicas
Há apenas um método correto de looping para trás utilizando um contador sem sinal:
for( i = n; i-- > 0; )
{
// Use i as normal here
}
Há um truque aqui, para a última iteração do loop você terá i = 1 no topo do loop, eu-> 0 passes porque 1> 0, então i = 0 no corpo do loop. Na próxima iteração eu-> 0 falha porque i == 0, de modo que não importa o que o decréscimo postfix rolou sobre o balcão.
Muito non óbvio que eu sei.
Esta não é uma resposta para o seu problema, porque você não parecem ter um problema.
Este tipo de otimização é completamente irrelevante e deve ser deixada para o compilador (se feito em tudo).
Você perfilado o seu programa para verificar se o seu ciclo for é um gargalo? Se não, então você não precisa gastar tempo se preocupando com isso. Ainda mais, tendo "i" como "registrar" int, como você escreve, não faz qualquer sentido real do ponto de vista do desempenho.
Mesmo sem saber o seu domínio do problema, eu posso lhe garantir que tanto a técnica de loop reverso eo "registo" contra int terão insignificante impacto no desempenho do seu programa. Lembre-se, "otimização prematura é a raiz de todo mal".
Dito isso, o tempo de otimização melhor gasto seria no pensamento sobre a estrutura global do programa, estruturas de dados e algoritmos utilizados, utilização de recursos, etc.
Verificar se um número é zero pode ser mais rápido ou mais eficiente do que uma comparação. Mas este é o tipo de micro-otimização que você realmente não deve se preocupar -. Poucos ciclos de clock será grandemente diminuído por apenas sobre qualquer outra questão perf
Em x86:
dec eax
jnz Foo
Em vez de:
inc eax
cmp eax, 15
jl Foo
Se você tem um compilador decente, ele vai otimizar "contando" tão eficazmente como "contagem regressiva". Apenas tente alguns benchmarks e você vai ver.
Assim você "ler" que couting para baixo é mais eficiente? Acho isso muito difícil de acreditar a menos que você me mostrar alguns resultados Profiler e o código. Posso comprá-lo em algumas circunstâncias, mas, no caso geral, não. Parece-me que este é um caso clássico de otimização prematura.
O seu comentário sobre "register int i" é também muito revelador. Hoje em dia, o compilador sabe sempre melhor do que você como alocar registros. Não se incomode com usando a palavra-chave registo a menos que tenha perfilado seu código.
Quando você está looping através de estruturas de dados, de qualquer tipo, erros de cache tem um impacto muito maior do que a direção está indo. Preocupe-se com o quadro maior de layout de memória e estrutura algoritmo em vez de micro-otimizações triviais.
Não tem nada a ver com contagem se ou abaixo . O que pode ser mais rápido é contagem em direção a zero . resposta de Michael mostra por que - x86 dá-lhe uma comparação com zero como um efeito colateral implícito de muitas instruções, por isso depois de ajustar seu contador, você só se ramificar, com base no resultado, em vez de fazer uma comparação explícita. (Talvez outras arquiteturas fazer isso também, eu não sei.)
compiladores Pascal da Borland são notórias para a realização de que a otimização. O compilador transforma este código:
for i := x to y do
foo(i);
em uma representação interna mais parecido com isto:
tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
foo(i);
Inc(i);
Dec(tmp);
end;
(digo notório não porque a otimização afeta o resultado do loop, mas porque o depurador exibe a variável do contador incorretamente. Quando o programador inspeciona i, o depurador pode exibir o valor de tmp vez, não causando final de confusão e pânico para programadores que pensam seus laços estão em execução para trás.)
A idéia é que, mesmo com o Inc extra ou instrução Dec, ainda é uma vitória líquida, em termos de tempo de execução, sobre fazendo uma comparação explícita. Se você pode realmente aviso que a diferença está em debate.
Mas nota que a conversão é algo que o compilador faria automaticamente , com base no fato que considerou a transformação de valor. O compilador é geralmente melhor em otimização de código do que você é, por isso não gastar muito esforço competir com ele.
De qualquer forma, você perguntou sobre C ++, não Pascal. C ++ "para" laços não são tão fáceis de aplicar que a otimização como Pascal "para" loops são porque os limites de loops de Pascal são sempre totalmente calculada antes da execução do loop, enquanto C ++ laços às vezes dependem da condição de parada eo loop conteúdo. compiladores C ++ precisa fazer alguma quantidade de análise estática para determinar se qualquer laço dado poderia caber os requisitos para o tipo de transformação laços Pascal qualificar para incondicionalmente. Se o compilador C ++ faz a análise, então ele poderia fazer uma transformação similar.
Não há nada que você parar de escrever seus loops dessa maneira em seu próprio país:
for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
array[i] = do stuff
Fazer isso pode tornar seu código correr mais rápido. Como eu disse antes, porém, você provavelmente não vai notar. O custo maior do que você paga por organizar manualmente seus loops como essa é que seu código não segue idiomas estabelecidos. Seu laço é um perfeitamente normal "para" loop, mas já não aparência como um - ele tem duas variáveis, eles estão contando em direções opostas, e um deles é nem mesmo usado no corpo do laço - para quem lê o seu código (incluindo você, uma semana, um mês ou um ano a partir de agora, quando você esqueceu a "otimização" que você estava esperando para conseguir) terá que gastar prova esforço extra para si mesmo que o loop é realmente um laço comum disfarçado.
(Você notou que o meu código acima variáveis ??não assinados usados ??sem risco de envolvimento em torno do zero? Usando duas variáveis ??separadas permite isso.)
Três coisas para tirar de tudo isso:
- Deixe o otimizador de fazer o seu trabalho; em geral é melhor para ele do que você.
- Faça olhar código comum tão comum que o código especial não tem que competir para conseguir a atenção das pessoas rever, depuração, ou mantê-la.
- Não faça nada extravagante em nome do desempenho até testando e profiling mostram que isso é necessário.
Você pode tentar o seguinte, que compilador irá otimizar de forma muito eficiente:
#define for_range(_type, _param, _A1, _B1) \
for (_type _param = _A1, _finish = _B1,\
_step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
_stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))
Agora você pode usá-lo:
for_range (unsigned, i, 10,0)
{
cout << "backwards i: " << i << endl;
}
for_range (char, c, 'z','a')
{
cout << c << endl;
}
enum Count { zero, one, two, three };
for_range (Count, c, three, zero)
{
cout << "backwards: " << c << endl;
}
Você pode interagir em qualquer direção:
for_range (Count, c, zero, three)
{
cout << "forward: " << c << endl;
}
O loop
for_range (unsigned,i,b,a)
{
// body of the loop
}
irá produzir o seguinte código:
mov esi,b
L1:
; body of the loop
dec esi
cmp esi,a-1
jne L1
É difícil dizer com a informação dada, mas ... inverter a sua matriz, e contagem regressiva?
Jeremy Ruten justamente salientou que o uso de um contador de loop não assinado é perigoso. Também é desnecessário, tanto quanto eu posso dizer.
Outros também têm apontado os perigos de otimização prematura. Eles são absolutamente certo.
Com isso dito, aqui é um estilo que eu usei ao programar sistemas embarcados muitos anos atrás, quando cada byte e cada ciclo fez contar para alguma coisa. Estas formas foram útil para mim nas CPUs e compiladores que eu estava usando, mas sua milhagem pode variar particulares.
// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
*p-- = (... whatever ...)
}
Esta forma leva vantagem da bandeira condição que está definido na --i) é a chave aqui -. Utilizando postdecrement (i--) não teria funcionado bem
Como alternativa,
// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
*(--p) = (... whatever ...)
}
Esta segunda forma aproveita ponteiro (endereço) aritmética. Raramente vejo a forma (pointer - int) estes dias (por uma boa razão), mas as garantias de linguagem que quando você subtrair um int de um ponteiro, o ponteiro é diminuído por (int * sizeof (*pointer)).
Vou enfatizar novamente que se essas formas são uma vitória para você depende da CPU e compilador que você está usando. Eles me serviu bem na Motorola 6809 e 68000 arquiteturas.
Em alguns mais tarde braço núcleos, decremento e comparar leva apenas uma única instrução. Isso faz com laços decrementing mais eficiente do que o incremento queridos.
Eu não sei por que não há uma instrução comparar-incremento também.
Estou surpreso que este post foi votado -1 quando é um verdadeiro problema.
Todo mundo aqui está se concentrando no desempenho. Há realmente uma razão lógica para iterate para zero que pode resultar em um código mais limpo.
iteração sobre o último elemento primeiro é conveniente quando você excluir elementos inválidos, trocando com o final da matriz. Para maus elementos não adjacentes à extremidade que pode trocar para a posição final, diminuir a extremidade ligada da matriz, e manter a iteração. Se você fosse fazer uma iteração para o fim, em seguida, trocando com o fim pode resultar em troca ruim para ruim. Iterando fim a 0 sabemos que o elemento no final da matriz já foi provado válido para esta iteração.
Para obter mais explicações ...
Se:
- Você eliminar maus elementos, trocando com uma extremidade da matriz e alterando os limites de matriz para excluir os maus elementos.
Então, obviamente:
- Você trocaria com um bom elemento ou seja, um que já foi testado nesta iteração.
Então, isso implica:
- Se iterate longe da variável ligada, em seguida, elementos entre a variável ligada eo ponteiro iteração atual foram provados bom. Se o ponteiro iteração recebe ++ ou - não importa. O que importa é que estamos repetindo longe da variável vinculados por isso sabemos que os elementos adjacentes a ele são boas.
Então, finalmente:
- Iterating na direção de 0 nos permite usar apenas uma variável para representar os limites da matriz. Se isso é importante é uma decisão pessoal entre você e seu compilador.
O que importa muito mais do que se você está aumentando ou diminuindo seu contador é se ou não você está indo para cima ou para baixo memória memória. A maioria dos caches são otimizados para subir memória, não para baixo memória. Desde o tempo de acesso à memória é o gargalo que a maioria dos programas hoje rosto, isso significa que a mudança de seu programa para que você subir de memória pode resultar em um aumento de performance, mesmo que isso requer comparar o seu contador para um valor diferente de zero. Em alguns dos meus programas, eu vi uma melhoria significativa no desempenho alterando o meu código para subir memória em vez de para baixo.
cético? Aqui está a saída que eu tenho:
sum up = 705046256
sum down = 705046256
Ave. Up Memory = 4839 mus
Ave. Down Memory = 5552 mus
sum up = inf
sum down = inf
Ave. Up Memory = 18638 mus
Ave. Down Memory = 19053 mus
a partir de executar este programa:
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
std::random_device rnd_device;
std::mt19937 generator(rnd_device());
std::uniform_int_distribution<T> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
std::random_device rnd_device;
std::mt19937_64 generator(rnd_device());
std::uniform_real_distribution<double> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
T sum = 0;
auto it = first;
do {
sum += *it;
it++;
} while (it != one_past_last);
total += sum;
}
template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI one_past_last, T &total) {
T sum = 0;
auto it = one_past_last;
do {
it--;
sum += *it;
} while (it != first);
total += sum;
}
template<class T> std::chrono::nanoseconds TimeDown(
std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_down(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class T> std::chrono::nanoseconds TimeUp(
std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_up(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
int main() {
std::size_t num_repititions = 1 << 10;
{
typedef int ValueType;
auto lower = std::numeric_limits<ValueType>::min();
auto upper = std::numeric_limits<ValueType>::max();
std::vector<ValueType> vec(1 << 24);
FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
const auto vec_original = vec;
ValueType sum_up = 0, sum_down = 0;
auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
std::cout << "sum up = " << sum_up << '\n';
std::cout << "sum down = " << sum_down << '\n';
std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n";
std::cout << "Ave. Down Memory = "<< time_down/(num_repititions * 1000) << " mus"
<< std::endl;
}
{
typedef double ValueType;
auto lower = std::numeric_limits<ValueType>::min();
auto upper = std::numeric_limits<ValueType>::max();
std::vector<ValueType> vec(1 << 24);
FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
const auto vec_original = vec;
ValueType sum_up = 0, sum_down = 0;
auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
std::cout << "sum up = " << sum_up << '\n';
std::cout << "sum down = " << sum_down << '\n';
std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus\n";
std::cout << "Ave. Down Memory = "<< time_down/(num_repititions * 1000) << " mus"
<< std::endl;
}
return 0;
}
Ambos sum_abs_up e sum_abs_down fazer a mesma coisa e são cronometradas eles mesma maneira com a única diferença sendo que sum_abs_up sobe memória enquanto sum_abs_down vai para baixo memória. Eu mesmo passar vec por referência para que ambas as funções acessar as mesmas posições de memória. No entanto, sum_abs_up é consistentemente mais rápido que sum_abs_down. Dê-lhe um prazo-se (I compilado com g ++ O3).
FYI vec_original está lá para a experimentação, para torná-lo fácil para mim sum_abs_up mudança e sum_abs_down de uma forma que os torna vec alter enquanto não permitindo que estas alterações afetam tempos futuros.
É importante notar quão apertado o laço que eu sou o timing é. Se o corpo de um laço é grande, então ele provavelmente não importa se o seu iterador vai para cima ou para baixo memória desde o tempo que leva para executar o corpo do circuito provavelmente vai dominar completamente. Além disso, é importante mencionar que com alguns laços raros, a descer memória às vezes é mais rápido do que ir até ele. Mas mesmo com esses laços é raramente o caso que subir sempre foi mais lento do que ir para baixo (ao contrário de loops que sobem de memória, que são muito frequentemente sempre mais rápido do que os loops de baixo-memória equivalentes; um pequeno punhado de vezes que eles eram ainda 40 +% mais rápido).
O ponto é, como regra geral, se você tem a opção, se o corpo do laço é pequeno, e se há pouca diferença entre ter o seu ciclo subir memória em vez de para baixo, então você deve ir para cima memória.
