[Programa] Gerar 'N' de chaves do euromilhoes e ver qual é que saiu mais

[pikax]

Boas

Já à algum tempo um amigo meu pediu-me para ver se eu conseguia criar um programa que gerasse por exemplo 1milhão de chaves, e verificar qual foi a que saiu mais(apesar que 1milhão é muito pouco).

É um programa relativamente simples(se nos abstrairmos da memória, que poderá consumir), tentei livrar-me de excesso de memória que ficava sem ser utilizada(acho que não memoria desnecessária).

Para quem quiser utilizar threads(básicas) em objectos em windows basta utilizar a class Thread(que tenho no código) e depois utilizar herança de classes.

NOTA: O programa está feito para windows, por causa da thread, se apagar-mos a class e tirar-mos no inicio da main a thread, deverá funcionar em linux

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include <time.h>
#include<cstdio>
#include<windows.h>

typedef unsigned short int uint;


using namespace std;
class chave;

vector<chave> koizo;
vector<uint> numeros;
vector<uint> estrelas;



//random generator function:
ptrdiff_t random12 (ptrdiff_t i) { return rand()%i;}

// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = random12;

class Thread //class para termos threads no windows
{
    public:
        Thread();
        void Begin();
        virtual DWORD creatThread();
    private:
        HANDLE  d_threadHandle;
        DWORD   d_threadID;
};

/*************************************************************/
static DWORD WINAPI cCreatThread( Thread *pThis )
{
    return pThis->creatThread();
  return pThis->creatThread();
}
/*************************************************************/


Thread::Thread()
{
    d_threadID = 0;
    d_threadHandle = NULL;
}

void Thread::Begin()
{
    d_threadHandle = CreateThread( NULL,
                                 0,
                                 (LPTHREAD_START_ROUTINE)cCreatThread,
                                 this,
                                 0,
                                 (LPDWORD)&d_threadID );
    if(d_threadHandle==NULL)
        cerr<<"Falhou a criação da Thread\n";//throw Error("Falhou a criação da Thread\n");

}


DWORD Thread::creatThread()
{
    return 0;
}


class fps: public Thread
{
public:
    fps(){last_visited=1;}
    DWORD creatThread()
    {
        unsigned int xenx=1;
        while(xenx<=MAX_KOIZO)
        {
            Sleep(30000);
            xenx=koizo.size();
            cout<<"palavras por 30 segundos:"<<(xenx-last_visited)<<endl;

            last_visited=xenx;
        }
        return 0;
    }
    int MAX_KOIZO;
private:
    unsigned int last_visited;
};


class chave
{
    public:
    	chave(){}
    	chave(uint n1,uint n2,uint n3,uint n4,uint n5,uint e1,uint e2):m_n1(n1),m_n2(n2),m_n3(n3),m_n4(n4),m_n5(n5),m_e1(e1),m_e2(e2),repeticao(1){}

    	unsigned int repeticao;
    	uint m_n1;
    	uint m_n2;
    	uint m_n3;
    	uint m_n4;
    	uint m_n5;

    	uint m_e1;
    	uint m_e2;

};
unsigned long int kkkoasdi=0;
bool comp();

inline bool operator==(const chave& ch1, const chave& ch2)
    	{
            if(ch1.m_n1!=ch2.m_n1)
                return false;
            if(ch1.m_n2!=ch2.m_n2)
                return false;
            if(ch1.m_n3!=ch2.m_n3)
                return false;
            if(ch1.m_n4!=ch2.m_n4)
                return false;
            if(ch1.m_n5!=ch2.m_n5)
                return false;
            if(ch1.m_e1!=ch2.m_e1)
                return false;
            if(ch1.m_e2!=ch2.m_e2)
                return false;

            return true;
    	}

bool myfunction (short int i,short int j) { return (i<j); }


chave gera_chave()
{
    vector<uint>::iterator it;

    uint temp;

    vector<uint> v_chaves;

    v_chaves.push_back(gera_random(50));


    for(int i=0;i<4;i++)
    {
        do
        {
            random_shuffle(numeros.begin(),numeros.end(),p_myrandom);
            temp=numeros.back();
            it = find (v_chaves.begin(), v_chaves.end(), temp);
        }while(it!=v_chaves.end());
        v_chaves.push_back(temp);
    }

    vector<uint> v_est;
    for(int i=0;i<2;i++)
    {
        do
        {
            random_shuffle(estrelas.begin(),estrelas.end(),p_myrandom);
            temp=estrelas.back();
            it = find (v_est.begin(), v_est.end(), temp);
        }while(it!=v_est.end());
        v_est.push_back(temp);
    }

    sort(v_chaves.begin(),v_chaves.end());
    sort(v_est.begin(),v_est.end());

    return chave(v_chaves[0],v_chaves[1],v_chaves[2],v_chaves[3],v_chaves[4],v_est[0],v_est[1]);
}
bool myfn(chave i, chave j) { return i.repeticao<j.repeticao; }

void preencher_vectores()
{
    for(uint i=0;i<50;i++)
        numeros.push_back(i+1);
    for(uint i=0;i<9;i++)
        estrelas.push_back(i+1);
}

int main()
{
    preencher_vectores();

    time_t mytime = time(0);

    int MAX_KOIZO;

    cout<<"Quantas chaves quer gerar:";
    cin>>MAX_KOIZO;

    chave temp;
    vector<chave>::iterator it;

    fps *koizossdf;
    koizossdf=new fps();
    koizossdf->MAX_KOIZO=MAX_KOIZO;
    koizossdf->Begin();

    int a;
    bool flag=false;
    for(int i=0;i<MAX_KOIZO;i++)
    {
        temp=gera_chave();
        it = find (koizo.begin(), koizo.end(), temp);

        if(it!=koizo.end())
        {
            a=(int(it-koizo.begin()));
            koizo[a].repeticao++;
        }
        else
            koizo.push_back(temp);

        if(((i+1)*100/MAX_KOIZO)%25==0 && ((i+1)*100/MAX_KOIZO)>0 && flag==false)
        {
            cout<<"\t"<<i+1<<"/"<<MAX_KOIZO<<"     "<<(i+1)*100/MAX_KOIZO<<"%"<<endl;
            flag=true;
        }
        else
        {
            if(((i+1)*100/MAX_KOIZO)%25==1)
                flag=false;
        }
    }
    cout<<"----------------------------"<<endl<<endl;

    it=max_element(koizo.begin(),koizo.end(),myfn);

    cout<<"a chave vencedora e:"<<endl;
    int i=it-koizo.begin();

    cout<<koizo[i].m_n1<<endl;
    cout<<koizo[i].m_n2<<endl;
    cout<<koizo[i].m_n3<<endl;
    cout<<koizo[i].m_n4<<endl;
    cout<<koizo[i].m_n5<<endl;
    cout<<"estrelas:"<<endl;
    cout<<koizo[i].m_e1<<endl;
    cout<<koizo[i].m_e2<<endl;
    cout<<endl<<"com "<<koizo[i].repeticao<<" iguais"<<endl;


    printf("Demorou %d segundos a gerar %d chaves\n", time(0)-mytime,MAX_KOIZO);
    cin>>i;
}

O código foi feito há pressa, os nomes das variáveis não são as melhores B) e o código está lento para grandes valores(maior de n*10^1000)

[KTachyon]

Podes utilizar chars para as chaves, visto que não necessitas de valores maiores que 50. Assim poupas 50% da memória.

EDIT: Short ints já poupa 50% em relação a ints, mas, como tens o tipo char que te permite guardar valores até 256, ocupando apenas um byte,...

[pikax]

Podes utilizar chars para as chaves, visto que não necessitas de valores maiores que 50. Assim poupas 50% da memória.

EDIT: Short ints já poupa 50% em relação a ints, mas, como tens o tipo char que te permite guardar valores até 256, ocupando apenas um byte,...

Esqueci-me completamente que char converte-se facilmente em int 

e tive olhar melhor para o código e vi que tem uns problemas  :dontgetit:

//class fps
class fps: public Thread
{
public:
    fps(){last_visited=1;actived=true;}
    DWORD creatThread()
    {
        unsigned int xenx=1;
        while(actived)
        {
            Sleep(30000);
            xenx=koizo.size();
            cout<<"palavras por 30 segundos:"<<(xenx-last_visited)<<endl;

            last_visited=xenx;
        }
        return 0;
    }
    int MAX_KOIZO;
    bool actived;//variavel de controlo, para depois que o programa
private:
    unsigned int last_visited;
};

//função gera_chave()

chave gera_chave()
{
    vector<char>::iterator it;

    char temp;

    vector<char> v_chaves;

    for(int i=0;i<5;i++)
    {
        do
        {
            random_shuffle(numeros.begin(),numeros.end(),p_myrandom);
            temp=numeros.back();
            it = find (v_chaves.begin(), v_chaves.end(), temp);
        }while(it!=v_chaves.end());
        v_chaves.push_back(temp);
    }

    vector<char> v_est;
    for(int i=0;i<2;i++)
    {
        do
        {
            random_shuffle(estrelas.begin(),estrelas.end(),p_myrandom);
            temp=estrelas.back();
            it = find (v_est.begin(), v_est.end(), temp);
        }while(it!=v_est.end());
        v_est.push_back(temp);
    }

    sort(v_chaves.begin(),v_chaves.end());
    sort(v_est.begin(),v_est.end());

    return chave(v_chaves[0],v_chaves[1],v_chaves[2],v_chaves[3],v_chaves[4],v_est[0],v_est[1]);
}

//int main()

int main()
{
    preencher_vectores();
srand ( time(NULL) );//tinha-me esquecido completamente disto

    int MAX_KOIZO;

    cout<<"Quantas chaves quer gerar:";
    cin>>MAX_KOIZO;
time_t mytime = time(0);
    chave temp;
    vector<chave>::iterator it;

    fps *koizossdf;
    koizossdf=new fps();
    koizossdf->MAX_KOIZO=MAX_KOIZO;
    koizossdf->Begin();

    int a;
    bool flag=false;
    for(int i=0;i<MAX_KOIZO;i++)
    {
        temp=gera_chave();
        it = find (koizo.begin(), koizo.end(), temp);

        if(it!=koizo.end())
        {
            a=(int(it-koizo.begin()));
            koizo[a].repeticao++;
        }
        else
            koizo.push_back(temp);

        if(((i+1)*100/MAX_KOIZO)%25==0 && ((i+1)*100/MAX_KOIZO)>0 && flag==false)
        {
            cout<<"\t"<<i+1<<"/"<<MAX_KOIZO<<"     "<<(i+1)*100/MAX_KOIZO<<"%"<<endl;
            flag=true;
        }
        else
        {
            if(((i+1)*100/MAX_KOIZO)%25==1)
                flag=false;
        }
    }
    koizossdf->actived=false;
    cout<<"----------------------------"<<endl<<endl;

    it=max_element(koizo.begin(),koizo.end(),myfn);

    cout<<"a chave vencedora e:"<<endl;

    cout<<(int)(*it).m_n1<<endl;
    cout<<(int)(*it).m_n2<<endl;
    cout<<(int)(*it).m_n3<<endl;
    cout<<(int)(*it).m_n4<<endl;
    cout<<(int)(*it).m_n5<<endl;
    cout<<"estrelas:"<<endl;
    cout<<(int)(*it).m_e1<<endl;
    cout<<(int)(*it).m_e2<<endl;
    cout<<endl<<"com "<<(*it).repeticao<<" iguais"<<endl;

cout<<"Demorou "<<time(0)-mytime<<" segundos a gerar "<<MAX_KOIZO<<" chaves"<<endl
	<<"Houve "<<MAX_KOIZO-koizo.size()<<" chaves diferentes"<<endl;

    cin>>MAX_KOIZO;
}