Como verificar a eficiência dessas 2 funções em C++? – c++ loop desempenho
Pergunta:
Como determinar qual é a melhor escolha dentre estas duas funções para implementação?
1:
int X(int x){
if(x<=0)
return 0;
return(x + X(x-1));
}
2:
int Y(int x){
int soma=0;
for(int i=0;i<=x;++i)
soma+=i;
return soma;
}
Como determinar as equações de complexidade e resolvê-las? Ou há outro método?
Autor da pergunta HeraldOfVegas
No geral, as respostas até o momento tratam a mensuração da eficiência em termos práticos.
Vou dar uma resposta em termos teóricos, já que você faz duas perguntas: Como determinar as equações de complexidade e se há outro método.
Para responder a primeira pergunta, em primeiro lugar recomendo um livro introdutório de algoritmos que ensine notação Big-O.
Os livros que recomendo são:
- Algoritmos: Teoria e Prática – Conhecido internacionalmente, particularmente só tive acesso à versão em inglês.
- Algorithms Unlocked – Não tive acesso, mas é bem recomendado por ser uma versão menos longa do livro anterior. Escrito pelo mesmo autor renomado.
- Schaum’s Outline of Discrete Mathematics – Gosto deste livro por ser bem direto, mais apropriado pra quem não é iniciante talvez. Não exatamente focado em algoritmos, abrange várias áreas importantes das ciências da computação (particularmente sinto ser até mais acessível que “Algoritmos: Teoria e Prática” em certos pontos no tocante a algoritmos).
Vou reduzir a análise em miúdos, de forma não rigorosa, sem envolver loop invariants, etc.
Primeiro o mais fácil de analisar, o caso 2.
Este caso consiste em apenas um loop que repete uma operação de complexidade O(1). A quantidade de repetições é diretamente proporcional ao valor de entrada da função. Se o argumento x for N, então o loop será repetido N vezes. Fora o loop, o corpo da função só tem outras operações de complexidade O(1):
int Y(int x) { // O(1)
int soma=0; // O(1)
// O(1) O(1) O(1)
for( int i=0; i<=x; ++i )
soma+=i; // O(1)
// O() do loop = O(x) == O(1) + x*O(1) + x*O(1) + x*O(1)
return soma; // O(1)
}
// O() da função = O(x) == O(1) + O(1) + O(x) + O(1)
Portanto esta função tem complexidade O(N) no tempo. Nota-se que esta função realiza seu cálculo com uma quantidade fixa de variáveis locais somente, portanto ela é O(1) no espaço usado (ou seja, não precisa de mais memória dependendo da entrada).
O primeiro caso é uma função recursiva, e a análise de complexidade se torna recursiva também. Existe uma teoria sólida para isto, mas irei me ater a uma
explicação simplória.
Note que, todas as operações no corpo da função, exceto a própria chamada recursiva, são O(1). As chamadas recursivas ocorrerão até que se chegue a condição de término. Nota-se que para uma entrada x = N, ocorreram N chamadas. Dado que em cada chamada, fora a chamada recursiva, são realizadas operações O(1), então a complexidade no tempo desta função também é O(N).
A complexidade no espaço desta função difere do caso 2. Pelo fato de ser uma função recursiva cujo resultado precisa ser agregado como uma soma no final, ela não é uma função tail-recursive, e portanto não é possível que o compilador otimize sua função utilizando esta técnica.
Dado que tail-recursion não é possível, a cada chamada recursiva é preciso que se empilhe na pilha de chamada um número fixo de dados (argumentos da função, endereço de retorno, etc). Ou seja, para N chamadas, ocorreram Nempilhamentos de dados de um tamanho determinado, portanto a função é O(N) no espaço que utiliza também.
Respondendo à segunda pergunta: Há outro método?
Você tem duas soluções para o problema, uma é O(N) no tempo e O(N) no espaço, uma é O(N) no tempo e O(1) no espaço.
Uma alternativa seria procurar uma solução cuja complexidade não dependa do valor de entrada, será que é possível uma solução O(1) no tempo e O(1) no espaço?
Note que:
- y = 1 + 2 + 3 … + (x – 2) + (x – 1) + x
- y – x * x = (1 – x) + (2 – x) + (3 – x) … + [(x – 2) – x] + [(x – 1) – x] + (x – x)
- -(y – x * x) = (x – 1) + (x – 2) + (x – 3) … + 2 + 1 + 0
- x * x – y = 1 + 2… + (x – 3) + (x – 2) + (x – 1)
- x * x – y = y – x
- x * x + x = 2y
- y = x * (x + 1) / 2
Desta formula (uma dedução básica da soma dos elementos de uma progressão aritmética), é possível obter o valor da soma a partir do valor de entrada com complexidade O(1), ou seja, sem loops.
Então o método mais eficiente seria:
int Z(int x) { // O(1)
return (x * (x + 1)) / 2; // O(1)
}
(Se você já se perguntou na vida onde que iria usar PA e PG ensinado na escola, tá aí 😉 )
Se você quisesse ser mais eficiente ainda, com C++11 poderia declarar a função como
constexpr.
constexpr int Z(int x) {
return (x * (x + 1)) / 2;
}
Assim, a maioria dos compiladores que suporta C++11 faria o cálculo da soma em tempo de compilação, incorrendo em nenhum cálculo em tempo de execução, quando o argumento passado for uma constante. Caso o argumento não seja uma constante (i.e. um valor de tempo de execução), a função obtém a mesma eficiência de uma versão inline.
Melhorando o desempenho:
No g++ existe a flag -Ofast que faz várias modificações durante a fase de compilação do seu algoritmo e, na maioria das vezes, ele fica muito mais eficiente!
Já reduzi execuções que duravam 20 minutos para menos de 1!
Segue um exemplo:
g++ main.cpp -o App.exe -Ofast
Faça o teste, calcule o tempo de execução conforme as outras respostas sugerem e tire suas próprias conclusões!
No Windows
#include <stdio.h>
#include <windows.h>
int main() {
int i, j;
int inicio, final, tmili;
inicio = GetTickCount();
/* Substitua o for a seguir pelo trecho de código
cujo tempo de execução deverá ser medido. */
for (j = 0; j < 10; j ++)
for (i = 0; i < 1387634340; i ++);
final = GetTickCount();
tmili = final - inicio;
printf("tempo decorrido: %dn", tmili);
return 0;
}}
No Linux
#include <stdio.h>
#include <sys/time.h>
int main() {
int i, j;
struct timeval inicio, final;
int tmili;
gettimeofday(&inicio, NULL);
/* Substitua o for a seguir pelo trecho de código
cujo tempo de execução deverá ser medido. */
for (j = 0; j < 10; j ++)
for (i = 0; i < 1387634340; i ++);
gettimeofday(&final, NULL);
tmili = (int) (1000 * (final.tv_sec - inicio.tv_sec) + (final.tv_usec - inicio.tv_usec) / 1000);
printf("tempo decorrido: %dn", tmili);
return 0;
}
Como calcular a eficiência eu não sei mas posso testá-la:
#include <stdio.h>
#include <time.h>
#include <cstdint>
#ifdef WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#include <ctime>
#endif
/* Returns the amount of milliseconds elapsed since the UNIX epoch. Works on both
* windows and linux. */
uint64_t get_time()
{
#ifdef _WIN32
/* Windows */
FILETIME ft;
LARGE_INTEGER li;
/* Get the amount of 100 nano seconds intervals elapsed since January 1, 1601 (UTC) and copy it
* to a LARGE_INTEGER structure. */
GetSystemTimeAsFileTime(&ft);
li.LowPart = ft.dwLowDateTime;
li.HighPart = ft.dwHighDateTime;
uint64_t ret = li.QuadPart;
ret -= 116444736000000000LL; /* Convert from file time to UNIX epoch time. */
ret /= 10000; /* From 100 nano seconds (10^-7) to 1 millisecond (10^-3) intervals */
return ret;
#else
/* Linux */
struct timeval tv;
gettimeofday(&tv, NULL);
uint64_t ret = tv.tv_usec;
/* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
ret /= 1000;
/* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
ret += (tv.tv_sec * 1000);
return ret;
#endif
}
int X(int x){
if(x<=0)
return 0;
return(x + X(x-1));
}
int Y(int x){
int soma=0;
for(int i=0;i<=x;++i)
soma+=i;
return soma;
}
int main(void) {
uint64_t startTime, endTime, timeElapsed;
startTime = get_time();
X(300000);
endTime = get_time();
timeElapsed = endTime - startTime;
printf("Tempo decorrido: %dn", timeElapsed);
startTime = get_time();
Y(300000);
endTime = get_time();
timeElapsed = endTime - startTime;
printf("Tempo decorrido: %dn", timeElapsed);
return 0;
}
Coloquei no GitHub para referência futura.
Fiz um teste e a segunda foi claramente muito mais eficiente, pelo menos 7 vezes mais rápida. Não consegui postar em nenhum site online que permitisse executar corretamente. Onde executou não dá para compartilhar.
A função de medição foi retirada dessa resposta no SO.
Related Posts:
