C++

[Concours] Recherche de doublons dans une séquence

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 3 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [Concours] Recherche de doublons dans une séquence

el muchacho

Comfortably Numb

Reprise du message précédent :

xterminhate a écrit :

Bon, revennons à nos moutons !... le concours

El much -> tu as vérifié ton code parce que pour le moment, on a vraiment pas la meme sequence de départ !

Bon je revois mon code...

Message édité par el muchacho le 30-04-2004 à 22:49:41

Publicité

el muchacho

Comfortably Numb

Taz a écrit :

el muchacho : distribue un fichier avec la séquence, chaque élément séparé par un espace, le tout compréssé (et pas en zip/rar hein)

C'est inutile. Les chiffres de début et de fin sont bien suffisants.

xterminhate

Si vis pacem, para bellum.

L'idée de taz me parait bonne au passage, ca evite de trop se prendre la tête sur la génération de la séquence qui n'a rien a voir avec de la programmation C++ ! Au contraire ca pourrait être du pur C pour correctement coder ta formule (__int64).

Soit tu nous file le fichier de 5.000.000 octets qui va bien (sans espace si possible, mais bon je m'en fou).

---------------
Cordialement, Xterm-in'Hate...

xterminhate

Si vis pacem, para bellum.

Soit on prend mon code Il est pas si mauvais non en terme de C++ (taz?)

---------------
Cordialement, Xterm-in'Hate...

Taz

bisounours-codeur

xterminhate a écrit :

ben si j'avais la séquence ... j'ai tenté avec une hashmap< int, vector<position> >

el muchacho

Comfortably Numb

xterminhate a écrit :

Bon, c'est tout con, je viens de piger ce matin en me réveillant (c'est grâve, là, de rêver de C++). J'ai pas initialisé ma variablez statique.

il suffit donc de mettre : static unsigned long r = SEED.

Le code correct est donc :

Code :

#include <iostream>
#include <vector>
using namespace std;
const int N = 5000000;
const unsigned long SEED = 17UL;
inline void alea(unsigned long &rand){
static unsigned long r = SEED;
rand = r = 1664525UL * r + 1013904223UL;
}
int remplit_v(vector<char> &v, const int n)
{
unsigned long r;
char buf[20] = "";
vector<char> tmp;
v.reserve(n);
for (int i = 0; i < n; i+= 5)
{
do alea(r); while (r < 10000UL);
sprintf(buf, "%u", r);
tmp.assign(buf, &buf[sizeof(buf)]); // faute de mieux
copy(tmp.begin(), tmp.end(), back_inserter(v));
}
return v.size();
}

Si j'ajoute une fonction main comme :

Code :

int main(int argc, string argv[])
{
vector<char> vect;
remplit_v(vect, N); // genere un vecteur aleatoire
/////////////// VERIFICATION MANUELLE ////////////////////
unsigned long nn = 1664525UL * 17UL + 1013904223UL;
for (int i = 0; i < 8; i++){
cout << nn << "\n";
nn = 1664525UL * nn + 1013904223UL;
}
//////////////////////////////////////////////////////////
cout << "Genere un vecteur de " << vect.size() << " chiffres." << endl;
for (int i = 0; i < 40; ++i) cout << vect[i] ;
cout << endl;
for (int i = N-40; i < N; ++i) cout << vect[i] ;
cout << endl;
}

J'obtiens :

Citation :

1042201148
3524153451
1973856974
1276228565
3066622768
1429761231
2883449826
921854425
669737316
2398403955
Genere un vecteur de 5000000 chiffres.
1042235241197381276230666142972883492185
1675913308512872428215612116421983834693

Bon, sur ce, on va enfin pouvoir passer au morceau intéressant ! :na:

Message édité par el muchacho le 07-05-2004 à 21:09:46

el muchacho

Comfortably Numb

xterminhate a écrit :

Soit on prend mon code Il est pas si mauvais non en terme de C++ (taz?)

Ben il a un ch'ti problème.

Code :

std::string generation()
{
std::string alea;
std::string::size_type taille_sequence( alea.size() );
const unsigned long multiplier( 1664525UL );
const unsigned long addend( 1013904223UL );
unsigned long valeur( 17UL );
while( taille_sequence < 10 )
{
if( ( valeur = ( multiplier * valeur + addend ) ) > 9999UL )
{/*
std::ostringstream str;
str << valeur;
alea += str.str().substr(0,5);*/
cout << valeur << "\n";
taille_sequence++;
}
}
return alea;
}

donne la bonne séquence. La séquence que tu as donnée "saute" des valeurs.

Message édité par el muchacho le 01-05-2004 à 08:11:04

xterminhate

Si vis pacem, para bellum.

Bon c'est cool, je viens de compiler ton code et on trouve exactement la même séquence au final ! Enfin

On peut commencer, mais je garde mon code (il fait moins de warning dans gcc) par contre le mien tourne 5 fois moins vite (et m......).

Message édité par xterminhate le 01-05-2004 à 10:07:29

---------------
Cordialement, Xterm-in'Hate...

el muchacho

Comfortably Numb

Taz a écrit :

ben si j'avais la séquence ... j'ai tenté avec une hashmap< int, vector<position> >

Tiens oui, pas con, la hashmap. Probablement la meilleure solution.

xterminhate

Si vis pacem, para bellum.

Voila, le calcul est simple : j'aurai ma solution dans 28 jours a peu pres..... j'ai interet d'acheter un onduleur !

---------------
Cordialement, Xterm-in'Hate...

Publicité

souk

Tourist

avec un petit arbre de suffixes a la Ukkonen ca se fait pas bien ?

xterminhate

Si vis pacem, para bellum.

Suite au crash de ce WE, mon post a viré. Je le remets.

Avez vous trouvé un nombre de plus de 12 chiffres dans la séquence d'aléa qui se répete au moins une fois ?

---------------
Cordialement, Xterm-in'Hate...

el muchacho

Comfortably Numb

Pas eu le temps de continuer ce we. Mariage, tout ça. C'est bien les mariages, ça rappelle qu'il y a une vie à coté du pécé.
Question : les string sont-ils illimités en taille ? (est-ce tjrs le cas ?)

Message édité par el muchacho le 03-05-2004 à 21:49:48

xterminhate

Si vis pacem, para bellum.

Réponse normande : aussi limités que les vector ?!

Message édité par xterminhate le 03-05-2004 à 22:03:16

---------------
Cordialement, Xterm-in'Hate...

el muchacho

Comfortably Numb

xterminhate a écrit :

Suite au crash de ce WE, mon post a viré. Je le remets.

Avez vous trouvé un nombre de plus de 12 chiffres dans la séquence d'aléa qui se répete au moins une fois ?

Non. Voici la liste des nombres de 12 chiffres que j'ai trouvés :

Citation :

Séquences à 12 chiffres :
251171222386 est repete 2 fois [4014523 4178258 ]
493337816967 est repete 2 fois [315458 3344903 ]
617314402174 est repete 2 fois [1491421 3665914 ]
238736143232 est repete 2 fois [96106 3681379 ]
182428036637 est repete 2 fois [533908 2812393 ]
528333149232 est repete 2 fois [1631619 3485164 ]
923295163412 est repete 2 fois [494142 4702474 ]
911107194538 est repete 2 fois [2255209 4050609 ]
227113708026 est repete 2 fois [581265 3523865 ]
340737154117 est repete 2 fois [505659 2702371 ]
407719582282 est repete 2 fois [76221 4165646 ]
570420451489 est repete 2 fois [483946 4716727 ]
532531180082 est repete 2 fois [638204 4322849 ]
020197153311 est repete 2 fois [42784 3330204 ]
574228782149 est repete 2 fois [123951 1714636 ]
071199204248 est repete 2 fois [127217 2690946 ]
632266371121 est repete 2 fois [894934 4846064 ]
198413477935 est repete 2 fois [3473960 4620965 ]
921633115889 est repete 2 fois [2825419 4904334 ]

Mon code prend 6mn 30s de temps CPU sur un P4 à 2.4 GHz (commande : doublons 5000000 7 15) et s'arroge jusqu'à 500 Mo de RAM, donc dépasse très largement la limite des 128 Mo de RAM que je m'étais fixée...

Code :

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <ext/hash_map>
#include <map>
using namespace std;
unsigned int N;
const unsigned long SEED = 17L;
typedef deque<char> Chaine;
inline void alea(unsigned long &rand){
static unsigned long r = SEED;
rand = r = 1664525UL * r + 1013904223UL;
}
int remplit_v(vector<char> &v, const int N)
{
// Pour un vecteur de 5000000 chiffres avec seed = 17 :
// 40 premiers chiffres : 1042235241197381276230666142972883492185
// 40 derniers chiffres : 1675913308512872428215612116421983834693
unsigned long r;
char buf[20] = "";
vector<char> tmp;
v.reserve(N);
for (int i = 0; i < N; i+= 5)
{
do alea(r); while (r < 10000UL);
sprintf(buf, "%u", r);
tmp.assign(buf, &buf[5]); // faute de mieux
copy(tmp.begin(), tmp.end(), back_inserter(v));
}
int num = 40;
cout << num << " premiers chiffres : ";
for (int k = 0; k < num; ++k) cout << v[k]; cout << endl;
cout << num << " derniers chiffres : ";
for (int j = N-num; j < N; ++j) cout << v[j]; cout << endl;
return v.size();
}
// Fonction de hachage (cf Taz)
struct FNV_hash{
inline unsigned operator()(const string& x) const
{
register unsigned hash = 2166136261u;
const string::size_type x_size(x.size());
for(register string::size_type i = 0; i < x_size;
hash = (hash * 16777619u)^x[i++]);
return hash;
}
};
typedef hash_map<const string, vector<int>, FNV_hash> HachageChaine;
int hache(HachageChaine &table_H, const vector<char> &vect, const int n)
{
string str;
HachageChaine::iterator it;
str.reserve(100);
table_H.resize(N-n+1);
for (unsigned int i = 0; i < N-n; ++i)
{
for(unsigned int j = i; j <= i+n; j++) str += vect[j]; //grossièrement répétitif
it = table_H.find(str);
if(it == table_H.end())
{
vector<int> v;
v.push_back(i);
table_H.insert(HachageChaine::value_type(str, v));
}
else
{
it->second.push_back(i);
}
str.erase();
}
return table_H.size();
}
int hache(map<const string, vector<int> > &table_M, const vector<char> &v, const int n)
{
string str;
map<const string, vector<int> >::iterator it;
str.reserve(100);
for (unsigned int i = 0; i < N-n; ++i)
{
for(unsigned int j = i; j <= i+n; j++) str += v[j];
it = table_M.find(str);
if(it == table_M.end())
{
vector<int> v;
v.push_back(i);
table_M.insert(pair<string, vector<int> >(str, v));
}
else
{
it->second.push_back(i);
}
str.erase();
}
return table_M.size();
}
void affiche_doublons(const vector<char>& vect , const int lmin, const int lmax)
{
HachageChaine table;
typedef HachageChaine::iterator H_iter;
for (int l = lmin; l <= lmax; ++l)
{
cout << "\nSéquences à " << l << " chiffres :\n";
cout << "Hachage : " << N - hache(table, vect, l) - l
<< " séquences trouvées\n";
for(H_iter it = table.begin(); it != table.end(); ++it)
{
string clef = it->first;
int card = it->second.size();
if(card > 1)
{
cout << clef << " est repete " << card << " fois [ ";
copy(it->second.begin(), it->second.end(),
ostream_iterator<int>(cout, " " ));
cout << "]" << endl;
}
}
table.clear();
}
}
void affiche_doublons_m(const vector<char>& vect , const int lmin, const int lmax)
{
map<const string, vector<int> > table;
typedef map<const string, vector<int> >::iterator M_iter;
for (int l = lmin; l <= lmax; ++l)
{
cout << "\nSéquences à " << l << " chiffres :\n";
cout << "Hachage : " << N - hache_m(table, vect, l) - l
<< " séquences trouvées\n";
for(M_iter it = table.begin(); it != table.end(); ++it)
{
string clef = it->first;
int card = it->second.size();
if(card > 1)
{
cout << clef << " est repete " << card << " fois [ ";
copy(it->second.begin(), it->second.end(),
ostream_iterator<int>(cout, " " ));
cout << "]" << endl;
}
}
table.clear();
}
}
int main(int argc, char* argv[])
{
vector<char> vect;
int lmin, lmax;
if (argc != 4 ) {
cout << "Usage : doublons N lmin lmax" << endl;
return -1;
}
N = atoi(argv[1]);
lmin = atoi(argv[2]);
lmax = atoi(argv[3]);
cout << "Genere un vecteur de " << N << " chiffres." << endl;
remplit_v(vect, N);
//affiche_doublons_m(vect, lmin, lmax);
affiche_doublons_h(vect, lmin, lmax);
return 0;
}

En prime, il y a la version avec map.

Message édité par el muchacho le 07-05-2004 à 21:18:47

Taz

bisounours-codeur

je vois pas le besoin d'utiliser des string

Kristoph

Le problème est assez pipo en fait. Si il est resolu pour n = 7 par exemple, et bien tout le reste en découle très très facilement et consomme forcement beaucoup moins de mémoire à traiter avec le résultat pour n = 7 disponible.

De plus la 2eme question n'a alors plus aucun sens car la réponse sera très vite donnée par la première question : il suffit de trouver le premier n pour lequel il n'y a pas de répétition

xterminhate

Si vis pacem, para bellum.

Je me permets de reposer ma question une fois de plus (elle n'a semble-t-il pas été comprise). Avez vous trouvé un nombre de plus de 12 chiffres ? C'est à dire 13 ou plus encore !! Person j'ai que des sequences de 12 chiffres au maximum.

---------------
Cordialement, Xterm-in'Hate...

el muchacho

Comfortably Numb

Taz a écrit :

je vois pas le besoin d'utiliser des string

Y'en a pas. J'avais commencé avec des deque<char> en fait (uniquement pour pouvoir faire un pop_front(); push_back() sur la fenetre...). C'est juste que l'implémentation de hash_map de STLPort accepte des char * ou des string. Mais il s'avère que le temps est passé en grande majorité dans les fonctions de la hashmap. J'ai pas mesuré mais je me demande si la fonction de hachage n'est pas un peu compliquée, ou si le fait d'utiliser des string ne ralentit pas grandement l'implémentation. Je n'en sais rien mais je compte essayer avec des char * ou au moins un vector<char> si possible.
Les quelques tests que j'ai faits donnaient la version avec hashmap seulement 50% plus rapide que la version avec map, ce qui est un peu décevant (sur des tableaux de l'ordre de ~50 000 caractères, sans doute pas assez grands).

Enfin, dans la fonction "hache()", je voulais faire un truc du genre :

Code :

pair<string, bool> res;
res = table_H.insert(HachageChaine::value_type(str, v));
if(res.second == false)
{
récupérer it d'une manière ou d'une autre
it->second.push_back(i);
}

ce qui m'aurait évité d'appeler la méthode find.
Y'aurait-il une manière de faire cela ?

Message édité par el muchacho le 07-05-2004 à 00:16:15

el muchacho

Comfortably Numb

Kristoph a écrit :

Euh, j'ai pas tout compris... à part le fait que on peut prendre les chaines de longueur n comme base pour trouver celles de longueur n+1 (j'y ai pensé, optimisation intéressante).
Pour la 2e question, c'est sûr que la méthode brutale marche, mais je voulais savoir s'il n'y avait pas une procédure plus directe. Ceci dit, avec l'optimisation proposée, c'est pas mal.

el muchacho

Comfortably Numb

xterminhate a écrit :

J'ai répondu. Tu n'as pas vu ?

Au fait, on peut voir ton code ? :bounce:

Message édité par el muchacho le 07-05-2004 à 00:21:15

Kristoph

Code :

$ time python sequence2.py > result.txt
137.34user 4.20system 5:42.74elapsed 41%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (25945major+163035minor)pagefaults 0swaps
$ ll result.txt
-rw-r--r-- 1 kristoph kristoph 46702592 mai 7 00:24 result.txt
$ cat sequence2.py
import psyco
psyco.full()
import os
f = file("data.txt","rb" )
data = f.read()
def recherche(data,size):
result = {}
for i in xrange(len(data)-size+1):
chunck = data[i:i+size]
val = result.get(chunck,None)
if val is None:
result[chunck] = [i]
else:
val.append(i)
return result
d = recherche(data,7)
for seq,posList in d.iteritems():
if len(posList) > 1:
print "Found %s at pos : %s" % (seq,posList)
os._exit(0)

Qui a dis que le python c'est lent :whistle:

Au fait, la config c'est un Athlon XP 1800+

Message édité par Kristoph le 07-05-2004 à 00:30:36

xterminhate

Si vis pacem, para bellum.

Donc le max est bien 12

---------------
Cordialement, Xterm-in'Hate...

xterminhate

Si vis pacem, para bellum.

Mon code n'est vraiment pas terrible, il tourne tellement lentement! Si je trouve le moyen de l'optimiser et si j'atteins des perfs acceptables, je le posterai.

Dans le principe, j'applique une fonction de traitement du signal : autocorrelation. Cela répond à la fois aux deux problèmes posés initialement. Ainsi, je compare l'aléa avec lui même sur toute sa longueur et pour tous les décalages possibles compris entre 1 (pas 0 evidemment) et 5.000.000.

Mon code est en fait une double boucle for imbriquée avec au milieu un test : alea[t]==alea[delta_t+t). Ainsi, je mesure le taux de corrélation, et lorsque j'obtiens un pic de correlation, je suis en présence d'une séquence qui se répete. Je relève donc toutes les séquences qui ont générées un pic de correlation supérieur ou égale à 7.

Mais bon, j'ai lancé mon code sur une machine d'appoint (Celeron300) et dans la version complète (relevé des séquences de 7 à 15), il prend son temps (28jours j'avais calculé)!

Message édité par xterminhate le 07-05-2004 à 00:41:13

---------------
Cordialement, Xterm-in'Hate...

Taz

bisounours-codeur

f = file("data.txt","rb" )
data = f.read()

laid

val = result.get(chunck,None)
if val is None:

laid, mauvais, utilise setdefault

os._exit(0)
...

Kristoph

Taz a écrit :

f = file("data.txt","rb" )
data = f.read()

laid

Peut être mais tu mettrais quoi à la place ?

Taz a écrit :

val = result.get(chunck,None)
if val is None:

laid, mauvais, utilise setdefault

Alors là pas d'accord. Je ne vois vraiment pas ce que setdefault viens faire ici.

Taz a écrit :

os._exit(0)
...

C'est pour ne pas faire desallouer la mémoire à la fin du script. Je prendrais sinon la moitié en quittant le programme :whistle:

Message édité par Kristoph le 07-05-2004 à 01:05:59

Taz

bisounours-codeur

data = file("data.txt","rb" ).read()

result.setdefault(chunck, []).append(i)

Kristoph

Taz a écrit :

data = file("data.txt","rb" ).read()

result.setdefault(chunck, []).append(i)

Mouais, ce n'est pas evident au premier abord que la methode setdefault renvoie le resultat de get apres affectation. En tout cas, je ne pense pas que ce soit plus clair que ce que j'ai ecris

Et pour le file, j'essaye d'eviter ce genre de syntaxe car on ne peux pas faire explicitement appel à close() de cette façon. ( appel que j'ai oublié dans le code ... )

Taz

bisounours-codeur

au si ça l'est. et c'est bien plus rapide

« Et pour le file, j'essaye d'eviter ce genre de syntaxe car on ne peux pas faire explicitement appel à close() de cette façon. ( appel que j'ai oublié dans le code ... ) »

et les __del__ de python c'est du vent ? python __a__ des destructeurs et il les __appelle__ systématiquement (sauf cyle)

alors re pose toi dessus et oubli le C

el muchacho

Comfortably Numb

xterminhate a écrit :

Ah oui, effectivement, c'est un peu "bourrin" !
La méthode rapide pour l'autocorrélation est d'utiliser des FFT -> n Log (n).

Avec l'optimisation proposée plus haut, je devrais pouvoir faire tomber ma méthode à moins de 2 minutes sur un gros P4.

el muchacho

Comfortably Numb

el muchacho a écrit :

Enfin, dans la fonction "hache()", je voulais faire un truc du genre :

Code :

pair<string, bool> res;
res = table_H.insert(HachageChaine::value_type(str, v));
if(res.second == false)
{
récupérer it d'une manière ou d'une autre
it->second.push_back(i);
}

ce qui m'aurait évité d'appeler la méthode find.
Y'aurait-il une manière de faire cela ?

Je me disais bien que ça existait. Il suffisait de lire le fuckin' manual :

Code :

pair <HachageChaine::iterator, bool>
res = table_H.insert(hash_map<string,
vector<int>,
FNV_hash>::value_type(str, v));
if(res.second == false) res.first->second.push_back(i);

Message édité par el muchacho le 10-05-2004 à 09:24:06

assyrium

Kristoph a écrit :

Code :

$ time python sequence2.py > result.txt
137.34user 4.20system 5:42.74elapsed 41%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (25945major+163035minor)pagefaults 0swaps
$ ll result.txt
-rw-r--r-- 1 kristoph kristoph 46702592 mai 7 00:24 result.txt
$ cat sequence2.py
import psyco
psyco.full()
import os
f = file("data.txt","rb" )
data = f.read()
def recherche(data,size):
result = {}
for i in xrange(len(data)-size+1):
chunck = data[i:i+size]
val = result.get(chunck,None)
if val is None:
result[chunck] = [i]
else:
val.append(i)
return result
d = recherche(data,7)
for seq,posList in d.iteritems():
if len(posList) > 1:
print "Found %s at pos : %s" % (seq,posList)
os._exit(0)

Qui a dis que le python c'est lent :whistle:

Au fait, la config c'est un Athlon XP 1800+

J'ai essayé ce programme sur ma machine (je ne suis absolument pas un connaisseur en python), mais le programme a tourné plus de 10 minutes, l'ordi s'est mis à swaper comme un fou (mes pauvres 512Mo ne suffisaient pas). Y a t'il une explication (peut être mon fichier data qui n'était pas correct syntaxiquement) ? Autrement, j'aurai une version c++ qui mettrait 3 mn sur un athlon 2000+ (mais il faut que je vérifie le résultat) qui fonctionne avec des arbres avl (et qui n'est pas du tout optimisée : c'est très moche). Je posterai le code dès que ça sera vérifié.

Kristoph

assyrium a écrit :

Moi aussi j'ai seulement 512Mo et ça suffisait tout juste à faire marcher cette version. J'en ai une autre qui prend un peu moins de place pour n=7 mais pour réduire encore la consomation mémoire, il va falloir passer à du C ou du C++

assyrium

Kristoph a écrit :

Ah oui, en + je n'avais pas fait attention que c'était pour n=7(j'ai recopié bêtement le code).ma version fait pour n=7 à n= 15... à priori ça prend à peu près 100 Mo (je suis en train de mesuree). Mais je le fais en plusieurs passes, c'est pas très propre... et si je fais en une passe, avec des arbres dans les arbres (ça accélère de 2 ou 3 fois), ça prend 500 Mo à 20% de tous les calculs... va faloir trouver un moyen de changer ça.

el muchacho

Comfortably Numb

Kristoph a écrit :

Personne n'a encore essayé en Ocaml ?
Je pars en vacances 15 jours et au retour, je m'y colle.

Message édité par el muchacho le 08-05-2004 à 14:08:02

assyrium

J'ai un peu optimisé, mnt ça met 45 secondes sur un amd 2000+, et ça utilise environ 250 mo de ram. Par contre, le code fait 400 lignes environ, je ne sais pas si ça ne gêne pas (ou se fait) de poster un message de cette taille.

Taz

bisounours-codeur

bah cai psyco qui te fait tout péter je pense là

el muchacho

Comfortably Numb

assyrium a écrit :

Si si, ça devrait être intéressant. Vas-y, envoie.

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;
}

Voilà... Y'a beaucoup de choses en dur (notamment le nb max de positions dans la classe Position). Ensuite, le programme perd finalement beaucoup de temps à générer le fichier résultat (en redirection avec > ). D'autres choses sont moches, mais ça a été fait à l'arrache. Soyez indulgents, merci.

lecouteux@zorglub:~$ time ./rdoublon >result

real 0m35.759s
user 0m32.150s
sys 0m3.520s

Là c'est sur un ordi de mon université, un xeon à 2,4 Ghz.
Ensuite, je pense qu'on peut encore pas mal optimiser le code pour accélérer de deux fois... mais j'pense que je vais m'arrêter là.

Message édité par assyrium le 11-05-2004 à 14:30:08

Taz

bisounours-codeur

adieu, c'est trop pour moi

el muchacho

Comfortably Numb

assyrium, mets ton code entre les balises "[ c p p ]" et "[/ c p p ]" (enlève les espaces que j'ai rajoutés pour éviter qu'elles ne soient inerprétées).

Ensuite, quelques commentaires ne seraient pas de trop, surtout que ton algo est costaud, et que tout le monde ne sait pas ce qu'est un arbre AVL (ce qui est mon cas... :sweat: ).

Enfin, petite remarque :

Code :

bool operator > (Position &p)
{
if (n > p.n) return true;
return false;
}

Peut être écrit

Code :

inline bool operator > (Position &p){ return (n > p.n); }

En tout cas, chapeau bas, parce que ton algo tient la corde, et de loin, et même en l'optimisant, je ne pense pas que ma solution puisse atteindre cette performance.

Message édité par el muchacho le 09-05-2004 à 17:02:00

Publicité

Page : 1 2 3

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

[Concours] Recherche de doublons dans une séquence

Sujets relatifs
Recherche de chaine	Recherche d'imprimantes réseau en PHP
Recherche cours et didacticiels: JSP/Servlet/JavaBeans - Struts - MVC2	[Java WebStart]Recherche d'un tutorial
[C++] recherche tutorial COMPLET et SERIEUX sur DLL win32	Comment passer d'une séquence d'images BMP à une video ?
Recherche API	fonction de recherche de fichier en C [LINUX]
éviter les doublons	[Access97] Recherche avec l'option "tous" (zone de liste modifiable)
Plus de sujets relatifs à : [Concours] Recherche de doublons dans une séquence

Page générée en 0.258 secondes