assyrium | Code :
- #include <iostream.h>
- #include <cstdlib>
- unsigned int N = 5000000;
- const unsigned long SEED = 17L;
- class Position **PositionsRedondantesG;
- int NbPositionsG;
- template <class T> class noeud
- {
- private:
- noeud *fg;
- noeud *fd;
- int dq;//desequilibre du noeud
- int Nb;//compteur du nombre d'occurence de l'element ajoute
- T Info;
-
- public:
- T &RInfo(){return Info;}
- noeud<T> *Ajouter(T &Info, noeud *&Lien, int &G);
- //noeud<T> *Ajouter(noeud<T> &Info, noeud *&Lien, int &G);
- void RotationDroite(noeud *&N);
- void RotationGauche(noeud *&N);
- void RotationGaucheDroite(noeud *&N);
- void RotationDroiteGauche(noeud *&N);
- void Reequilibrer(noeud *&Lien, int des);
- void Vider();
- noeud(T &Info)
- {
- fg = NULL;
- fd = NULL;
- noeud::Info = Info;
- Info.SetParent(this);
- Nb = 1;
- dq = 0;
- };
- };
- template <class T> class arbre
- {
- private:
- int Haut;
- int NbElmt;
- public:
- noeud<T> *Racine;
- noeud<T> *Ajouter(T &Info);
- arbre();
- ~arbre();
- };
- class Position
- {
- private:
- unsigned long long n;
- int Nb;
- unsigned int Positions[10];
- void *Contenant;
- public:
- void SetPos(int Pos){Positions[0] = Pos;};
- void SetN(unsigned long long N){n = N;};
- unsigned long long GetN(){return n;};
- int GetNb(){return Nb;};
- int GetPos(int i){return Positions[i];};
- void SetParent(void *C) {Contenant = C;};
- void *GetParent(){return Contenant;};
-
- Position()
- {
- Nb = 0;
- n = 0;
- }
-
- void Afficher()
- {
- cout << "Nb "<<n<<" -> "<< Nb <<" fois ";
- for (int i = 0; i < Nb; i++)
- cout <<"["<<Positions[i]<<"] ";
- cout <<endl;
- }
-
- Position &operator = (Position &p)
- {
- Positions[Nb++] = p.Positions[0];
- n = p.n;
- }
-
- bool operator == (Position &p)
- {
- if (p.n == n)
- {
- if (Nb == 1) PositionsRedondantesG[NbPositionsG++] = this;
- Positions[Nb++] = p.Positions[0];
- return true;
- }
- return false;
- }
-
- bool operator < (Position &p)
- {
- if (n < p.n) return true;
- return false;
- }
-
- bool operator > (Position &p)
- {
- if (n > p.n) return true;
- return false;
- }
- };
- template <class T> void noeud<T>::Vider()
- {
- if (fd) fd->Vider();
- if (fg) fg->Vider();
- if (Nb <= 1) delete this;
- else Info.Afficher();
- }
- template <class T> void noeud<T>::Reequilibrer(noeud *&Lien, int des)
- {
- noeud *FG=NULL, *FD = NULL;
- bool DoubleRotation = false;
- if (des > 0)
- {
- if (fg->dq >= 0)
- {
- RotationDroite(Lien);
- if (Lien->dq == 1) Lien->fd->dq = Lien->dq = 0;
- else Lien->dq = -1, Lien->fd->dq = 1;
- }
- else
- {
- RotationGaucheDroite(Lien);
- DoubleRotation = true;
- FG = Lien->fg;
- FD = Lien->fd;
- }
- }
- else
- {
- if (fd->dq <= 0)
- {
- RotationGauche(Lien);
- if (Lien->dq == -1) Lien->fg->dq = Lien->dq = 0;
- else Lien->fg->dq = -1, Lien->dq = 1;
- }
- else
- {
- RotationDroiteGauche(Lien);
- DoubleRotation = true;
- FG = Lien->fd;
- FD = Lien->fg;
- }
- }
- if (DoubleRotation)
- {
- switch(Lien->dq)
- {
- case 1: FG->dq = 0;
- FD->dq = -1;
- break;
- case -1:FG->dq = 1;
- FD->dq = 0;
- break;
- case 0: FG->dq = FD->dq = 0;
- }
- Lien->dq = 0;
- }
- }
- template <class T> noeud<T> *noeud<T>::Ajouter(T &Info, noeud *&Lien, int &G)
- {
- noeud<T> *R;
- if (Info > noeud::Info)
- {
- if (fd) R = fd->Ajouter(Info, fd, G);
- else R = fd = new noeud(Info), G = 1;
- if (G) dq--;
- if (dq >= 0) G = 0;
- if (dq == -2) Reequilibrer(Lien, dq), G=0;
- }
- else if (Info < noeud::Info)
- {
- if (fg) R = fg->Ajouter(Info, fg, G);
- else R = fg = new noeud(Info), G = 1;
- if (G) dq++;
- if (dq <= 0) G = 0;
- if (dq == 2) Reequilibrer(Lien, dq), G=0;
- }
- else
- {
- noeud::Info==Info;
- Nb++;
- return NULL;
- }
- return R;
- }
- template <class T> void noeud<T>::RotationDroite(noeud *&Q)
- {
- noeud *P = Q->fg;
- Q->fg = P->fd;
- P->fd = Q;
- Q = P;
- }
- template <class T> void noeud<T>::RotationGauche(noeud *&P)
- {
- noeud *Q = P->fd;
- P->fd = Q->fg;
- Q->fg = P;
- P = Q;
- }
- template <class T> void noeud<T>::RotationGaucheDroite(noeud *&R)
- {
- RotationGauche(R->fg);
- RotationDroite(R);
- }
- template <class T> void noeud<T>::RotationDroiteGauche(noeud *&R)
- {
- RotationDroite(R->fd);
- RotationGauche(R);
- }
- template <class T> noeud<T> *arbre<T>::Ajouter(T &Info)
- {
- int G = 0;
- noeud<T> *N;
- if (Racine == NULL)
- {
- Racine = new noeud<T>(Info);
- NbElmt++;
- return Racine;
- }
- else
- {
- N = Racine->Ajouter(Info, Racine, G);
- if (N) NbElmt++;
- return N;
- }
- }
- template <class T> arbre<T>::arbre()
- {
- NbElmt = 0;
- Racine = NULL;
- Haut = 0;
- }
- template <class T> arbre<T>::~arbre()
- {
- if (Racine) Racine->Vider();
- }
-
- inline void alea(unsigned long &rand){
- static unsigned long r = SEED;
- rand = r = 1664525UL * r + 1013904223UL;
- }
-
- int remplit_t(char *Tampon, const int N)
- {
-
- unsigned long r;
- char buf[20] = "";
-
- for (int i = 0; i < N; i+= 5)
- {
- do alea(r); while (r < 10000UL);
- sprintf(&Tampon[i], "%u", r);
- }
- }
-
- int lmin = 7, lmax = 15;
-
- int main(int argc, char *argv[])
- {
- char *Tampon;
- unsigned long long f;
- char Tmp;
- unsigned int i, j, k, t, v;
- int Nb;
- int PosTmp;
- int NbPositionsTmp;
- Position ** PositionsTmp;
- PositionsRedondantesG = new Position *[N];
- NbPositionsG = 0;
-
- Tampon = new char[N];
- remplit_t(Tampon, N);
- arbre<Position> *Arbre = new arbre<Position>;
- Position Temp;
- j = 7;
- for (i = 0; i < N-j; i++)
- {
- Tmp = Tampon[i+j];
- Tampon[i+j] = 0;
- f = atoll(&Tampon[i]);
- Tampon[i+j] = Tmp;
- Temp.SetN(f);
- Temp.SetPos(i);
- Arbre->Ajouter(Temp);
- }
- for (t = 8; t <= 15; t++)
- {
- cout <<"nombres de "<<t-1<<" chiffres --------------" <<endl;
- delete Arbre;
- Arbre = new arbre<Position>;
-
- NbPositionsTmp = NbPositionsG;
- PositionsTmp = PositionsRedondantesG;
-
- if (NbPositionsTmp)
- {
- PositionsRedondantesG = new Position *[NbPositionsTmp];
- NbPositionsG = 0;
-
- for (i = 0; i < NbPositionsTmp; i++)
- {
- Nb = PositionsTmp[i]->GetNb();
-
- for (j = 0; j < Nb; j++)
- {
- PosTmp = PositionsTmp[i]->GetPos(j);
-
- if (N - PosTmp > t)
- {
- Tmp = Tampon[PosTmp+t];
- Tampon[PosTmp+t] = 0;
- f = atoll(&Tampon[PosTmp]);
- Tampon[PosTmp+t] = Tmp;
- Temp.SetN(f);
- Temp.SetPos(PosTmp);
- Arbre->Ajouter(Temp);
- }
- }
- }
- for (i = 0; i < NbPositionsTmp; i++)
- delete (noeud<Position> *) PositionsTmp[i]->GetParent();
- delete PositionsTmp;
- }
- }
- cout <<"nombres de "<<t-1<<" chiffres --------------" <<endl;
- delete Arbre;
- if (NbPositionsTmp)
- {
- for (i = 0; i < NbPositionsTmp; i++)
- delete (noeud<Position> *) PositionsTmp[i]->GetParent();
- delete PositionsTmp;
- }
- delete [] Tampon;
- return EXIT_SUCCESS;
- }
|
il est vrai que mon cas est très limité au problème (j'ai juste pris les données du problème). Si on veut passer à un n indéfini ou des caractères, il suffit de faire une classe qui récupère m paquets de 64bits (qui peuvent être convertis à partir de caractères sur leur code ascii), et de surdéfinir les opérateurs de comparaison qui compareront un ensemble de paquet.
Je conçois que ce n'est pas réutilisable, mais il fallait préciser que n pouvait augmenter au delà de 15... Cependant, les modifications sont très vite faites. Ptet que si j'ai le temps, je le ferai. De plus, je viens de penser à une méthode qui mélangerait table de hachage et arbres. La table de hachage servant d'index dans l'arbre, réduirait la complexité d'insertion (et de recherche). Par rapport à ton exemple, je pense qu'il manque d'efficacité par rapport à la fonction de hachage qui est trop compliquée par rapport aux données. Il faudrait plutot faire une table de hachage avec 10 millions d'entrées environ et trouver une fonction de répartition (la fction de hachage) qui suive une loi normale... Mais bon, c'est facile à dire, et plus difficile à trouver la fonction de répartition. Surtout que cette dernière dépend des données qui dans notre cas ne sont pas connues à l'avance.
Mais en trichant, tu pourrais calculer les distributions des répétitions pour en déduire la fonction de répartition adéquate... mais ça serait adapté uniquement à ton jeu de données. Sinon,il existe un outil gnu qui permet de calculer une fonction de hachage à partir des données, mais je ne me souviens plus de ce que c'est. Je cherche, et je le dis cet aprèm. |
).
Au lieu de te laisser abattre, tu devrais plutôt donner des pistes pour améliorer les choses dans ce cas-ci.
