Ir para conteúdo
Fórum Script Brasil
  • 0

Reduzir o tempo do algoritmo(otimização)


Samuel Rios

Pergunta

Fala pessoal!

Bem, escrevi um algoritmo em c++ para a solução de um problema mas acontece que o tempo de execução dele está acima da média. Tentei pensar o que poderia estar causando tal situação e reescrevi o código. Sucedeu que na segunda tentativa eu consegui reduzir tempo, mas ainda assim ele continua acima da média.
O problema é o seguinte: Dado um vetor(que tem N elementos inteiros digitados pelo usuário), imprimir os três maiores números do mesmo em ordem decrescente.

Segue os dois algoritmos:

01- Time: @45:30

#include <iostream>
#include <vector>
using namespace std;
int main
(){
    int N, c, aux, i, j;
    cin >> N;
    vector <int> contri;
    for(int i=0; i<N; i++){
        cin >> c;
        contri.push_back(c);
    }
    for(i=0; i<3; i++){
            aux=0;
            for(j=i+1; j<N; j++){
                    if(contri[aux]<contri[j]){
                            aux=j;
                    }
            }
            cout << contri[aux] << endl;
            contri[aux]=-1;
    }
}

 

02- Time: @33:32

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main
(){
    int N;
    cin >> N;
    vector <int> contri;
    for(int i=0; i<N; i++){
        int c;
        cin >> c;
        contri.push_back(c);
    }
    stable_sort(contri.begin(), contri.end(), less<int>());
    cout << contri[N-1] << endl;
    cout << contri[N-2] << endl;
    cout << contri[N-3] << endl;
}



Todos da minha sala estão dando uma média de time: @20:30. Poderiam me dar dicas de como posso otimizar mais o meu algorímo? Não só esse, mas os meus próximos. Agradeço!

Editado por Samuel Rios
Link para o comentário
Compartilhar em outros sites

4 respostass a esta questão

Posts Recomendados

  • 0

Olá, tudo bem?

 

Então, você está armazenado todos os N-valores, quando na verdade se quer apenas 3 dos N. Logo a medida que os valores vão entrando você já vai colocando eles em 3 variáveis, e selecionado sempre o maior valor s depois transferindo para as outras sempre que encontras um maior ainda. Por exemplo:

x E [1, 2, 3, 4, 5, 6] Se x  >  c então c =  x, b =  c, a = b, se não então

x E [1, 2, 3, 4, 5, 6] Se x  >  b então b =  x, a =  b, se não então

x E [1, 2, 3, 4, 5, 6] Se x  >  a então a =  x.

 

No fim imprima: a, b , c.

Entendeu como é mais simples que isso que você fez.

O.k. !? Tchau.

Link para o comentário
Compartilhar em outros sites

  • 0
Em 05/09/2018 at 09:58, britivaldo disse:

Olá, tudo bem?

 

Então, você está armazenado todos os N-valores, quando na verdade se quer apenas 3 dos N. Logo a medida que os valores vão entrando você já vai colocando eles em 3 variáveis, e selecionado sempre o maior valor s depois transferindo para as outras sempre que encontras um maior ainda. Por exemplo:

x E [1, 2, 3, 4, 5, 6] Se x  >  c então c =  x, b =  c, a = b, se não então

x E [1, 2, 3, 4, 5, 6] Se x  >  b então b =  x, a =  b, se não então

x E [1, 2, 3, 4, 5, 6] Se x  >  a então a =  x.

 

No fim imprima: a, b , c.

Entendeu como é mais simples que isso que você fez.

O.k. !? Tchau.

Cara, segui tua recomendação, mas isso aumentou 3x o tempo do algoritmo. Meu professor sempre comentou que if e else custa muito caro, quanto mais pudermos diminuir o uso, melhor! O computador meio que "para" para fazer todas as comparações e isso custa mais tempo. Não foi uma solução :/

Link para o comentário
Compartilhar em outros sites

  • 0

Não entendi, seu professor disse que o processo para e é mais lento que gravar e depois aplicar uma ordenação. Por conta do IF Else ser mais lento e você notou um acréscimo de 3x.

Então depende de como está sendo feito esse teste, eu aqui fiz assim porque penso que assim deve ser:

int main()
    {
    clock_t begin =  clock();

    vector <int> contri;
    int N =  10000000;
      
    for(int i =  0; i < N; ++i)
        {
        contri.push_back(i);
        }

    stable_sort(contri.begin(), contri.end(), less<int>());

    cout << contri[N-1] << endl;
    cout << contri[N-2] << endl;
    cout << contri[N-3] << endl;

    clock_t end = clock();
    double time_spent =  (double)(end - begin) / CLOCKS_PER_SEC;
    cout << "Time taken to process : " << time_spent << endl;
    return 0; 
    }

O tempo: ~8.275 segundos.

O algoritmo que proponho, faz em: ~0.1 segundos.

 

Em 08/09/2018 at 15:19, Samuel Rios disse:

Não foi uma solução :/

Discordo!

Editado por britivaldo
Correção
Link para o comentário
Compartilhar em outros sites

  • 0
13 horas atrás, britivaldo disse:

Não entendi, seu professor disse que o processo para e é mais lento que gravar e depois aplicar uma ordenação. Por conta do IF Else ser mais lento e você notou um acréscimo de 3x.

Então depende de como está sendo feito esse teste, eu aqui fiz assim porque penso que assim deve ser:


int main()
    {
    clock_t begin =  clock();

    vector <int> contri;
    int N =  10000000;
      
    for(int i =  0; i < N; ++i)
        {
        contri.push_back(i);
        }

    stable_sort(contri.begin(), contri.end(), less<int>());

    cout << contri[N-1] << endl;
    cout << contri[N-2] << endl;
    cout << contri[N-3] << endl;

    clock_t end = clock();
    double time_spent =  (double)(end - begin) / CLOCKS_PER_SEC;
    cout << "Time taken to process : " << time_spent << endl;
    return 0; 
    }

O tempo: ~8.275 segundos.

O algoritmo que proponho, faz em: ~0.1 segundos.

 

Discordo!

Perdão, amigo!
Cometi um equívoco estúpido, o tempo que aparece lá no site é o tempo que eu demorei para submeter o algoritmo desde a liberação da lista. Então, a cada vez que eu enviava o código o tempo ia, obviamente, crescendo.
Não mostrei seu código ao meu professor, ele só deu essa pequena observação não generalizando. A má interpretação foi minha, como tenho dito.
Agora eu acredito que foi uma solução. Vlw!

Link para o comentário
Compartilhar em outros sites

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152k
    • Posts
      651,7k
×
×
  • Criar Novo...