Reduzir o tempo do algoritmo(otimização)

[Samuel Rios]

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 Setembro 5, 2018 por Samuel Rios

[britivaldo]

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.

[Samuel Rios]

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 :/

[britivaldo]

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 Setembro 11, 2018 por britivaldo
Correção

[Samuel Rios]

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!